哎哟 大周日的， 又是约饭又是要约吃鸡的，我只能说我尽量写几道题吧，真是堕落呀
- Binary Tree Zigzag Level Order Traversal
虽然是bfs分层遍历， 但是用到了deque，分两个方向去offer() poll(), 挺有意思，明天再写一遍
- Kth Smallest Element in a Sorted Matrix
看了答案写的，感觉挺麻烦的
要define一个Cell class，因为定义了新的PriorityQueue<Cell>，需要重新定义comparator
PriorityQueue<Cell> minHeap = new PriorityQueue<Cell> (k, new Comparator<Cell> () {
@Override
public int compare(Cell c1, Cell c2) {
if (c1.value == c2.value) {
return 0;
}
return c1.value < c2.value ? -1 : 1;
}
});
用priorityqueue 来做best first search，并存下visited[][], 然后再从matrix[i][j]->matrix[i+1][j]
matrix[i][j]->matrix[i][j+1]判断是否visited过后放入pq
minHeap.offer(new Cell(0, 0, matrix[0][0]));
visited[0][0] = true;
for (int i = 0; i < k - 1; i++) {
Cell cur = minHeap.poll();
if (cur.row + 1 < rows && !visited[cur.row + 1][cur.col]) {
minHeap.offer(new Cell(cur.row + 1, cur.col, matrix[cur.row + 1][cur.col]));
visited[cur.row + 1][cur.col] = true;
}
if (cur.col + 1 < rows && !visited[cur.row][cur.col + 1]) {
minHeap.offer(new Cell(cur.row, cur.col + 1, matrix[cur.row][cur.col + 1]));
visited[cur.row][cur.col + 1] = true;
}
}
return minHeap.peek().value;
78 subsets
DFS
有set.size()层，每层只有两个状态pick or not pick
// teminate condition, 每次触底时都加入到res中
if (index == nums.length) {
res.add(new ArrayList<>(list));
return;
}
// not pick
helper(nums, list, index + 1, res);
// pick
list.add(nums[index]);
helper(nums, list, index + 1, res);
list.remove(list.size() - 1);
- Generate Parentheses
有n对(), 所以有2n层，每层选'(' 或 ')'，但要注意如果是valid的话需要 cur出现过的'(' 比 ')' 多
用每次加完就 - 1的方法记录
注意这里没有做添加完删除的操作，因为我们每次必须添加，长度是不变的，添加不同时即会重置当前(像定义了array，定长)，但是像arraylist，stringbuilder这样的就得进行添加然后删除操作
// add '('
if (left > 0) {
arr[index] = '(';
parenthesis(arr, left - 1, right, index + 1, res);
}
// add ')'
if (left < right) {
arr[index] = ')';
parenthesis(arr, left, right - 1, index + 1, res);
}
***Combinations Of Coins
n叉树，注意teminate condition时候，最后一层特殊的操作
另外还要注意 coins[] 顺序从大到小还是从小到大
// terminate condition
if (index == coins.length - 1) {
if (target % coins[coins.length - 1] == 0) {
cur.add(target / coins[coins.length - 1]);
result.add(new ArrayList<Integer>(cur));
cur.remove(cur.size() - 1);
}
return;
}
n叉树
or (int i = 0; i <= max; i++) {
cur.add(i);
helper(target - i * coins[index], coins, index + 1, cur, result);
cur.remove(cur.size() - 1);
}
- Coin Change 2
我用的是想上题一样的思路，但是dp是更好的选择，毕竟只是要数量，不需要permutation
