9-1
-
number-of-islands (medium)
必须是vertical或者horizontal的“1”才是连成一个岛，这里用dfs进行搜索，遍历过的岛令其为0，这样就不会重复计算。 -
search-in-rotated-sorted-array (medium)
基础二分法，这里用start <= end作为判断，推进的时候要mid+1/-1
细节:1. start和mid可能指向同一个元素，所以即使没有dups，也要用>=来判断 -
前一段找递增和后一段找递增，两个if来解决问题。
-
meeting-rooms-ii (medium)
int[][] interval 拿出starts ends 分别sort，然后遍历一般，看start和end的关系。涉及图形学。
9-15
-
find-first-and-last-position-of-element-in-sorted-array (medium)
二分法有几个细节:
二分法找的是单个的res，不要指望二分法找出一个边界(那得运行两次)。
start找到的是，第一个不符合边界条件的值。
while(start <= end) 才有end = mid - 1和start = mid + 1 -
find-the-duplicate-number (medium)
虽然不是有序的，但它是1到n的自然数，所以核心是利用抽屉原理，如果10个数，前6个都比5小，那自然有重复的。这里是二分法的,o(nlogn)
最后return start还是end呢，要return从符合正常条件跳出来的那个量，那个才是我们要的，异常情况。
9-16
-
linked-list-cycle-ii （medium)
要返回的是cycle的起始位置，先用快慢指针找到一个有标志性的位置，然后再用while循环，确定点的位置。 -
binary-tree-zigzag-level-order-traversal (medium)
bfs，但是每一次变换一下布尔量flag的正负，就能实现zigzag的遍历，这里不用递归的话，用queue来实现。
用递归的话，bfs是要记录层数，分层数的奇偶性，也可以实现zigzag。
9-17
-
binary-tree-level-order-traversal-ii (easy)
level遍历，唯一的不同是最后res加的时候，加到arraylist的最前面。 -
word-search (medium)
二维数组遍历char来找一个string的word。用循环，i,j作为index遍历数组，start作为index遍历word。
很容易返回false,很难返回true，也就是最后结果找到了再返回true，用多个||来迭代res。
注意外面是一个双层for循环，里面才可以用index。
二维数组的数要赋值成别的值，防止重复，最后可以还原。
9.18
-
minimum-path-sum (medium)
典型的动态规划。两层for循环，先考虑边界的特殊情况，一般情况其实也不复杂，走到一个点，只能从它的左边或者上边，取最小值即可。注意这里直接修改原二维数组的值，然后取最右下角的一个数作为结果。 -
subsets (medium)
Backtracking典型题。回溯的核心就是靠的helper递归下一句的list.remove(list.size() - 1)
注意这里helper多take一个index，否则就是全排列了。
9.19
- next-permutation (medium)
弄明白permutation的含义，然后能写出swap和reverse工具函数。
private void reverse(int[] nums, int i, int j) {
while(i < j) {
swap(nums, i++, j--);
}
}
- binary-tree-paths (easy)
递归dfs，这个涉及maintain一个string。
9.23
-
combination-sum (medium)
backtracking题。helper函数里需要记录index，同时这个题说可以多次重复选取同一个元素，所以迭代helper函数的input是i而不是i+1。还有每一次input是target - certainNum。 -
rotate-image (medium)
二维数组的旋转都是通过横纵斜轴的翻转来实现的。
对角线翻转:直接双层for循环就可以了(第二个for循环 int j = i)，奇偶是无所谓的。
纵轴翻转: i < matrix[0]/length / 2
9.24
-
multiply-strings (medium)
全程模拟乘法的过程(变为加法)，首先确定结果是一个有限位数的数组。
另外，乘法的过程是，乘积加之前已有的进位，作为一个整体去处理。要抛弃的进位是=，下次接着用的则是+= -
group-anagrams (medium)
counting sort(存字母出现的次数)
hashmap value: list<string>
key: aabbc -> a2b2c1怎么制作呢? 用一个int[26]数组
how to get final result: return new ArrayList<>(map.values());
9.26
-
partition-list (medium)
ListNode排序的同时维护原有顺序，借助两个listnode分情况来加，最后接起来就是答案。
注意三个listnode都需要向前推进。 -
decode-ways (medium)
dp题。一个string表示的数，顺序应该是从左到右，这样可以判断数是否在10和26之间。
9.29
-
binary-tree-level-order-traversal (medium)
用队列queue来实现。 -
sort-list (medium)
listnode，用merge sort。merge sort就是分治，不断细分成更小，直到只有1个，那就要找中点，中点则要靠fast node和slow node来找。
比大小的逻辑在merge函数里实现。
网友评论