liuguohua.friend
BAN USERAlgorithm sketch:
max_bomb(v, r, denote_nothing) = max { v[i] + max_bomb(v, r, denote_i | i = 0 .. n-1}, where denote_nothing represent the initial state.
#include <stdlib.h>
#include <iostream>
#include <vector>
using namespace std;
bool in_range( vector<int> r, int j, int i ){
if (j < r.size() && i < r.size() && abs(j - i) <= r[i])
return true;
else
return false;
}
int max_bomb( vector<int> v, vector<int> r, vector<bool> destroy){
int n = v.size();
int max = 0;
vector<bool> flip; // for recovery
for(int i = 0; i < n; i++)
flip.push_back(false); // change from valid to destroy
for(int i = 0; i < n; i++ ){
if( ! destroy[i] ){
destroy[i] = true;
for( int j = 0; j < n; j++){
if( in_range(r, j, i) && !destroy[j]){
destroy[j] = true;
flip[j] = true;
}
}
int cur = v[i] + max_bomb( v, r, destroy);
max = cur > max? cur : max;
// recover
destroy[i] = false;
for( int j = 0; j < n; j++){
if(flip[j] == true){
destroy[j] = false;
}
}
}
}
return max;
}
int main(){
vector<int> v;
v.push_back(2);
v.push_back(1);
v.push_back(3);
vector<int> r;
r.push_back(0);
r.push_back(1);
r.push_back(1);
vector<bool> destroy;
for(int i = 0; i < v.size(); i++)
destroy.push_back(false);
int max = max_bomb(v, r, destroy);
cout << max << endl;
}
Definition:
The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree.
Algorithm:
The diameter of a tree T is the largest of the following quantities:
* the diameter of T’s subtree (path does not go through the root)
* the longest path between leaves that goes through the root of T (this can be computed from the heights of the subtrees of T)
Code: (with test case in main)
#include <stdlib.h>
#include <iostream>
#include <vector>
using namespace std;
typedef struct node{
node* parent;
}Node;
int height( Node* n, vector<Node*> t ){
if( is_leaf( n, t ) )
return 0;
int maxH = 0;
int size = t.size();
for(int i = 0; i < size; i++ )
if( t[i] -> parent == n )
maxH = height( t[i], t ) > maxH? height( t[i], t ) : maxH;
return maxH + 1;
}
bool single_child(Node* n, vector<Node*> t){
int size = t.size();
int cnt = 0;
for( int i = 0; i < size; i++ )
if( t[i] -> parent == n ){
cnt ++;
if( cnt >= 2 )
return false;
}
if( cnt == 1 )
return true;
}
int diameter ( Node* n, vector<Node*> t ){
if( is_leaf( n, t ) )
return 0;
else if( single_child( n,t ) )
return 0;
else{
int size = t.size();
int maxD = 0;
for( int i = 0; i < size; i++ ){ // not through n
if ( t[i] != n && t[i] -> parent == n ){
int d = diameter( t[i] , t );
maxD = d > maxD? d : maxD;
}
}
for( int i = 0; i < size; i++ ) // through n
if( t[i] -> parent == n )
for( int j = 0; j < size; j++ )
if( j != i && t[j] -> parent == n ){
int d = height( t[i], t ) + height( t[j], t ) + 3;
maxD = d > maxD? d : maxD;
}
return maxD;
}
}
int main(){
vector<Node*> t;
Node* n1 = new Node;
n1 -> parent = NULL;
Node* n2 = new Node;
n2 -> parent = n1;
Node* n3 = new Node;
n3 -> parent = n1;
node* n4 = new Node;
n4 -> parent = n2;
node* n5 = new Node;
n5 -> parent = n2;
node* n6 = new Node;
n6 -> parent = n5;
node* n7 = new Node;
n7 -> parent = n6;
t.push_back(n1);
t.push_back(n2);
t.push_back(n3);
t.push_back(n4);
t.push_back(n5);
t.push_back(n6);
t.push_back(n7);
cout << diameter( n1, t ) << endl;
}
Simple comparisons seem work to me. Does the following solution miss any key points?
To find the largest right-hand-word:
1. max = the first right-hand-word; // initialization
2. For each word{
3. if the word is a right-hand-word{
4. max = word > max? word : max;
5. }
6. }
7. Output max;
The comparison in 4 is defined, since the order of words must be given in the question (by the interviewer).
Here is an implementation.
- liuguohua.friend September 15, 2013