Archive for August 24th, 2013
没啥可说的，对于每个cell，如过和word的开头字母一致，就生成一个新的全是false的visited[][], 进去原matrix开始前后左右的找。直到word的每个字母都找到为止。
要点：之前做的是直接
// left, right, up, down return find(board, i, j - 1, word, index + 1, visited) || find(board, i, j + 1, word, index + 1, visited) || find(board, i - 1, j, word, index + 1, visited) || find(board, i + 1, j, word, index + 1, visited);
这样就挂了！因为往左走的一路已经Update visited[][]了，然后没人去undo它，往右走的一支就直接拿来用了，不就乱套了么！所以在mark true的时候，函数结尾给undo一下，就可以保证一对儿出现，路径在反上来的被清理。
public boolean exist(char[][] board, String word) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == word.charAt(0)) {
boolean found = find(board, i, j, word, 0, new boolean[board.length][board[0].length]);
if (found)
return true;
}
}
}
return false;
}
private boolean find(char[][] board, int i, int j, String word, int index, boolean[][] visited) {
if (i < 0 || j < 0 || i >= board.length || j >= board[0].length)
return false;
if (board[i][j] != word.charAt(index) || visited[i][j])
return false;
visited[i][j] = true;
if (index == word.length() - 1)
return true;
// left, right, up, down
boolean found = find(board, i, j - 1, word, index + 1, visited) || find(board, i, j + 1, word, index + 1, visited)
|| find(board, i - 1, j, word, index + 1, visited) || find(board, i + 1, j, word, index + 1, visited);
visited[i][j] = false;//这样就能保证每次true的能给false回来
return found;
}
- In: 面经
- Leave a Comment
五分钟bug free，忍不住有成就感。
思路：root <= x，说明肯定不在左边，往右找；root >x，有可能是本身：如果root.left没找到，那就是本身了；如果找到了，那就返回找到那个。
public TreeNode getImmediateNext(TreeNode node, int x) {
if (node == null)
return null;
if (node.val <= x) {
return getImmediateNext(node.right, x);
} else {
TreeNode parent = node;
TreeNode findAtLeft = getImmediateNext(node.left, x);
return findAtLeft== null ? parent : findAtLeft;
}
}
[onsite] 找两个排好序的数组中的第k大的数
Posted on: August 24, 2013
private int findKth(int[] A, int[] B, int k) {
if (A.length == 0 && B.length == 0)
return 0;
return findKth(A, B, 0, 0, k);
}
private int findKth(int[] A, int[] B, int i, int j, int k) {
if (A.length – i > B.length – j)
return findKth(B, A, j, i, k);
if (i == A.length)
return B[j – 1 + k]; // the kth starting from j
if (k == 1) //when trying to find the first, just return the smaller head
return Math.min(A[i], B[j]);
int m1, m2; // section size
if (A.length – i < k / 2) { // A’s left over (start from A[i] to A[last]) can’t slice a size k/2 section
m1 = A.length – i;
} else {
m1 = k / 2;
}
m2 = k – m1;
int i1 = i + m1 – 1; // the pivot’s index in A
int j1 = j + m2 – 1;
if (A[i1] < B[j1]) // abandon A’s left section including A[i1]
return findKth(A, B, i1 + 1, j, k – m1);
else if (A[i1] > B[j1]) {// abandon B’s left section including B[j1],
return findKth(A, B, i, j1 + 1, k – m2);
} else {
return A[i1];
}
}
- In: 面经
- Leave a Comment
这个题和前几天做的另一道“找二叉树的第n个元素“一样，用到的是pass-count technique：用一个IntWrapper keep track of 线性的index。无论tree怎么走，这个index是不断增加的。
serialize很简单，用#表示null，然后中左右(pre order)的traverse一遍就变成serialize的文件了。
deserialize的话，和preorder一样，怎么来的就怎么populate回去。是#，说明populate null，就不用往下做了；不是的话，继续做；重点是要keep track of current element in the array，就用到了一个Integer wrapper好能把count的这个值一路传下去。需要特别小心的是，这个count要一直增加，不管当前是不是#！
Node deserialize(char[] arr, IntWrapper i) {
i.val++;//这个不能放if后面！
if (arr[i.val] == '#')
return null;
Node newNode = new Node(arr[i.val]);
newNode.left = deserialize(arr, i);
newNode.right = deserialize(arr, i);
return newNode;
}
Lexi's Leetcode solutions 