2019-04

4.1
1.leaf-similar-trees (easy)
所谓的leaf similar就是说，二叉树的末端的node，从左到右的序列是一样的。
要点1:不论什么遍历，判断root == null的语句都要放在最开头。
要点2:用postorder把root1，root2各自遍历一遍，利用数组+=，最后再判断每一个元素是否为0。

2.groups-of-special-equivalent-strings (easy)
题意比较复杂，所谓的special equivalent是说，经过一种特殊变化的两个string相等，那他俩就是special equivalent。我认为做题的过程中要复现这个特殊变化。

误区1:元素有可能有重复，第一时间排除hashset，应该是类似于hashmap的数组，做int[26]然后有这个字符就++。
误区2:这是一个二维数组，要分两层，把它当成两道题，来定义变量，来保存结果。不要想着一步到位。
误区3:定义数组总是出错 一是不要忘记是int[]，二是不要忘记加new。

这里很聪明的地方是用Arrays.toString把两个数组的结果合成了一个string。

3. intersection-of-two-arrays (easy)
   要点1:array是固定大小的，size未知的时候，用arrayList
   要点2:Integer[]转成int[]没有直接的方法，目前觉得arrayList变成int[]，可能需要一个for循环。
   要点3:学习一下写法:

if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
       return new int[0];
}

4.2

1. island-perimeter (周长) (easy)
   首先这是一个数学问题，4边的总个数减去公用的边。
   其次，要找一个方格四面的临近方格，很麻烦(因为同时有四个，而且循环的话会重复)，所以单向的看，也总能遍历到的，这样的话就是只有两个量需要maintain。

这里注意index和array size的大小比较要先进行，同时要具体分析这个不等式是啥样子。

4.3

1. meeting-rooms (easy)
   给几个时间段的meeting，来决定一个人能否都参加。
   要点:先根据开始时间做quicksort，然后核心是前一个meeting的结束时间早于下一个meeting的开始时间。

2. palindrome-permutation (easy)
   注意：char haha : s.toCharArray()

3. majority-element (easy)
   摩尔投票法。其实就是细分，如果在整体中是多数，那么细分到2个元素，也应该占一个(to some sense)

4.7

1. missing-number (easy)
   已知是0到n的自然数，从给的array中，找出miss的那个数。
   数字array的问题多考虑异或，异或的辅助变量应该是0。
   a^bb =a

2. best-time-to-buy-and-sell-stock (easy)
   遍历的时候要实时maintain一个profit，那么实时的股价减谁呢，所以还要maintain一个实时的最低股价。

3. lowest-common-ancestor-of-a-binary-search-tree (easy)
   binary search tree的核心就是search，利用值的大小关系分情况讨论。

4.8

1. implement-strstr (easy)
   自己实现一个string的indexOf。
   注意一:string相当于有个小尾巴，用substring的时候，endIndex要多加一。
   注意二:string之间的比较尽量用equals()。
   注意三:写for循环首先有个意识，index会不会超？然后取一个Index的最大值，确定这个边界的具体值。

要点一:不让用substring怎么办？类似于sliding window。

2. count-and-say (easy)
   要点一:从题意来看，下一个依赖上一个，只能递归，先写递归基，然后处理n-1的情况。
   要点二:for循环处理不了末尾的状态，要放在for循环后面处理。这里同时maintain i和i+1的情况，那么corner case就是length为1的时候，要注意。

3. sqrtx (easy)
   因为答案是整数，所以判断符合的条件是 input <= x / input && input + 1 > x / (input + 1)
   corner case是这个<=的=

4.10

1. largest-perimeter-triangle (easy)
   从array的多个element中找出能构成三角形的三边的最大的周长。
   困惑是不知道什么顺序来遍历。

先找数学关系:最长边<另外两遍之和
怎么知道最长边和次长边？这就需要先sort，从最大的可能性开始一个一个试，看能不能符合三角形的要求。

注意:要适应for循环倒着写，for(int i = len - 1; i > = 0; i --) {}

