8月刷题/Mock interview接龙活动（缺米刷题的来）

50 Pow(x,n)

Cases:
1. pow(2,10)
2. pow(2,-10)
3. pow(1,0)

recursion的写法stack overflow了
iteration的写法还是time limit exceeded

加了3个corner case….1^n, (-1)^n, 0^n
没有考虑到underflow, 在n= Integers.MIN_VAlUE 变成-n的时候
还是time limit exceed…
———————————————
这道题很像 29 Divide Two Integers, 不可以用除法只能用减法，然后也是这里time limit exceed那里overflow & underflow

O(N) -> O(log2N)

Method 1: Fast Power Recursion
Time complexity: O(logN)
Space complexity: O(logN)-stack

Wrong answer cases:
2.00000
-2147483648

Wrong answer cases:
34.00515
-3
为了避免n=Integer.MIN_VAlUE, n=-n underflow, 就只写了
x=1/x, 那么遇到的recursion就是 一个1/x * 两个x (由-1产生的)

Method 2: Fast Power Iteration
Time complexity: O(logN)
Space complexity: O(1)

思路：
x^17：x->x^2 ->x^4->x^8->x^8*x^8*x = x^17
x^15:  x->x^2*x=x^3->x^6*x = x^7 -> x^14*x = x^15
注意到 每次n%2 == 1 的时候，都是*x，这个可以理解recursion的解法

Multiply Ans
x              1.0  x
x^2          x    x^3
x^4          x^3  x^7
x^8          x^7   x^15

49 Group Anagrams

Different ways of Hashing Strings

1. Sorting a string
2. Build a char[26] ca,
for (char c : s.toCharArray()) ca[c - 'a']++;
            String keyStr = String.valueOf(ca);
相当于count 每个字母，最终结果是string
3. 用int, 建一个26primes number array, int key = 1,
for (int j = 0, max = strs[i].length(); j < max; j++) {
                mapping *= PRIMES[strs[i].charAt(j) - 'a'];
            }
43 Multiply Strings

这道题比string addition要难了很多，之前只需要考虑两个相加。而且，任何试图用int 解决问题的方法，都会面临overflow的问题

Corner case 1: 最后add_on 有剩余
Corner case 2: 9133 * 0

这道题看上去挺复杂的，但是实际写起来也没有很多行。理清楚思路再code

8.2 Day2打卡
4题，主要是动态规划，
312 Burst Balloons
72 Edit Distance
241Different Ways to Add Parentheses
95Unique Binary Search Trees II

8月2号，刷了4道，再接再厉

Kth Larget Element in an Array
Decode Ways
Diameter of N-Ary Tree
Design HashSet

问个问题在这，大家有没有发现leetcode上用 GO 提交时候有Bug， 有很多次， 同样的test case， 用run test 和submit 出来的结果不一样。
望高人指点

08/02 3题打卡

字符串想加 遍历模拟想加过程 用stringbuilder模拟字符串增加
所有满二叉树 分成根 左右 分别进行递归实现
组合 选定当前数字 利用backtrack实现所有可能的组合

day 2：二叉树的问题有些要掌握both递归和非递归。

求加米，必回加。一起加油！

第一天开始打卡

8.2 打卡

1. Get the Maximum Score.  Two Pointers.
2. Design HashSet. 因为给的数值范围较小，可以简单的map解决
2. Minimum Swaps to Arrange a Binary Grid. 用list模拟Swap的过程。

8/2 打卡第2天， 刷了3道题

290. Word Pattern
用了两个hash table

304. Range Sum Query 2D - Immutable
用2D数组， (i+1,j+1) 存matrix(0,0)到（i，j）的元素的和

705. Design HashSet
用了python built-in set. 学习了set.remove, set.discard, set.pop的区别

今日5题！

今天做了Word Search II, Implement Trie，这两道题都是trie相关的，word search II的trie实现还没看完，
Search a 2D Matrix II，这道题是binary search，沿对角线向右向下binary search可以优化时间复杂度，但是这道题的divide and conquer解法还没看。
Regular expression matching是直接参考solution的，还需要再理解下。