2019-05

5.6

1. symmetric-tree (easy)
   看一个树是否镜面对称，第一直觉是bfs，但还是用的递归和stack或者dequeue，也就是说不是一个树specific的问题。

首先是recursive的方法。

        return left==right;

很优雅的判空方式。
判断顺序是：判空->判两节点的val->判节点的子节点(recursive way)

然后是iteration方法。

2. valid-perfect-square (easy)
   判断平方数。二分法。

3. house-robber (easy)
   偷不相邻的家中的最大财务：动态规划。首先定义二维数组，然后找初始值，然后找n和n-1，n+1的关系。
   问题1:写for循环的时候，搞不清楚dp数组的Index。这里要用更make sense的index而不是dp数组的没有实际意义的Index。
   问题2:搞不清楚dp数组的含义，它代表的是可能的结果。

5.8

1. two-sum-iii-data-structure-design (easy)
   问题1: 这里对map的key和value概念不清晰，key才是结果，value只是一个结果出现的次数。同时一开始想不到value该代表什么所以无从下手，这里主要是考虑重复出现的元素。
   可以用

for(Map.Entry<Integer, Integer> entry : map.entrySet())

来遍历map

2. jewels-and-stones (easy)
   hashset题。

5.8

1. count-primes (easy)
   给出比某个数小的所有质数的数量。分解成两步，一是遍历比num小的所有数，二是写出函数isPrime()

从质数定义出发，如果不是质数，那么可以去找，这个数的因数(num % i == 0)，同时它小于sqrt(num)。

最佳方法是用Sieve of Eratosthenes。
注意这里用的boolean[]，The array will be initialized to false

5.13

1. range-sum-of-bst (easy)
   recursion的角度，这里的初始判断是(base)root.val，三种情况:1.排除root和左边2.排除root和右边3.root.val加左右

2. find-anagram-mappings (easy)
   hashmap, return any of the res.

5.14

1. remove-outermost-parentheses (easy)
   一堆嵌套的圆括号，只去掉最外层的圆括号。stack问题。
   几个小细节:char c : string.toCharArray() 和 stack.pop()没有Input param

2. to-lower-case (easy)
   转换大写字母到小写。
   几个小细节:
   string转换成charArray 才可以修改。
   iterator的方法无法改变原数组，只能用Index。
   算完ASCII之后，要(char)类型换换。
   charArray到string不能用，toString，要用new String(chars)

5.15

1. rotate-array （easy）
   reverse一次是不够的。先对整体reverse，然后0到k-1，然后k到len-1。

2. intersection-of-two-linked-lists (easy)
   用接续的方式来找第一个Intersection的节点。

5.16

1. linked-list-cycle (easy)
   快慢两个指针。

2. pascals-triangle-ii (easy)
   一定要先去考虑general后corner case。
   这里只用一层for循环是不够的。而且加和不是一次到位的。

5.19

1. min-cost-climbing-stairs (easy)
   动态规划。这里的特点是，相加的时候，可以1步也可以2步。所以最后时刻，要看dp[nums.length]和dp[nums.length-1]谁是最终的答案。

2. two-sum-ii-input-array-is-sorted (easy)
   在input array being sorted的情况下，就可以不用hashmap而是two pointers

3. invert-binary-tree (easy)
   bt左右颠倒。写递归要想办法确保它是不断迭代进行的。

5.20

1. find-all-anagrams-in-a-string (easy)
   sliding window。这个一开始没有思路是因为忘了用整数数组，整数数组的效果好于hashmap。
   不管符合不符合我们的hash，都要前进，过去多借的，要补回来。
   判断顺序也很有意思:先推进end，符合条件返回结果，符合条件推荐start并且还债。
2. remove-all-adjacent-duplicates-in-string (easy)
   去除相邻的duplicates，关键是去除一次之后，剩下的还相邻，还得去除(类似消消乐)
   这是一个stack问题，想到stack，就自然而然的解决了。
   注意stack pop的时候会使顺序颠倒，要用sb.reverse()。

5.21

1. shortest-unsorted-continuous-subarray (easy)
   题干是找一个不sorted的区域，sort这个区域之后只剩下sorted的array。
   这个要分前面一片和后面一片，当i的元素小于前面一片的最大值，或者n-i-1的元素大于后面一片的最小值，可以锁定这个区域。

2. convert-bst-to-greater-tree (easy)
   Recursion。bst每一个Node的值 要加 全树的比自己值更大的 值(也就是右子树或者是root)。
   应该先跑到最右子树端，然后往回走，注意值不要加两次。

5.27

1. climbing-stairs (easy)
   动态规划。
   应该对数组的长度和数组可容纳最大index更敏感一些。dp数组长度定义成n+1的原因是我们需要遍历到n。最终结果往往是n或者n-1。

2. diameter-of-binary-tree (easy)
   递归。但这里要做一个区分，需要一个global的变量记录结果，但每一个递归都要return这一轮的结果，这时候就需要一个helper function。

3. path-sum-iii (easy)
   两种做法：hashmap, two sum变体，递归(怎么处理currentSum的值，要区分现在的递归循环和上一个递归循环大的值)。dfs。

4. 对于hashmap，使用map.getOrDefault 可以有效替代复杂的containsKey选择。

5. 这里问的是有几种加和方法，这个不是储存在某个变量里，而是储存在hashmap的value里。

5.28

1. unique-morse-code-words (easy)
   java给数组赋值的方法 int[] d=new int[]{1,2,3,4}; 不像js那么随意
   不需要一个count变量了，直接用hashset.size()就可以。

2. sort-array-by-parity (easy)
   array, 把偶数sort到前面，奇数sort到后面。
   没有思路，让我们来尝试做个in place， two pointer。
   一步一步的判断，首位节点，是否是奇数偶数，再根据情况互换。
   要点一：有些地方可以不用else，接一个if继续判断。
   要点二：只要把奇数的都放到后面了，偶数自然都在前面，反之亦然，所以只用管一次。

5.29

1. n-repeated-element-in-size-2n-array (easy)
   问题:用o(1)的额外空间，能否确定某个变量出现了两次？不行。
   这里用hashset，比hashmap节省空间。

2. height-checker (easy)
   一些人排队，找出不符合 非降序 排列的人的个数。

不好找判断标准，不好找算法的思路。
很直接的方法:sort and compare
sort这里可以优化，可以用一个hashmap在给定input范围内，确保一个最优的排序方案，然后compare。

这个注意:还是没搞明白map的key和value，value是频次，key才是这里用到的height。