2. intersection-of-two-arrays-ii (easy)
   注意:sort了之后有点不知所措，要利用index和index++/index--

3. sort-array-by-parity-ii (easy)
   一是找到数学关系，二是双指针也可以考虑奇偶数。

4.12
1.add-binary (easy)
用string表示二进制，做加法。注意string里面的char要 减'0'才是Int。

2. palindrome-linked-list (easy)
   先把一般reverse，再去判断是否palindrome。

4.14

1. reverse-linked-list (easy)
   iteratively: 全局变量两个，一个是head本身，一个是newHead = null，局部变量一个是head.next，是为了把head.next保留下来。
   recursively: same，唯一的区别是最后两步可以直接用递归调用的赋值来实现。
   void和有返回值的递归，其实写起来没有区别，记得return就可以。

2. unique-email-addresses (easy)
   经典的string handle类型。

4.16

1. flipping-an-image (easy)
   一个极端复杂的读题过程。。有一些小型收获。
   一是，给一个array，1要变成0，0不变 => 去和1做异或(^= 1)
   二是，给一个array，首尾 两个指针，就是array[i]和array[n-1-i]
   三是，需要考虑array有奇数个 偶数个元素的时候，也就是多考虑奇数个元素的array的中间拿一个，可以用
   j < n / 2 + n % 2或者j * 2 < n

2. plus-one (easy)
   核心是:反着的，要注意。
   把一个array当成一个int一样去加1，首先只考虑末尾是不是9，然后这个问题可以一直推广到最高位，只要有不是9的，就直接可以输出了。
   重要的是，array当成一个整数，优先考虑for循环从n-1到>=0去遍历。注意array的Index和整数的数位是反着的。

3. add-strings (easy)
   这是一个进阶版本了，从加1变成了两个数相加。
   这里可以用i,j 二元的for循环。
   注意string.charAt这种方式无法对string进行修改，一般都采用StringBuilder。或者用toCharArray()来转换，往回转换的时候必须用String.valueOf(chars)

4.17

1. find-all-numbers-disappeared-in-an-array (easy)
   array有两个东西，一个是nums[i]，也就是值，另一个就是i，也就是Index。要把这两个东西区分开，在In place的问题中，我们就有了double的virtual space。
   没有要求排序的题里，不要尝试去得到一个排序的结果，同时quicksort也需要两重for循环。

2. reverse-vowels-of-a-string (easy)
   一个string只reverse元音字母，直观的就是用stack。但是这种题，inplace也可以用two pointers。

判断是否是元音字母，如果一个一个写if太麻烦，把所有可能元音拼成一个string用contains来判断比较好。

3. first-unique-character-in-a-string (easy)
   题设说只有26个小写字母，就暗示着可以用int[26]作为一个hashset。
   尽量不要用双重for循环，分别写两个for循环可以保证O(n)。

4.21

1. power-of-two (easy)
   判断是否是2的N次方。1是2的0次方，是个递归基，0不是2的N次方。
   考虑二进制，2的N次方的形式是10000.。return ((n & (n-1)) == 0 && n > 0);

2. power-of-three (easy)
   1是3的0次方。

3. paint-house (easy)
   三种颜色刷房子，相邻房子颜色不能重复，最终的cost要最小。
   这是一道DP题，因为三种颜色的选择导致的cost是一路积累来的。

这里有个学习到的trick是，两个数组也可以直接互换，用的是引用。(但如果两个都引用同一个数组的地址空间，可能会互相干扰，所以要互换一下)。

4.22

1. maximum-depth-of-binary-tree (easy)
   递归for now

2. second-minimum-node-in-a-binary-tree (easy)
   这个题，给了题设就可以分析出来，root.val是全局最小值。
   分治法可以解决，但是注意，递归一定要有递归基。当相等的时候要去找下一个candidate。

DFS遍历也可以。直观的理解就是，要找离全局最小值最接近的那个值。
注意比大小的时候，Long.MAX_VALUE，然后最终return的时候(int)类型转换。

3. maximum-subarray (easy)
   sliding window，注意要考虑全是负数的情况，要选一个最大值。