Avaln
BAN USERThis can be solved as a back tracking problem. Basically we make an agreement on the order of directions for checking the next step, use a stack to track the steps we are passed, update possible directions for the current step when move on to the next step and whenever there is a new step, check if it is back to the start point.
This problem can also been seen as a graph DFS problem. Basically we are looking for the longest cycle in a undirected unweighted graph. But since the data structure doesn't support graph DFS algorithm and it's too much work to create an adjacency list from this input matrix, the back tracking way is easier.
int FindCycle(int[][] M, int i, int j){
if(M == null)
return 0;
int m = M.length();
int n = M[0].length();
if(i > m - 1 || j > n - 1 || i < 0 || j < 0)
return 0;
Stack<Step> s = new Stack<Step>();
int count = 1;
boolean isBack = false;
int startI = i;
int startJ = j;
Step start = new Step(i, j, true, true, true, true);// all four directions are enabled
while(s.size() > 0 && !isBack){
Step cur = s.pop();
if(cur.right && j+1 < n && isPath(M[i][j+1]){
int i = cur.row;
int j = cur.column;
cur.right = false;
Step next = new Step(i, j+1, true, true, false, true);// disable the left direction
if(i == startI and j == startJ){
isBack = true;
break;
}else{
count++;
s.push(next);
}
}else if(cur.down && i+1 < n && canBeIncluded(M[i+1][j]){
// move down. the directions should be set to true, true, true, false
}else if(cur.left && j-1 >= 0 && canBeIncluded(M[i][j-1]{
// move left. the directions should be false, true, true, true
}else if(cur.up && i-1 >= 0 && canBeIncluded(M[i-1][j]){
// move up. the directions should be true, false, true, true
}else{
// reach a dead end
s.pop();
count--;
}
}
if(isBack){
return count;
}
}
boolean canBeIncluded(int value){
// check if the current element can be included
}
Class Step{
int row;
int column;
boolean right;
boolean down;
boolean left;
boolean up;
public Step(int i, int j, boolean r, boolean d, boolean l, boolean u){
this.row = i;
this.column = j;
this.right = r;
this.down = d;
this.left = l;
this.up = u;
}
}
Keep track of the current wave trend, up or down in a boolean value, swap adjacent numbers if the trend is violated. If swapped, go back one position to make sure it doesn't violate the sorted trend, but do not go back if i is already 0.
P.S. Can't believe the solution that requires sorting the entire array got the most votes.
WaveArray(int[] A){
int i = 0;
boolean up = true;
while(i < A.length() - 1){
if(isValidWave(up, i)){
i++;
up = !up;
}
else{
swap(A, i, i+1);
if( i > 0){
i--;
up= !up;
}
}
}
}
isValidWave(boolean up, int i, int[] A){
if(up)
return A[i] <= A[i+1];
else
return A[i] >= A[i+1];
}
These methods need parent link. If parent link don't exist, we can traverse the tree first and keep a parent array, and use the same methods. Or we can use recursive traverse, but pass two boolean values (one for target node, one for next node) and the target node along the way, whenever we see the boolean is true, it means we just found the target node, so the current recursion call, which should be visiting the next node, should set the next node boolean to true, and all other calls should bail out when they see the next node boolean is set to true.
- Avaln May 30, 2014FindNextNodeInOrder(Node root, Node node){
// search the first in-order node in the right tree
// because in in-order traverse, the left tree must
// have been traversed before we reach the current node
if(cur.right != null){
Node cur = node.right;
while(cur!= null){
cur = cur.left;
}
return cur;
}else{
// if there is no right tree, we search for the first ancestor
// who is a left child, this ancestor's parent will be the next
// node we are looking for. Be careful since we may reach the root
// without seeing any ancestor as a left child, in which case cur
// will end up being null.
cur = cur.parent;
while(cur!= null && cur != cur.parent.left){
cur = cur.parent;
}
if(cur!= null)
return cur.parent;
else
// no ancestor is a left child
// it means the node in question itself is the last node
// in the in-order traverse, there is no next node.
return null;
}
}
FindNextNodePreOrder(Node root, Node node){
if(cur.left != null){
return cur.left;
}else if(cur.right != null){
return cur.right
}else{
cur = cur.parent;
// complex logic, the false conditions are either cur is null
// or cur is left tree and it's right sibling is not null
// the while loops says keeping searching if we haven't found
// an ancestor who is a left child, or we found one but it's
// right sibling is null
while(cur!= null
&& ((cur != cur.parent.left)
||(cur == cur.parent.left && cur.parent.right == null))){
cur = cur.parent;
}
if(cur == null){
return null;
}else{
return cur.right;
}
}
}
FindNextNodePostOrder(Node root, Node node){
Node cur = node;
if(cur.parent == null){
return null;
}
if(cur = cur.parent.left){
if(cur.parent.right != null){
// search the left most node in the right sibling
cur = cur.parent.right;
while(cur.left != null){
cur = cur.left;
}
return cur;
}else{
return cur.parent;
}
}else{
return cur.parent;
}
}
You really want to review your understanding about basic graph algorithms, Sweetheart, this is by no mean could possibly be a breadth first search, it's depth first search. And given the data structure, it's not efficient to go with graph algorithms.
- Avaln May 31, 2014