LintCode/LeetCode 概括總結全集

05-03

一年多以前我在知乎上答了有關LeetCode的問題, 分享了一些自己做題目的經驗。張土汪：刷leetcode是什麼樣的體驗？

慢慢有一些贊和感謝, 備受鼓舞, 於是我把所做過的題目用一個script跑了一下，編輯成一篇文章。這也是我知乎的第一篇文章, 也是我GitHub(https://github.com/awangdev/LintCode)上面的的演算法總結頁面。

這個總結頁面是這麼規劃的：

題目名稱(答案鏈接)
題目難度
解題關鍵點

學習過程中, 我認為, 成事四分靠刷題, 六分靠總結. 在漫長的刷題過程中, 我們常常被海量的題目(據說今天已經有700題)壓得喘不過氣, 而常常忽略總結的必要性. 然而，在真正面試時，刷題的功底最重要的功能就是在聽到題目的的時候，能夠快速地反應，在腦中找到相應地關鍵字，再回憶起相應地答案。這個時候，對題目的熟知和關鍵點的掌握就非常重要。

當然，倒不是要將這份總結頁面倒背如流，但是起碼能在聽到某個題目時，很快想到該用什麼數據結構和方法，給自己有一個快而準的開端，會讓面試的過程流暢許多，少一些緊張。成事之後，又能少幾個月蹉跎：）

有朋友問，為什麼要把自己做的題目和題目總結放在GitHub上面分享？這些不是要私自珍藏的精華嗎？

Engineering的本質就是重複利用已有的精華，在已有的地基上創新前進。在我起初刷題的時候，我也蹉跎我也迷茫，不知道去哪找到做題的手感。那時候我找到許多前輩們在自己blog上面的題目解答，分享，給我帶來非常多的思路。我是個強調注重自己思考，走完全程的人，在前輩的見解上為基礎，按照所指引的方法嘗試，優化，最後交上一份自己的答案，建立起自己的知識網路。這每一步，都離不開最初所得到的指點。

當自己結束了刷題旅程後，心中充滿感激。為此，我特別把題目的精華寫成中文，方便中國人閱讀，複習起來也事半功倍。最後，總結了這篇長文章，希望給還在刷題事業中奔跑的中國人助力，希望大家找到自己心儀的工作！

如果對題目有什麼不同的見解，我特別希望你能給我留言，或者到我的GitHub上發一個issue/pull-request, 幫助到更多學習中的代碼仔!

Review Page

This page summarize the solutions of all problems. For thoughts,ideas written in English, refer to deach individual solution. New problems will be automatically updated once added.

0. A+B.java Level: Easy

^ 是不完全加法. 每次都忽略了進位。而 & 剛好可以算出需要的所有進位。

那麼就，首先記錄好進位的數字：carry. 然後 a^b 不完全加法一次。然後b用來放剩下的carry, 每次移動一位，繼續加，知道b循環為0為止。

在第一回 a ^ b 之後, b 的作用就消失了. 接下去應該給parameter重新命名. sum = a ^ b; // sum without adding carries nextCarry = (a & b) << 1;

用其他variable name 取代 a, b 會更好理解一點.

Bit Operation

Steps: a & b: 每bit可能出現的餘數

a ^ b: 每bit在此次操作可能留下的值，XOR 操作

每次左移餘數1位，然後存到b, 再去跟a做第一步。loop until b == 0

(http://www.meetqun.com/thread-6580-1-1.html)

1. Add and Search Word.java Level: Medium

Trie結構, prefix tree的變形： .可以代替任何字元，那麼就要iterate這個node所有的children.

節點裡面有char, isEnd, HashMap<Character, TrieNode>

Build trie = Insert word:沒node就加，有node就移動。

Search word:沒有node就報錯. 到結尾return true

這題因為.可以代替任何possible的字元，沒一種都是一個新的path，所以recursive做比較好些。

(iterative就要queue了,麻煩點)

2. Add Binary.java Level: Easy

方法一:土辦法沒技術，把binary換成數字，加起來，再換成binary。如果input很大，那麼很可能int,long都hold不住。不保險。

方法二:一般方法，string化為charArray,然後逐位加起，最後記得處理多餘的一個carry on

3. Add Digits.java Level: Easy

方法1: 普通做法就是按照題意, 把每個digit加起來. O(n)

方法2: 找數學規律, 每過9個數字, 取mod就會開始重複, 所以給所有數字取mod 就可以間接找到答案.

4. Add Two Numbers II.java Level: Medium

LinkedList並沒有反過來，那麼自己反：

方向相反。巧用stack.

做加法都一樣：

carrier
carrier = (rst + carrier) / 10
rst = (rst + carrier) % 10

5. Add Two Numbers.java Level: Easy

LinkedList都已經反轉好了，直接做。

遍歷兩個l1,l2把carry-on處理好，每次生成一個新node，最後檢查carry-on。

跟Add Binary的理解方式一模一樣。

6. Alien Dictionary.java Level: Hard

Not Done yet。 Topological sort.

7. Anagrams.java Level: Medium

HashMap 的做法. sort每個string, 存進HashMap, 重複的就是anagrams,最後輸出。

toCharArray Arrays.sort Stirng.valueOf(char[]) 時間nLO(logL),L是最長string的長度。
Arrays.toString(arr)的做法。arr是int[26], assuming only have 26 lowercase letters.
Count occurrance, 然後convert to String，作為map的key. Time complexity: nO(L)
另一種做法：http://www.jiuzhang.com/solutions/anagrams/

take each string, count the occurrance of the 26 letters. save in int[]count.
hash the int[] count and output a unique hash value.
hash = hash * a + num
a = a * b.
save to hashmap in the same way as we do.

這一步把for s: strs 裡面的時間複雜度降到了O(L). L = s.length().

Need to work on the getHash() function.

時間變成n*O(L). Better.

8. Backpack II.java Level: Medium

做了Backpack I, 這個就如出一轍。

想法還是，選了A[i-1] 或者沒選A[i].

一路往前跑不回頭。就出來了。

其實這個Backpack II 還更容易看懂代碼。

O(m)的做法:

想想，的確我們只care 最後一行，所以一個存value的就夠了。

注意：和bakcpackI的 O(m)一樣的，j是倒序的。如果沒有更好的j，就不要更新。就是這個道理。

9. Backpack.java Level: Medium

DP。

row是item大小: 0, A[0], A[1] ... A[A.length -1] col是背包累積的size: 0, 1, 2, ... m.

想法： dp[i][j]有這麼i-1個item, 用他們可否組成size為j的背包？true/false. （反過來考慮了，不是想是否超過size j，而是考慮是否能拼出exact size == j）。

注意注意：雖然dp裡面一直存在i的位置，實際上考慮的是在i位置的時候，看前i-1個item.

看一遍code，會發現：

picked A[i-1]: 如果上一個item, A[i-1],被加了上來, 用j-A[i-1]看看，是否這再前一步也true. true就好啦。
did not pick A[i-1]: 那就是說，不加上A[i-1], 上一行d[i-1][j]還是需要是true。

最後：

跑一邊dp 最下面一個row. 從末尾開始找，最末尾的一個j (能讓dp[i][j] == true)的，就是最多能裝的大小

時間，空間都是：O(mn)

再有：

O(m)時間的做法，具體看solution. 注意j是倒序的啊！

依然是O(mn)的空間

10. Balanced Binary Tree.java Level: Medium

DFS using depth marker: 每個depth都存一下。然後如果有不符合條件的，存為-1. 一旦有 <0 或者差值大於1，就全部返回Integer.MIN_VALUE. Integer.MIN_VALUE比較極端, 確保結果的正確性。最後比較返回結果是不是<0. 是<0，那就false. Traverse 整個tree, O(n)
Only calculate depth using maxDepth function. Same concept as in 1, but cost more traversal efforts.

11. Binary Representation.java Level: Hard

首先要分兩半解決，斷點是.: str.split(".");

Integer那一半好弄，whie loop里： num%2, num/2。

Decimal那邊複雜點. bit == 1的數學條件：當下num * 2 >= 1。更新: num = num * 2 - 1; bit == 0的數學條件： num * 2 < 1. 更新: num = num * 2

注意：num是 double, 小數在（num = num * 2 -1）的公式下可能無限循環. 因此check: num重複性，以及binary code < 32 bit.

(所以題目也才有了32BIT的要求！)

12. Binary Search Tree Iterator.java Level: Hard

用O(h)空間的做法：

理解binary search tree inorder traversal的規律：先找left.left.left ....left 到底，這裡是加進stack. 然後考慮parent,然後再right.

例如這題： stack裡面top，也就是tree最左下角的node先考慮,取名rst. 其實這個rst拿出來以後, 它也同時是最底層left null的parent，算考慮過了最底層的parent。最後就考慮最底層的parent.right, 也就是rst.right.

注意: next()其實有個while loop, 很可能是O(h).題目要求average O(1),所以也是okay的.

用O(1)空間的做法：不存stack, 時刻update current為最小值。

找下一個最小值,如果current有right child：

和用stack時的iteration類似,那麼再找一遍current.right的left-most child,就是最小值了。

如果current沒有right child:

那麼就要找current node的右上parent, search in BinarySearchTree from root.

注意：一定要確保找到的parent滿足parent.left == current. 反而言之，如果current是parent的 right child, 那麼下一輪就會重新process parent。但是有錯:binary search tree裡面parent是小於right child的，也就是在之前一步肯定visit過，如此便會死循環。

13. Binary Tree Inorder Traversal.java Level: Easy

法一:

Recursive: Divide and Conquer, with helper(dfs) method

法二:

Stack: Add left nodes all the way

Print curr

Move to right, add right if possible.

注意stack.pop()在加完left-most child 的後，一定要curr = curr.right.

若不右移，很可能發生窘境：

curr下一輪還是去找自己的left-most child，不斷重複curr and curr.left, 會infinite loop, 永遠在左邊上下上下。

14. Binary Tree Level Order Traversal II.java Level: Medium

方法1: 跟Binary Tree Level Order Traversal一樣,只不過存result一直存在存在0位.

方法2(略複雜, 不需要): 普通BFS，用一個queue，加上一個queue.size()來交替換行. 或者多用一個queue來存下個level的nodes

方法3: DFS, 根據level來append每個list rst裡面add(0,...)每次都add在list開頭

15. Binary Tree Level Order Traversal.java Level: Medium

方法1. 最普通,Non-recursive: BFS, queue, 用個queue.size()來end for loop:換行。

或者用兩個queue. 當常規queue empty，把backup queue貼上去。

方法2. Recursive with dfs:

每個level都應該有個ArrayList. 那麼用一個int level來查看：是否每一層都有了相應的ArrayList。

如果沒有，就加上一層。

之後每次都通過DFS在相應的level上面加數字。

16. Binary Tree Longest Consecutive Sequence.java Level: Medium

屌炸天的4行代碼。Divide and Conquer

主要想法：

Recursive用好。首先在這個level比一比，可否成。

不成的話，另立門戶, count = 1。

然後左右開弓。再把結果拿過來比較一下就好了。

17. Binary Tree Maximum Path Sum II.java Level: Medium

比Binary Tree Maximum Path Sum I 簡單許多. 因為條件給的更多：at least 1 node + have to start from root => have to have root.

方法1:

維持一個global或者recursive里的sum。traversal entire tree via DFS. 簡單明了。

方法2:

Single path: either left or right.

If the path sum < 0, just skip it.

18. Binary Tree Maximum Path Sum.java Level: Medium

第一次做有點難理解，複雜原因是：因為可能有負值啊。不能亂assume正數。

single path max 的計算是為了給後面的comboMax用的。如果single path max小於0，那沒有什麼加到parent上面的意義，所以就被再次刷為0.

combo的三種情況：(root可能小於0)

只有left
2。只有右邊
root大於0，那麼就left,right,curr全部加起來。

情況1和情況2取一個最大值，然後和情況三比較。做了兩個Math.max(). 然後就有了這一層的comboMax

12.11.2015 recap:

So totally, 5 conditions:

(save in single)

left + curr.val OR right + curr.val

(save in combo:)

left, right, OR left + curr.val + right

19. Binary Tree Path Sum.java Level: Easy

Binary Tree的一個基本題。

遍歷到底，比較sum vs. target。

注意divide的情況。要把遍歷的例子寫寫。

LeetCode: Path Sum II

20. Binary Tree Paths.java Level: Easy

方法1：

Recursive:分叉。Helper。

方法2，Iterative:

非遞歸練習了一下

因為要每次切短list, 所以再加了一個Stack 來存level

21. Binary Tree Postorder Traversal.java Level: Easy

最prefer 2 stack的做法：

stack1和stack2合作。倒水。記這個做法。。。挺神奇的。

Divide and Conquer 的recursive方法也非常明了！

注意，這些binary tree traversal的題目，常常有多個做法:recursive or iterative

22. Binary Tree Preorder Traversal.java Level: Easy

Preorder 寫寫， stack

Divide and conquer
Stack(NON-recursive) push curr, push right, push left.
recursive with helper method

23. Binary Tree Right Side View.java Level: Medium

最右:即level traversal每一行的最末尾.

BFS，用queue.size()來出發saving result.

24. Binary Tree Serialization.java Level: Medium

方法1: BFS. Non-recursive, using queue. 想法直觀。level-order traversal. save到一個string裡面就好。

方法2: DFS. Recursive. 需要一點思考。basically divide and conquer. 但是代碼相對來說短。

25. Binary Tree Zigzag Level Order Traversal.java Level: Medium

簡單的level traversal.根據level奇數偶數而add到不同位子.

26. Building Outline.java Level: Hard

又叫做skyline

看網上的解答做，思路很漂亮。（http://codechen.blogspot.com/2015/06/leetcode-skyline-problem.html?_sm_au_=isVmHvFmFs40TWRt）

跟scan line的approach類似:

把所有點分出來，每個點有index x, 再加上一個height.
在這個list上排序，根據index和height（注意用負數標記building start point,這樣保證start在end 之前。）. 叫做 heightPoints
在processs時候用max-heap (reversed priorityqueue)，在ieteraete heightPoints 來存最大的height . 遇到peek,就是一個合理的解
處理1：因為start,end的height都存在了heightPoints裡面，這裡就是用來check end of bulding的，然後把height 從queue裡面remove. 處理2：重複x 上面的許多height? priorityqueue給了我們最高，這okay了；那麼其他的重複點，用一個int prev來mark之前做過的，一旦重複，跳過。

想法非常natural。大題目，腦子亂。

看了解答再去想，挺naturally doable的。

27. Burst Balloons.java Level: Hard

其實會做之後挺好想的一個DP。 dp[i][j] = balloons i~j 之間的sum. 然後找哪個點開始burst? 設為x。 For loop 所有的點作為x，去burst。每次burst都切成了三份：左邊可以recusive 求左邊剩下的部分的最大值 + 中間3項相乘 + 右邊遞歸下去求最大值。

這個是momorization, 而不純是DP 因為recursive了，其實還是搜索，但是memorize了求過的值，節省了Processing

28. Change to Anagram.java Level: Easy

簡單的check int[26] 26個小寫字母是否需要改變。若需要count+1.

主要HackerRank里要注意自己寫: Scanner, import java.util, non-static method ...etc.

注意: 最後count出來要除以2：字母不同，會在不同的字母位上加減count,那麼就是剛好重複計算了一遍。所以除以二。

29. Classical Binary Search.java Level: Easy

while: start + 1 < end mid = start + (end - start) / 2; 末尾double check start, end.

30. Climbing Stairs.java Level: Easy

方法1: DP。爬坡到i點總共有的方法，取決於i-1點和i-2的情況。也就是DP(i-1) + DP(i-2).

還可以用滾動數組優化一點：因為用到的變數就只有i,i-1,i-2，可以被替代。注意要寫好『滾動』的代碼。

方法2: DFS但是timeout

31. Clone Graph.java Level: Medium

Use HashMap to mark cloned nodes.

先能複製多少Node複製多少。然後把neighbor 加上

32. Closest Binary Search Tree Value.java Level: Easy

Binary Search. 記錄找到過的closest. 直到tree leaf, 找完return

33. Closest Number in Sorted Array.java Level: Easy

跟Closest Binary Search Tree Vlaue類似：

Binary search. 考慮mid-1, mid+1.

一旦沒有mid = target.index。那麼target最終就narrow down在(mid-1,mid) 或者(mid,mid+1)

34. ColorGrid.java Level: Medium

用HashMap，理解題目規律，因為重複的計算可以被覆蓋，所以是個優化題。

消滅重合點:

如果process當下col, 其實要減去過去所有加過的row的交接點。。。

再分析，就是每次碰到row 取一個單點, sumRow += xxx。

然後process當下col時候， sum += colValue * N - sumRow. 就等於把交叉所有row（曾經Process過的row）的點減去了。很方便。

最後read in 是O(P), process也是O(P).

35. Combination Sum II.java Level: Medium

還是DFS. 和Combination Sum I 類似.

確保Helper是用i+1，下一層的數字, 不允許重複。

36. Combination Sum.java Level: Medium

遞歸，backtracking. 非常normal。需要先sort.

記得求sum時候也pass 一個sum進去，backtracking一下sum也，這樣就不必每次都sum the list了。

題目裡面所同一個元素可以用n次，但是，同一種solution不能重複出現。如何handle?

用一個index （我們這裡用了start）來mark每次recursive的起始點。
每個recursive都從for loop裡面的i開始，而i = start。也就是，下一個iteration,這個數字會有機會被重複使用。
同時，確定在同一個for loop裡面，不同的Index上面相同的數字，不Process兩遍。用一個prev 作為checker.

假如[x1, x2, y, z], where x1 == x2，上面做法的效果: 我們可能有這樣的結果: x1,x1,x1,y,z

但是不會有:x1,x2,x2,y,z

兩個solution從數字上是一樣的，也就是duplicated solution, 要杜絕第二種。

37. Combinations.java Level: Medium

Combination DFS。畫個圖想想. 每次從1~n裡面pick一個數字i

因為下一層不能重新回去 [0~i]選，所以下一層recursive要從i+1開始選。

38. Compare Strings.java Level: Easy

比較一下大小, null.

然後用char[]來count chars from A. 再對照chars in B.

39. Complete Binary Tree.java Level: Easy

BFS

Use a flag . 當出現了第一次有 null children的node的時候，

說明complete tree的最低level出現了。

自此以後，queue再不該有node再有child, queue後面出現的node的左右孩子應該都是null.

40. Construct Binary Tree from Inorder and Postorder Traversal.java Level: Medium

寫個Inorder和Postorder的例子。利用他們分left/right subtree的規律解題。

Postorder array 的末尾，就是當下層的root.

在Inorder array 裡面找到這個root,就剛好把左右兩邊分割成left/right tree。

這題比較tricky地用了一個helper做recursive。特別要注意處理index的變化, precisely考慮開頭結尾

可惜有個不可避免的O(n) find element in array.

41. Construct Binary Tree from Inorder and Preorder Traversal.java Level: Medium

和Construct from Inorder && Postorder 想法一樣。

寫出Preorder和Inorder的字母例子，發現Preorder的開頭總是這Level的root。依此寫helper,注意處理index。

42. Container With Most Water.java Level: Medium

類似木桶理論。盛水的最高取決於最低的那面牆。左右兩牆，往中間跑動。另，若一面牆已經小於另外一面，就要移動，換掉矮牆（可能下一面更高，或更低）；但決不能換掉當下的高牆，因為低牆已經limit的盛水的上限，若高牆移動，導致兩牆之間距離減少，就註定水量更少了。（弄啥來，不能缺心眼啊）

43. Contains Duplicate II.java Level: Easy

方法1: HashTable<value, list of duplicates>, brutly check agains the list 方法2: 很巧妙地根據k range地條件, 把HashSet裡面的值控制在[i - k, i]. 那麼一旦match, 就符合條件.

這兩種做法很藝術: 一般的想法是把符合條件的index找出來, 集中處理第二種做法是限定選拔的candidate, 不合格就去掉, 那麼一旦有符合條件的(duplicates), 那麼一定中.

44. Contains Duplicate III.java Level: Medium

與Contains Duplicate II 類似概念. TreeSet有BST 因此可以直接用, 而不用自己構建BST 簡化題目裡面的重要條件 Math.abs(A-B) <= t 而推斷出需要用 TreeSet.ceiling(x): return number greater or equal to x. 這個用法要記住吧, 沒別的捷徑.

45. Contains Duplicate.java Level: Easy

方法1: No brain: HashSet. O(n), 但是實際上比方法2 要慢. 方法2: 排序, 重複數會排在一起. Arrays.sort() time complexity nLog(n)

46. Convert Binary Search Tree to Doubly Linked List.java Level: Medium

會iterative traverse Binary Search Tree就好（Stack && handle left-dig-down）, 然後create Doubly-ListNode 時候注意就好.

注意inorder traversal在check right node的事後，

不論right == null or != null, 每次都要強行move to right.

如果不node = node.right,

很可能發生窘境：

node alays = stack.top(), 然後stack.top()一直是一開始把left 全部遍歷的內容。所以就會infinite loop, 永遠在左邊上下上下。

47. Convert Expression to Polish Notation.java Level: Hard

還是Expression Tree (Min-Tree).

根據題意，Tree出來以後，來個Pre-order-traversal.

Note: label需要是String.雖然 Operator是長度為1的char, 但是數字可為多位。

48. Convert Expression to Reverse Polish Notation.java Level: Hard

build expression tree。

這個裡面把TreeNode就當做成我們需要的node,裡面擴展成有left/right child的node.

建造Expression Tree,然後根據　Reverse Polish Notation 的定義，來個post-traversal就行了。

49. Convert Integer A to Integer B.java Level: Easy

Bit Manipulation

a^b 顯示出bit format裡面有不同binary code的數位.

每次 (a^b)>>i 移動i位之後，再 & 1時其實是指留下這一位的數字.

count it up

50. Convert Sorted Array to Binary Search Tree With Minimal Height.java Level: Easy

Binary Search的感覺. 中間一開兩半, divde and conquer,左右各自recursive下去build left/right child.

51. Convert Sorted List to Binary Search Tree.java Level: Medium

Divide and Conquer

用快慢pointer

找到mid。

然後把root = mid.next

然後開始sortedListToBST(mid.next.next); //後半段

mid.next = null;//非常重要，要把後面拍過序的斷掉

sortedListToBST(head); //從頭開始的前半段

最後root.left, root.right merge一下。

52. Copy List with Random Pointer.java Level: Medium

Basic Implementation, 其中用了一下HashMap:

遍歷head.next .... null.

每一步都check map裡面有沒有head。沒有？加上。

每一步都check map裡面有沒有head.random。沒有？加上。

53. Cosine Similarity.java Level: Easy

basic implementation

54. Count 1 in Binary.java Level: Easy

可以把integer -> string -> char array.
或者就 count += num << i & 1

55. Count and Say.java Level: Easy

Basic implementation. Count duplicates and print

56. Count of Smaller Number before itself.java Level: Hard

與Count of Smaller Number非常類似。以實際的value來構成segment tree，leaf上存（count of smaller number）。

Trick: 先Query，再modify.

每次Query時候，A[i]都還沒有加入到Segment Tree 裡面，而A[i+1,...etc]自然也還沒有加進去。

那麼就自然是coutning smaller number before itself.

刁鑽啊！

另外注意：

在modify裡面：多Check了root.start <= index 和 index <= root.end。過去都忽略了。以後可以把這個也寫上。

（其實是Make sense的，就是更加嚴格地check了index再 root.left 或者 root.right裡面的站位）

57. Count of Smaller Number.java Level: Medium

和平時的segment tree問題不同。 0 ～ n-1代表實際數字。是造一個based on real value的segment tree. Modify時，把array裡面的value帶進去，找到特定的位子（leaf）,然後count+1.

最終在SegmentTree leaf上面全是array裡面實際的數字。

trick:

在query前，給進去的start和end是： 0 ~ value-1.

value-1就是說，找比自己所在range小1的range（那麼自然而然地就不包括自己了），這樣就找到了smaller number.

[那麼其他做過的SegmentTree是怎麼樣呢？]

那些構成好的SegmentTree(找min,max,sum)也有一個Array。但是構成Tree時候，隨Array的index而構架。

也就是說，假如有Array[x,y,....]:在leaf,會有[0,0] with value = x. [1,1] with value = y.

[但是這題]

構成時，是用actual value.也就是比如Array[x,y,....]會產生leaf:[x,x]with value = ..; [y,y]with value =...

其實很容易看穿:

若給出一個固定的array構成 SegmentTree，那估計很簡單：按照index從0~array.lengh，leaf上就是[0,0] with value = x.

若題目讓構造一個空心SegmentTree, based on value 0 ~ n-1 (n <= 10000), 然後把一個Array的value modify 進去。

這樣八成是另外一種咯。

58. Count Primes.java Level: Easy

什麼是prime number: >=2的沒有除自己和1以外公約數的數。

還有另外一個定義方法!!

這個n,有沒有小於n的一個i,而達到： i*i + # of i = n. 如果有，那就不是 prime。

方法很牛逼也很數學。沒做的時候可能想不到。做了之後就覺得，哎，我去，有道理啊。

簡而言之：簡歷一個boolean長條，存isPrime[]。然後從i=2，全部變true.

然後利用這個因子的性質，非prime滿足條件： self*self, self * self + self ... etc.

所以就check每一個j, j+i, j+i+i, 然後把所有non-prime全部mark成false.

最後，數一遍還剩下的true個數就好了

59. Course Schedule II.java Level: Medium

詳細的中文分析，看Course Schedule I

60. Course Schedule.java Level: Medium

有點繞，但是做過一次就明白一點。

是topological sort的題目。一般都是給有dependency的東西排序。

最終都會到一個sink node，再不會有向後的dependency, 在那個點截止。

我就已這樣子的點為map的key, 然後value是以這個node為prerequisite的 list of courses.

畫個圖的話，prerequisite都是指向那個sink node，然後我們在組成map的時候，都是從sink node 發散回來到dependent nodes.

在DFS裡面，我們是反向的，然後，最先完全visited的那個node, 肯定是最左邊的node了，它被mark的seq也是最高的。

而我們的sink node，當它所有的支線都visit完了，seq肯定都已經減到最小了，也就是0，它就是第一個被visit的。

最終結果：每個有pre-requisit的node都trace上去（自底向上），並且都沒有發現cycle.也就說明schedule可以用了。

61. Data Stream Median.java Level: Hard

把Input stream想成向上的山坡。山坡中間那點，自然就是median.

前半段，作為maxHeap,關注點是PriorityQueue的峰點，也就是實際上的median.

後半段，作為minHeap,正常的PriorityQueue。開頭是最小的。

Note:題目定義meadian = A[(n-1)/2],也就是說maxHeap需要和minHeap長度相等，或者多一個element,最後可以直接poll() and return.

62. Delete Digits.java Level: Medium

數位靠前的，權值更大. 所以硬來把靠前的相對更大的（跟following digit相比）去掉。

63. Delete Node in the Middle of Singly Linked List.java Level: Easy

Just do it. Link curr.next to curr.next.next

64. Distinct Subsequences.java Level: Hard

Not Done

65. Edit Distance.java Level: Medium

Not Done

66. Encode and Decode Strings.java Level: Medium

方法1:

用數字+"#"+string來encode.

基於我們自己定的規律, 在decode的裡面不需要過多地去check error input, assume所有input都是規範的.

decode就是找"#",然後用"#"前的數字截取後面的string.

Old Solution:

Cast character into int. 串聯起來, seperate by "LINE".

handle empty list [], or just null: 要把Null特別mark一下為『NULL』, 這樣decode時才能check到。 adminadmin

67. ExcelSheetColumnNumber .java Level: Easy

A - A = 0. 所以 char - A + 1 = 題目里的對應數位。

26位運算和10位一樣嘛，num += 每位的digit * Math.pow(26, 數位號)。

68. Expression Evaluation.java Level: Hard

Build Expression Tree的另外一個變形，依然Min Tree.

build好Min Tree以後，做PostTraversal. Divde and Conquer：

先recursively找到 left和right的大小，然後evaluate中間的符號。

Note:

Handle數字時，若left&&right Child全Null,那必定是我們weight最大的數字node了。
若有個child是null,那就return另外一個node。
prevent Integer overflow　during operation:過程中用個Long，最後結局在cast back to int.

69. Expression Tree Build.java Level: Hard

和Max-tree一樣，感謝http://blog.welkinlan.com/2015/06/29/max-tree-lintcode-java/

這個題目是Min-tree，頭上最小，Logic 和max-tree如出一轍

注意treeNode,為了幫助ExpressionTreeNode 排序。它加了一個weight based on expression，協助build Min-Tree 排序。

Space: O(n) Time on average: O(n).

70. Fast Power.java Level: Medium

a^n可以被拆解成(aaa*a....*a)，是乘機形式，而%是可以把每一項都mod一下的。所以就拆開來take mod.

這裡用個二分的方法，recursively二分下去，直到n/2為0或者1，然後分別對待.

注意1: 二分後要conquer，乘積可能大於Integer.MAX_VALUE, 所以用個long.

注意2: 要處理n%2==1的情況，二分時候自動省掉了一份，要乘一下。

71. Fibonacci.java Level: Easy

方法1: DP array.

方法1.1: 滾動數組, 簡化DP。

方法2: recursively calculate fib(n - 1) + fib(n - 2). 公式沒問題, 但是時間太長, timeout.

72. Find Peak Element.java Level: Medium

還是binary search. 一個特別的check condition, 和特別的move left, move right的case罷了。

73. Find the Connected Component in the Undirected Graph.java Level: Medium

BFS遍歷，把每個node的neighbor都加進來。

一定注意要把visit過的node Mark一下。因為curr node也會是別人的neighbor，會無限循環。

Component的定義：所有Component內的node必須被串聯起來via path (反正這裡是undirected, 只要鏈接上就好)

這道題：其實component在input裡面都已經給好了，所有能一口氣visit到的，全部加進queue裡面，他們就是一個component裡面的了。

而我們這裡不需要判斷他們是不是Component。

74. Find the Weak Connected Component in the Directed Graph.java Level: Medium

Identify這是個union-find問題還挺巧妙。

看到了weak component的形式：一個點指向所有，那麼所有的點都有一個公共的parent，然後就是要找出這些點。

為何不能從一個點出發，比如A，直接print它所有的neighbors呢？

不行，如果輪到了B點，那因為是directed,它也不知道A的情況，也不知道改如何繼續加，或者下手。

所以，要把所有跟A有關係的點，或者接下去和A的neighbor有關係的點，都放進union-find裡面，讓這些點有Common parents.

最後output的想法：

做一個 map <parent ID, list>。

之前我們不是給每個num都存好了parent了嘛。

每個num都有個parent, 然後不同的parent就創造一個不同的list。

最後，把Map裡面所有的list拿出來就好了。

75. First Bad Version.java Level: Medium

Binary Search

根據isBadVersion的性質，判斷還如何end=mid or start=mid.

isBadVersion 是有方向的嘛，一個點錯了，後面全錯。

76. Flatten 2D Vector.java Level: Medium

大概意思就是把2D list裡面的element全部遍歷一遍。注意啊，一開始理解題意搞錯：我以為是必須要排序正確，所以上來就PriorityQueue+HashMap搞得無比複雜。其實，這個跟一個nxn的matrix遍歷，是沒區別的拉。所有來個x,y，把2d list跑一變。

77. Flatten Binary Tree to Linked List.java Level: Easy

Not Done

78. Flip Game II.java Level: Medium

12.06.2015 recap: 注意：不要亂改input s. recursive call 需要用原始的input s.

這個題目李特是屌炸天的。我飛了九牛二虎之力（路子對），但是代碼寫的七葷八素，好長好長好長好長的。結果正解，三四行就搞定了。真是心有不甘啊。想法如下：保證p1能勝利，就必須保持所有p2的move都不能贏。同時，p1隻要在可走的Move裡面，有一個move可以贏就足夠了。（題目裡面用一個for loop + 只要滿足條件就return true來表達 OR的意思：p1不同的路子，?贏一?種就行了） p1: player1 p2: player2

79. Flip Game.java Level: Easy

這個題目是很寂寞的. 2 pointer可以做, 在網上又搜了一下，貌似可以有很多牛逼的優化，我暫時還沒去看。很鬱悶的就是條件不明，原來只需要從++轉到--的情況，反過來沒必要關注...搞了我半天啊

80. Fraction to Recurring Decimal.java Level: Medium

不難想到處理除法：考慮正負，考慮小數點前後。主要是小數點以後的要著重考慮。很容易忽略的是integer的益處。

81. Generate Parentheses.java Level: Medium

遞歸。看thought.取或者不取(, )

Note: 在DFS時, 可以pass object (String) and re-create every time; or pass a reference (StringBuffer) and maintain it

82. Graph Valid Tree.java Level: Medium

複習Union-Find的另外一個種形式。

題目類型：查找2個元素是不是在一個set裡面。如果不在，false. 如果在，那就合併成一個set,共享parent.

存儲的關鍵都是：元素相對的index上存著他的root parent.

另一個union-find，用hashmap的：http://www.lintcode.com/en/problem/find-the-weak-connected-component-in-the-directed-graph/

83. Gray Code.java Level: Medium

題目蛋疼，目前只接受一種結果。

BackTracking + DFS:

Recursive helper里每次flip一個自己/左邊/右邊. Flip過後還要恢復原樣.遍歷所有.

曾用法（未仔細驗證）：

基本想法就是從一個點開始往一個方向走，每次flip一個bit, 碰壁的時候就回頭走。

84. Group Anagrams.java Level: Medium

方法一: 60%

和check anagram 想法一樣：轉化並sort char array，用來作為key。

把所有anagram 存在一起。注意結尾Collections.sort().

O(NKlog(K)), N = string[] length, k = longest word length

優化：80% ~ 97%

用固定長度的char[26] arr 存每個字母的frequency; 然後再 new string(arr).

因為每個位子上的frequency的變化，就能構建一個unique的string

錯誤的示範: 嘗試先sort input strs[]，但是NlogN 其實效率更低. 13%

85. Group Shifted Strings.java Level: Easy

相同shift規則的string, 能被推算到同一個零起始點，就是共同減去一個char,最後就相等。以此作為key，用HashMap。一目了然。

記得根據題目意思，一開始要String[] sort一下。

86. H-Index II.java Level: Medium

H-index的一個優化。 binary search

87. H-Index.java Level: Medium

例子寫出來，發現可以sort以後按照定義搜索一遍。 nlogn. 當然，搜索一遍時候可以優化，用binary search. 但是沒意義，因為array.sort已經用了nlogn

o(n)也可以，用bucket. 比較巧妙。

88. Hamming Distance.java Level: Easy

bit: XOR, &, shift>>

89. Happy Number.java Level: Easy

Basic Implementation of the requirements.

用HashSet存查看過的數值。若重複，return false.

90. Hash Function.java Level: Easy

解釋Hash怎麼道理。Hash function例子：

hashcode("abcd") = (ascii(a) * 33^3 + ascii(b) * 33^2 + ascii(c) *33^1 + ascii(d)*33^0) % HASH_SIZE

用到的參數比如: magic number 33, HASH_SIZE.

Hash的用法是：給一個string key, 轉換成數字，從而把size變得更小。

真實的implementation還要處理collision, 可能需要design hash function 等等。

每一步都：

hashRst = hashRst * 33 + (int)(key[i]);

hashRst = hashRst % HASH_SIZE;

原因是，hashRst會變得太大，所以不能算完再%...

91. HashHeap.java Level: Hard

非題.是從九章找來的HashHeap implementation.

92. HashWithArray.java Level: Easy

93. HashWithCustomizedClass(LinkedList).java Level: Medium

練習HashMap with customized class.

94. Heapify.java Level: Medium

Heap用的不多. 得用一下, 才好理解。

通常default 的PriorityQueue就是給了一個現成的min-heap：所有後面的對應element都比curr element 小。

Heapify裡面的siftdown的部分：只能從for(i = n/2-1 ~ 0)，而不能從for(i = 0 ~ n/2 -1): 必須中間開花，向上跑的時候才能確保腳下是符合heap規則的

Heapify/SiftDown做了什麼？

確保在heap datastructure裡面curr node下面的兩個孩子，以及下面所有的node都遵循一個規律。

比如在這裡，若是min-heap,就是後面的兩孩子都要比自己大。若不是，就要swap。

還是要記一下min-heap的判斷規律:for each element A[i], we will get A[i * 2 + 1] >= A[i] and A[i * 2 + 2] >= A[i].

siftdown時：在curr node和兩個son裡面小的比較。如果的確curr < son, 搞定，break while.

但若curr 並不比son小，那麼就要換位子，而且繼續從son的位子往下面盤查。

95. Heaters.java Level: Easy

第一步：生題型, 理解題意需要時間：從字面和畫圖而言, 就是定住房子一個個過，房子左右的distance需要足夠達到heater. 目標是招儘可能小的radius, 所以house和heater緊貼著是必要的. 在for loop裡面定下house，把heater當作一個區間移動, 達到的第一個合適區間，這就是當下最小的理想radius，取這個值跟既定radius作比較。比較之後，繼續移動house，再試著移動heater區間去match。

第二步： Binary Search

注意！題目沒有說given array是否sort, 我們必須sort才能夠區間移動或者binary search. TODO:http://www.cnblogs.com/grandyang/p/6181626.html

96. House Robber III.java Level: Hard

由於無法用簡單的方法構造DP array, 所以採取了普通的DFS。

The catch:

判斷當下的node是否被採用，用一個boolean來表示.

如果curr node被採用，那麼下面的child一定不能被採用。
如果curr node不被採用，那麼下面的children有可能被採用，但也可能略過，所以這裡用Math.max() 比較一下兩種可能有的dfs結果。

97. Identical Binary Tree.java Level: Easy

Divide, && 每種情況（左右一一對應)

注意 null states

98. Implement Queue using Stacks.java Level: Easy

雙Stack. 一個是等於是queue，一個是backfillStack. Tricky: 是在pop()和peek()的時候backfill, 並且要等到stack用完再backfill. 寫一下例子就知道，如果提早backfill，stack.peek()就不是queue的head了.

99. Implement Stack by Two Queues.java Level: Easy

兩個Queue,交互倒水用一個Temp做swap

做法1: 邏輯在top()/pop()里, 每次換水，查看末尾項.

做法2: 邏輯在push裡面:

x 放q2。
q1全部offer/append到q2.
用一個Temp做swap q1, q2. q1的頭，就一直是最後加進去的值.

100. Implement Stack using Queues.java Level: Easy

兩個Queue,交互倒水用一個Temp做swap

做法1: 邏輯在top()/pop()里, 每次換水，查看末尾項.

做法2: 邏輯在push裡面:

x 放q2。
q1全部offer/append到q2.
用一個Temp做swap q1, q2. q1的頭，就一直是最後加進去的值.

101. Implement Stack.java Level: Easy

stack 後入先出. Data Structure: ArrayList return/remove ArrayList的末尾項。

102. Implement Trie (Prefix Tree).java Level: Medium

Trie自己不多用到。如果是遇到一個一個字查詢的題，可以考慮一下。構建TrieNode的時候要注意：如何找孩子？如果是個map的話，其實就挺好走位的。而且，每個node裡面的 char 或者string有時候用處不大，可以為空。但是有些題目，比如在結尾要return一些什麼String，就可以在end string那邊存一個真的String。

103. Implement Trie.java Level: Medium

Tire, 也即是 Prefix Tree.

HashMap構建Trie。 Trie三個Method:　

Inset: 加 word
Search: 找word
StartWith: 找prefix

只有兩條children的是binary tree. 那麼多個children就是Trie。那麼沒有left/right pointer怎麼找孩子？

用HashMap，以child的label為Key，value就是child node。 HashMap走位

Note:

node里的char在這是optional。

另外有種題目，比如是跟其他種類的search相關，在結尾要return whole string，就可以在node里存一個up-to-this-point的String。

104. IndexMatch.java Level: Easy

有序, 假設有這樣的數字:target.

target 左邊的數字，一定不比index大，target右邊的數字，一定比index大。

這樣可以binary search.O(logn)

105. Inorder Successor in Binary Search Tree.java Level: Medium

畫inorder圖，發現規律.每個node的後繼node(successor)有幾種情況:

node.right 是個leaf到底了。那麼就return.
set rightNode = node.right，但發現rightNode has a lot left children to leaf.
比如, node.right == null，也就是node自己是leaf，要回頭看山頂找Inorder traversal規則里的下一個。
發現：其實就是每層都把路過的curr node放在stack里，最上面的，就是當下改return的那個successor:) Done.

106. Insert Interval.java Level: Easy

方法1：Scan Line

Interval 拆點，PriorityQueue排點。

Merge時用count==0作判斷點。

PriorityQueue: O(logN). 掃n點，總共：O(nLogn)

方法2：

O(n) 直接找到可以insert newInterval的位子. Insert。這裡已經給了sorted intervals by start point. 所以O(n)

然後loop to merge entire interval array

另外: 因為interval已經sort, 本想用Binary Search O(logn). 但是找到interval insert position， merge還是要用 O(n)。

比如剛好newInterval cover entire list....

107. Insert Node in a Binary Search Tree .java Level: Easy

往Binary Search Tree裡面加東西，一定會找到一個合適的leaf加上去。

那麼：就是說someNode.left or someNode.right是null時，就是insert node的地方。

找到那個someNode就按照正常的Binary Search Tree規律。

108. Intersection of Two Arrays.java Level: Easy

方法1: 用到hashset找unique && duplicate: O(m+n) 方法2: 可以用binary search 找數字. Note:binary search一定需要array sorted: nLog(m)

109. Intersection of Two Linked Lists.java Level: Easy

長短list，找重合點。長度不同的話，切掉長的list那個的extra length。那麼起點一樣後，重合點就會同時到達。

110. Interval Minimum Number.java Level: Medium

SegtmentTree, methods: Build, Query. 這題是在SegmentTreeNode裡面存min.

類似的有存:max, sum, min

111. Interval Sum II.java Level: Hard

SegmentTree大集合。記得幾個Methods: Build, Query, Modify. 不難。只是要都記得不犯錯:)

112. Interval Sum.java Level: Medium

其實是segment tree 每個node上面加個sum。

記得Segment Tree methods: Build, Query

Note: 存在SegmentTreeNode裡面的是sum. 其他題目可能是min,max ... or something else.

113. Invert Binary Tree.java Level: Easy

non-recursive: BFS with queue。或者regular recurisve - divide and conquer.

114. Isomorphic Strings.java Level: Easy

HashMap 來確認match。有幾種情況考慮:

Match. 就是map.containsKey, map.containsValue, and char1 == char2. Perfect.
Either Key not exist, or Value not exit. False;
Both key and Value exist, but map.get(char1) != char2. Miss-match. False.
None of Key or Value exist in HashMap. Then add the match.

115. Jump Game II.java Level: Hard

Greedy, 圖解 http://www.cnblogs.com/lichen782/p/leetcode_Jump_Game_II.html

維護一個range, 是最遠我們能走的.

index/i 是一步一步往前, 每次當 i <= range, 做一個while loop，在其中找最遠能到的地方 maxRange

然後更新 range = maxRange

其中step也是跟index是一樣, 一步一步走.

最後check的condition是，我們最遠你能走的range >= nums.length - 1, 說明以最少的Step就到達了重點。Good.

116. Kth Largest Element.java Level: Medium

用Quick Sort 裡面partion的一部分。

partion的結果是那個low, 去找 low==nums.size() - k，也就是倒數第K個。

沒找到繼續partion recursively.

sort的過程是排一個從小到大的list. (同樣的代碼還可以好xth smallest，mid變成x就好)

Quick Sort:

每個iteration, 找一個pivot,然後從low,和high都和pivot作比較。

找到一個low>pivot, high<pivot, 也就可以swap了。

得到的low就是當下的partion point了

117. Kth Smallest Number in Sorted Matrix.java Level: Medium

和Merge K sorted Array/ List 類似：使用PriorityQueue。

因為Array的element無法直接找到next,所以用一個class Node 存value, x,y positions.

118. Kth Smallest Sum In Two Sorted Arrays.java Level: Hard

用priority queue. 每次把最小的展開，移位。分別x+1,或者y+1:

因為當下的Min裡面x,y都是最小的。所以下一個最小的不是（x+1,y）,就是（x,y+1）。

每次就poll（）一個，放2個新candidate進去就好了。注意，這樣的做法會用重複，比如例子（7,4）會出現兩次。用一個HashSet擋一下。

注意，HashSet的唯一性，用一個"x,y"的string就可以代為解決。

119. Letter Combinations of a Phone Number.java Level: Medium

方法1: Iterative with BFS using queue.

方法2: Recursively adding chars per digit

120. Longest Common Prefix.java Level: Medium

Nested loop, 每一次比較所有string 同位是否相等。

相等，append string. 不等，return.

121. Longest Increasing Continuous subsequence.java Level: Easy

O(n)跑2遍for. O(1)是用了兩個int來存：每次到i點時，i點滿足條件或不滿足條件所有的longestIncreasingContinuousSubsequence. 特點：返跑一回，ans還是繼續和left輪的ans作比較；求的所有情況的最大值嘛。

122. Longest Palindromic Substring.java Level: Medium

方法1: 從中間劈開. 遍歷i，從n個不同的點劈開：每次劈開都看是否可以從劈開出作為palindromic的中點延伸。

Worst case: 整個string都是相同字元，time complexity變成： 1 + 2 +３　＋　．．．　＋n = O(n^2)

方法2: 窮舉double for loop. O(n^2)

123. Longest Substring with At Most K Distinct Characters.java Level: Medium

大清洗 O(nk)

map.size一旦>k，要把longest string最開頭（marked by pointer:start）的那個char抹掉

一旦某一個char要被清除，所以在這個char 的1st and last appearance之間的char都要被清洗from map

124. Longest Substring Without Repeating Characters.java Level: Medium

方法2:用兩個pointer, head和i.

HashMap<Char, Integer>: <character, last occurance index> head從index 0 開始。若沒有重複char, 每次只有for loop的i++。每次取substring[head,i]作為最新的string. 一旦有重複，那麼意味著，從重複的老的那個index要往後加一格開始。所以head = map.get(i) +１.

注意：head很可能被退回到很早的地方，比如abbbbbba,當遇到第二個a，head竟然變成了 head = 0+1 = 1.

當然這是不對的，所以head要確保一直增長，不回溯。

方法1：只要有non-existing char就count++. 一旦有重複char:

i = 新出現重複Char的位置. 重新init HashMap, count.

這個方法每次都把map打碎重來, 是可以的，也沒什麼不好。就是在for裡面改i，自己覺得不太順.方法二可能順一點。

125. Longest Univalue Path.java Level: Easy

弄明白path的意義: 連接node的edge. 要找MAX, 可以在class scope裡面定義一個max variable.

用minimum amount of code來概括幾種不同的情況: left == root, right == root, or left == root == right.

126. Longest Word in Dictionary.java Level: Easy

方法1: 按大小排序 -> 從最大的開始做contains()的比較 -> 結果再按照字母表順序(lexicographically) sort一下. 但是Collections.sort()了兩次, 而且再list.contains(), 比較慢

方法2: 先排序, 以最簡單的size==1以及set.contains()找match. 如果找到, 因為已經按照字母表排序, 找到的這個肯定是這個長度裡面最符合的解答. 然後brutally找下一個更大的. 法2比法1好, 因為只用了一次sort, nLog(n). 然後其餘都是O(1)的contains. 法1有兩個sort(), 然後在list上面contains(), 所以比較耗時.

方法3: 應該可以有一個用Trie的方式做的, 還沒有考慮.

127. Lowest Common Ancestor II.java Level: Easy

這個題有個奇葩的地方，每個node還有一個parent。所以可以自底向上.

曾經做的hashset的優化，找到的都存hashset. exist就return那個duplicate.
普通做法：2 lists。自底向上。利用parent往root方向返回。

注意：無法從root去直接搜target node 而做成兩個list. 因為根本不是Binary Search Tree！

128. Lowest Common Ancestor of a Binary Search Tree.java Level: Medium

方法1: 利用 BST的性質，可以直接搜到target node，而做成兩個長度不一定相等的list。然後很簡單找到LCA 方法2: Brutly尋找p和q的common ancestor, 然後recursively drive left/right. 非常巧妙, 但是也比較局限; 稍微變條件, 就很難recursive.

129. Lowest Common Ancestor.java Level: Easy

普通的Binary Tree，node child 自頂向下蔓延。

方法1：O(1) sapce O(h). Recursive. 循環的截點是：

當root == null或者 A B 任何一個在findLCA底部被找到了(root== A || root == B)，那麼就return 這個root.

三種情況：

A,B都找到，那麼這個level的node就是其中一層的parent。其實，最先recursively return到的那個，就是最底的LCA parent.
A 或者 B 找到，那就還沒有公共parent,return 非null得那個。
A B 都null, 那就找錯了沒有唄, return null

//無法找到target element, 因為不是Binary Search Tree

//[Not Working]：O(n) space O(h) time。把兩條線binary search出來。找第一個不同的parent. 代碼長。 Iterative

130. LRU Cache.java Level: Hard

timeout method, 天真的來了一個O(n) 的解法，結果果然timeout.

一個map<key,value>存數值。一個queue來存排位。

每次有更新，就把最新的放在末尾；每次超過capaticity,就把大頭幹掉。很簡單嘛，但是跑起來太久，失敗了。

於是就來了第二個做法。其實還是跟方法一是類似的。

用了一個特別的雙向的LinkNode，有了head和tail，這樣就大大加快了速度。

主要加快的就是那個『更新排位』的過程，過去我是O(n),現在O(1)就好了。

巧妙點：

head和tail特別巧妙：除掉頭和尾，和加上頭和尾，就都特別快。
用雙向的pointer: pre和next, 當需要除掉任何一個node的時候，只要知道要除掉哪一個，
直接把node.pre和node.next耐心連起來就好了，node就自然而然的斷開不要了。

一旦知道怎麼解決了，就不是很特別，並不是難寫的演算法:

moveToHead()

insertHead()

remove()

131. Majority Number II.java Level: Medium

分三份：a b c考慮。若a, countA++, 或b, countB++，或c，countA--,countB--.

最後出現的兩個count>0的a和b,自然是potentially大於1/3的。其中有一個大於1/3.

比較a和b哪個大，就return哪一個。

132. Majority Number III.java Level: Medium

與其他Majority Number一樣。

出現次數多餘1/k，就要分成k份count occurance.用HashMap。存在的+1；不存在map里的，分情況:

若map.size() == k,說明candidate都滿了，要在map里把所有現存的都-1；若map.size() < k, 說明該加新candidate，那麼map.put(xxx, 1);

最後在HashMap里找出所留下的occurance最大的那個數。

133. Majority Number.java Level: Easy

Majority Number是指超半數。任何超半數，都可以用0和1count：是某個number，+1；不是這個number,-1.

注意：assume valid input, 是一定有一個majority number的。否則此法不成。[1,1,1,2,2,2,3]是個invalid input,結果是3，當然也錯了。

Majority Number II，超1/3, 那麼就分三份處理，countA, countB來計算最多出現的兩個。

Majority Number III, 超1/k, 那麼自然分k份。這裡用到 HashMap。

134. Matrix Zigzag Traversal.java Level: Easy

分析4個step:right, left-bottom,down,right-up

implement時注意index.有點耐心

135. Max Area of Island.java Level: Easy

雖然Easy, 但用到DFS最基本的想法.

dive deep
mark VISITED
sum it up

更要注意, 要從符合條件value==1的地方開始dfs. 對於什麼island都沒有的情況，area應該位0，而不是Integer.MIN_VALUE, 問清楚考官那小伙, 別寫順手。

136. Max Tree.java Level: Hard

Should memorize MaxTree. 依次類推，會做Min-Tree, Expression Tree

Stack里，最大的值在下面。利用此性質，有這樣幾個step:

把所有小於curr node的，全Pop出來, while loop, keep it going.

最後pop出的這個小於Curr的node：它同時也是stack裡面pop出來小於curr的最大的一個，最接近curr大小。（因為這個stack最大值靠下面）

把這個最大的小於curr的node放在curr.left.

那麼，接下去stack裡面的一定是大於curr：

那就變成curr的left parent. set stack.peek().right = curr.

結尾：stack底部一定是最大的那個，也就是max tree的頭。

137. Maximal Square.java Level: Medium

DP問題

從邊長為2的正方形看起，看左上角的那個點。

如何確定是個正方形？首先看左上點是不是1，然後看右邊，右下，下面的點是不是1.

DP就是根據這個特徵想出來。dp[i,j]: 從右下往左上推算，包括當前點在內的所能找到的最大邊長。

注意dp[i,j]被右邊，右下，下面三點的最短點所限制。這就是fn.

Init：

把右邊，下邊兩個邊緣init一遍，存matrix在這兩條邊上的值，代表的意思也就是dp[i][j]在這些點上的初始值:變成為1 or 0.

138. Maximum Average Subarray II.java Level: Review

139. Maximum Depth of Binary Tree.java Level: Easy

DFS: Divide and conquer. 維持一個最大值。

140. Maximum Subarray.java Level: Easy

方法1 比較像DP, 維持一個sums[i]: 從i向前位數, 所有正數的和. 一旦sums[i - 1]<0, 意味著sums[i-1]對maxSum沒有好處, 那麼就assign: sums[i]=nums[i] 這個做法比較中規中矩, makes sense

方法2(better) 想著用一用prefix sum. 把值一個個疊加。然後presum[j] - presum[i- 1] 就是 (i,j)之間的和。

141. Median of two Sorted Arrays.java Level: Hard

Not done

142. Meeting Rooms II.java Level: Medium

方法1:PriorityQueue + 一個Class來解決。Ｏ(nlogn)

方法2:這裡有嘗試了一下用一個sorted Array + HashMap：也還行，但是handle edge的時候,HashMap 要小心，因為相同時間start和end的map key 就會重複了。

143. Meeting Rooms.java Level: Easy

方法1: 找是否有overlap. priorityQueue 按照start time排序好以後, 比較current和peek: current.end > peek.start? 方法2: Scan line, class Point{pos, flag}, PriorityQueue排序。計算count

注意接頭點要考慮所有開會結會的情況，不要恰巧漏掉相接的點。

開會的是超人。瞬間移動接上下一個會議。

144. Merge Intervals.java Level: Easy

方法1：O(nlogn)

掃描線+Count無敵手。注意start end把interval給合起來。

count==0的時候，就是每次start end雙數抵消的時候，就應該是一個interval的開頭/結尾。寫個例子就知道了。

空間：O(2n) -> O(n)

時間,priorityqueue: O(nlogn)

記得怎麼寫comparator

在 LeetCode裡面，Scan line比方法2要快很多.

方法2：

Collections.sort() on interval.start之後，試著跑一遍，按照merge的需求，把需要merge的地方續好，然後減掉多餘的interval就好。

(不知為何LeetCode把Merge Interval, Insert Interval 標為Hard)

Collections.sort(..., new comparator): sort by Interval.start.

畫兩個相連的Interval， prev, curr: prev只有 prev.end覆蓋了 curr.start，才需要merge. 那麼比較一下, marege.

記得如果merge, 一定要list.remove(i), 並且i--，因為改變了List的大小。

若沒有重合，就繼續iteration: prev = curr. move on.

145. Merge k Sorted Arrays.java Level: Medium

由Merge k sorted list啟發。用PriorityQueue,存那k個首發element。

PriorityQueue需要存儲單位。自己建一個Class Node 存val, x,y index.

因為array里沒有 next pointer，只能存x,y來推next element

146. Merge k Sorted Lists.java Level: Medium

用Priorityqueue來排列所有list的leading node.

記得k lists 需要是已經sort好的。

時間：n*O(logk)

PriorityQueue: logk

這個題目可以有好幾個衍生：

比如，如果k很大，一個機器上放不下所有的k list怎麼辦？比如，如果Merge起來的很長，一個機器上放不下怎麼辦？

Note:

不要忘記customized priority需要一個customized new Comparator()
Given list 裡面也可能有null node, 不要忘記查.

147. Merge Sorted Array.java Level: Easy

A夠長，那麼可以從A的尾部開始加新元素。

注意，從尾部，是大數字優先排末尾的.

148. Merge Two Binary Trees.java Level: Easy

基礎binary tree traversal. 注意對null child的判斷

149. Merge Two Sorted Lists.java Level: Easy

小的放前。每次比head大小。

while過後，把沒完的list一口氣接上。

一開始建一個node用來跑路, 每次都存node.next = xxx。存一個dummy。用來return dummy.next.

150. Min Stack.java Level: Easy

雙Stack：一個正常stack，另一個minStack存當下level最小值. 注意維護minStack的變化

另外. 如果要maxStack，也是類似做法

151. Minimum Absolute Difference in BST.java Level: Easy

BST: inorder-traversal: 先left node(adding to stack till left leav), 再process stack.peek (mid node), 再 add rightNode && dive to rightNode.left leaf

152. Minimum Size Subarray Sum.java Level: Medium

2 pointer, O(n). 找subarray, start 或 end pointer，每次一格這樣移動.

好的策略: 先找一個solution, 定住end, 然後移動start; 記錄每個solution if occurs；然後再移動end，往下找。

Note: 雖然一眼看上去是nested loop.但是分析後，發現其實就是按照end pointer移動的Loop。start每次移動一格。總體上，還是O(n)

Note done the O(nlogn) yet

153. Minimum Window Substring.java Level: Hard

LeetCode Hard

LintCode M, 測試有問題，即使做錯也能過.

基本思想: 用個map存target的<char, int frequency>。然後在搜索s的時候，遇到Match， frequency--.

一旦map裡面的frequency都被減為0, 就說明找到candidate.

有好幾個trick：考慮start，前指針怎麼移動；考慮start在candidate首字母沒有多餘前，不能移動；考慮candidate出現的情況...

複習時，回去看別人網站和自己的thoughts

154. MinimumDepthOfBinaryTree.java Level: Easy

Divide and Conquery一個最小值. 注意處理Leaf的null, 用Integer.MAX_VALUE代替，這樣可以避免錯誤counting.

155. Multiply Strings.java Level: Medium

想法不難。turn into int[], 然後每個位子乘積，然後餘數carrier移位。

但是做起來有很多坑。適合面試黑。

數字『123』，在數組裡面， index == 0 是『1』。但是我們平時習慣從最小位數開始乘積，就是末尾的3開始。所以！翻轉兩個數字先！我去。這個是個大坑。
乘積product，和移動Carrier都很普通。
！！最後不能忘了再翻轉。
最後一個看坑。要是乘積是0，就返回『0』。但是這個其實可以在開頭catch到沒必要做到結尾catch。

用到幾個StringBuffer的好東西:

reverse（）；

sb.deleteCharAt(i)

找數字，或者26個字母，都可以：

s.charAt(i) - 0; //數字

s.charAt(i) - a; //字母

156. Next Permutation.java Level: Medium

需斟酌。

Permutation的規律:

從小的數字開始變化因為都是從小的數字開始recursive遍歷。
正因為1的規律，所以找大的斷點數字要從末尾開始：確保swap過後的permutation依然是前綴固定時當下最小的。

steps:

找到最後一個上升點，k
從後往前，找到第一個比k大的點, bigIndex
swap k &&　bigIndex
最後反轉 (k+1，end)

157. Nim Game.java Level: Easy

著名Nim遊戲。寫一些，發現n=4,5,6,7,8...etc之後的情況有規律性: 誰先手拿到4就輸了. 最終很簡單n%4!=0就可以了

158. Number of Airplane in the sky.java Level: Medium

把Interval拆分成數軸上的Point：

起飛mark 1

降落mark -1

用PriorityQueue排序， loop through queue, 計算(起飛+降落)值可能有的max。

注意: 同時起飛和降落，就是 1 - 1 = 0. 所以在while loop裡面有第二個while loop，

當坐標x重合時，在這裡做完所有x點的加減，然後再比較 max。

這避免了錯誤多count，或者少count

159. Number of Islands II.java Level: Hard

用HashMap的Union-find.

把board轉換成1D array，就可以用union-find來判斷了。判斷時，是在四個方向各走一步，判斷是否是同一個Land.

每走一次operator，都會count++. 若發現是同一個island, count--

160. Number of Islands.java Level: Medium

方法1: 兩個for loop brutle force。 DFS把每個跟1相關的都Mark一遍.生成一個island.

方法2: 可以用union-find，就像Number of island II 一樣。只不過這個不Return list, 而只是# of islands

161. One Edit Distance.java Level: Medium

理解Edit: 就是刪除，增加，和替換。

換完之後，理論上換成的String 就應該全等

一旦找到不一樣的char, 就判斷那三種可能性

162. Palindrome Permutation II.java Level: Medium

permutation的綜合題：

validate Input 是不是可以做palindromic permutation. 這個就是（Palindrome Permutation I）
順便存一下permutation string的前半部分和中間的single character(if any)
DFS 做unique permutation: given input有duplicate characters。

163. Palindrome Permutation.java Level: Easy

注意，條件裡面沒說是否全是lower case letter

164. Pascals Triangle II.java Level: Easy

簡單處理array list.

165. Permutation Index.java Level: Easy

和Permutation Sequence相反的題目。思想類似。

題目為Easy，琢磨很久，分析：

每個數位的數字，都是跳過了小於這數字開頭的多種可能。

舉例【6，5，2】吧。我們找6，5，2是permudation裡面的第幾個。

正常排序，也就是permutation的第一個，應該是【2，5，6】

如果要從首位，2，變成6，要跨過多少可能性呢？

很簡單，就是問：小於6的數字有多少個呢？（2，5）.每個數字變成head，都有各自的一套變化，都有(n-1)!種可能。

本題做法：每個（n-1）!加起來。　Note:(n-1) means, 開頭的數字(2,5)各帶出多少種排列，也就是不就是(n-1)!嘛。這一步，計算數量很簡單: (有幾個小於6的數字) ×(除去head剩下有多少個數字)!

以上，都是為了把６推上皇位，而犧牲的條數。

那麼把６推上去以後，還有接下去的呢。

接下去要看５，２.

６確定，後面ｐｅｒｍｕｄａｔｉｏｎ可變的情況有可能是【６，５，２】，那還可能是【６，２，５】呢。

Same process, 看ｇｉｖｅｎ　數組的第二位５，算它接下去：

１.　有幾個數字小於５呢？

２.　除去５，還有幾個數字可以　ｆａｃｔｏｒｉａｌ呢？

３. 一樣的。第一步就結果乘以第二步。

最後接下去要看最後一個元素2了。

6,5,2全看過了以後，加起來。

就是【6，5，2】上位，所踏過的所有小命啊！

我這解釋太生動了。因為耗費了好長時間思考...

166. Permutation Sequence.java Level: Medium

k是permutation的一個數位。而permutation是有規律的。

也就是說，可以根據k的大小來判斷每一個數位的字元（從最大數位開始，因為默認factorio從最大數位開始變化）。

於是先求出n!，然後 k/n!就可以推算出當下這一個數位的字元。然後分別把factorio 和 k減小。

另外, 用一個boolean[] visited來確保每個數字只出現一次。

這個方法比計算出每個permutation要efficient許多。

167. Permutations II.java Level: Medium

方法1: Mark visited. 並且要檢查上一層recursive時有沒有略過重複element. 並且要排序，通過permutation規律查看是否排出了重複結果。

背景1:在recursive call裡面有for loop, 每次從i=0開始, 試著在當下list上加上nums裡面的每一個。

從i=0開始，所以會依次recursive每一個nums：因此，例如i=2,肯定比i=3先被訪問。也就是:取i=2的那個list permutation肯定先排出來。

背景2:重複的例子：給出Input[x, y1, y2], 假設y的值是一樣的。那麼，{x,y1,y2}和{x,y2,y1}是相同結果。

綜上，y1肯定比y2先被訪問,{x,y1,y2}先出。緊隨其後，在另一個recursive循環里，{x,y2...}y2被先訪問，跳過了y1。

重點:規律在此，如果跳過y1，也就是visited[y1] == false, 而num[y2] == num[y1]，那麼這就是一個重複的結果，沒必要做，越過。

結果:那麼，我們需要input像{x,y1,y2}這樣數值放一起，那麼必須排序。

方法2: 一個辦法就是給一個visited queue。和queue在所有的地方一同populate. 然後visited裡面存得時visited indexes。 (Not efficient code. check again)

168. Permutations.java Level: Medium

Recursive Backtracking: 取，或者不取. Improvement: maintain list (add/remove elements) instead of list.contains

Iterative: 用個queue，每次poll()出來的list, 把在nums裡面能加的挨個加一遍。 However, code is a bit massive.

169. Populating Next Right Pointers in Each Node II.java Level: Hard

非perfect tree, 也就是有random的null children. DFS＋BFS

Populating Next Right Pointers in Each Node I 裡面依賴parent.next.left來作鏈接，但現在這個parent.next.left很可能也是Null.

於是需要移動parent去找children level的next node。
並且每次在一個level, 要用BFS的思想把所有parent 過一遍，也就是把parent 正下方的children全部用.next鏈接起來
原因: 到下一層children變成parent, 他們需要彼此之間的connection, grand children才可以相互連接。

Note: runtime O(n * 2^log(n) ) = O(n^2), not good.

170. Populating Next Right Pointers in Each Node.java Level: Medium

方法1：

題目要求DFS。

其實basic implementation. 每次處理node.left.next = node.right; node.right.next = node.next.left;

方法2:

不和題意，用了queue space，與Input成正比。太大。

BFS over Tree。用Queue 和 queue.size()，老規矩。

process每層queue時, 注意把next pointer加上去就好.

171. QuickSort.java Level: Easy

代碼是不難的.

首先partition. 返還一個partition的那個中間點的位置。然後劈開兩半。前後各自 quick sort, recursively

注意：在partition裡面, 比較的時候nums[start] < pivot, nums[end]>pivot, 如果寫成了 <= 會 stack overflow.

但是：在partition array那個題目裡面，第二個 nums[end] >= pivot, 是要去加上這個『=』的

172. Rehashing.java Level: Medium

173. Remove Duplicates from Sorted Array.java Level: Easy

Remove Duplicate from Array 不同於remove from linked list.

LinkedList裡面我們是最好不要動node.val的，直接把node去掉。而array我們很難直接把node去掉，又不能用新array，那麼就要：

把不重複的element一個個放到最前面。

這個思想跟merge two sorted array （其中一個後續非常長的array可以放下arr1,arr2）類似。就是找個不會事後mess up，不會去動得index,把滿足條件的element 填進去。這樣保證了in place.

有個反向思維：remove duplicate,實際上也是找unique elements, and insert into original array

174. Remove Duplicates from Sorted List.java Level: Easy

一旦node.next 和node是重複，跳

175. Remove Node in Binary Search Tree.java Level: Hard

方法1: Brutle一點。找到target和target的parent.

把target remove時，把target的children nodes 重新排列組成新的BST: inorder traversal, build tree based on inorder traversal list.

方法2: 分析規律,先找到target和parent, 然後根據性質，把target remove時，移動children nodes, 保證還是BST。

176. Reshape the Matrix.java Level: Easy

讀例子理解題意. 理清counter case. Basic implementation

177. Reverse Integer.java Level: Easy

方法1: 轉換成String 然後 reverse 方法2: 每次加上x%10，然後x不斷減小～0

178. Reverse Linked List.java Level: Easy

建立新list。每次把newList append 在current node的後面。

用head來循環所有node。

179. Reverse String.java Level: Easy

Similar to Reverse Integer. 可以用StringBuffer, 也可以two pointer reverse head/tail

180. Reverse Words in a String II.java Level: Medium

In-place reverse.

reverse用兩回. 全局reverse。局部:遇到空格reverse。

注意：結尾點即使沒有也要給reverse一下最後一個詞。

181. Reverse Words in a String.java Level: Medium

幾種不同的方法flip：

坑： 1. 結尾不能有空格。 2. 注意，如果Input是『』的話，split以後就啥也沒有了。check split以後 length == 0

另個題目Reverse Words in String (char[]) 可以in-place，因為條件說char[]裡面是沒有首尾空格,好做許多喲.

182. reverseInteger.java Level: Easy

183. Roman to Integer.java Level: Easy

熟悉羅馬字母規則

I V X L C D M 分別代表的數字
列舉combo的情況，需要從原sum裡面減掉多加的部分： IV, IX減2, XL, XC減20, CD, CM減200.

https://en.wikipedia.org/wiki/Roman_numerals

184. Rotate Image.java Level: Medium

找到個轉角度的規律公式。用一個temp。in place.

185. Search Range in Binary Search Tree .java Level: Medium

等於遍歷了所有k1<= x <= k2的x node。

如果是用Binary Search Tree搜索，那麼一般是if (...) else {...}，也就是一條路走到底，直到找到target.

這裡, 把 left/right/match的情況全部cover了，然後把k1,k2的邊框限制好，中間就全部遍歷了。

186. Search Rotated in Sorted Array.java Level: Hard

方法1：O(logn) 還是把它先當做正常的sorted list開始搜。

但是在比較的時候，多比較一個A[start] < A[mid]?

在1 和 2 裡面分別討論 target 的位置

1. A[start] < A[mid] ?

說明在前半段

- start<target<mid

- target > mid

2. A[start] > A[mid]

說明 start 還在前半段，而mid在後半段

- mid < target < end

- target < mid

方法2：O(logn)

1. binay search break point

2. binary search target

注意等號，在判斷target在前半段還是後半段：if (A[p1] <= target && target <= A[breakPoint])

187. Segment Tree Build II.java Level: Medium

給的是Array。注意找區間內的max, assign給區間。其餘和普通的segment tree build一樣

給了array,但是並不根據array里的內容排位，而是依然根據index in [0, array.length - 1]割開區間，break到底，

最終start==end。同時assign max=A[start] or A[end]

往上,parent一層的max:就是比較左右孩子,其實都是在兩個sub-tree裡面比較sub-tree的max。

這就好做了：

先分，找到left/right，比較max,在create current node,再append到當前node上面。

實際上是depth-first, 自底向上建立起的。

188. Segment Tree Build.java Level: Medium

按定義：

左孩子：（A.left, (A.left+A.rigth)/2）

右孩子：（(A.left+A.rigth)/2＋1， A.right）

189. Segment Tree Modify.java Level: Medium

Recursively 在segment tree裡面找index, update it with value.

每個iteration，很可能（要麼左手，要麼右手）max就變了。所以每次都left.max and right.max compare一下。

最後輪迴到頭頂，頭頂一下包括頭頂，就全部都是max了。

Divde and Conquer

190. Segment Tree Query II.java Level: Medium

和 Segment Tree Query I 以及其他Segment Tree問題沒啥區別。這個就是return個count。

這個題目考了validate input source：input 的start,end可能超出root[start,end]。

那麼第一步就要先clear一下。完全不在range就return 0. 有range重合就規整到root的range.

191. Segment Tree Query.java Level: Medium

給了segment Tree, node裡面有Max value, 找[start,end]裡面的max

[start,end]跟mid相比，可能：

全在mid左

全在mid右

包含了mid：這裡要特別break into 2 query method

按定義：

mid = (root.start + root.end)/2

192. Shortest Word Distance.java Level: Easy

找short distance, wordB可以在wordA的前後；而同一時間，只需要計算一個最近的up to date的distance。 greedy不斷變更A/B index再做比較即可。

193. Single Number.java Level: Easy

Bit XOR: 當兩個bit不同時，return 1. 題目正要消光所有重複出現的數兒留下出現一次的那個.

194. Sqrt(x).java Level: Easy

理解題意, 從[0, x]找一個可以m*m=x的值. 注意, 如果找不到, 最後問考官該return一個什麼值：按道理，因為return int, 會取整，那麼return一個平方最close to x就可以. 注意 mid 用 long, 因為很可能超過最大int.

195. String Permutation.java Level: Easy

把#of occurrences 存進HashMap, 第一個string 做加法，第二個string做減法。最後看是否有不等於0的作判斷。

196. String to Integer(atoi).java Level: Easy

方法1: 問清情況，一點一點把case都涉及到。

方法2: 用regular expression。if (!str.matches("[+-]?(?:d+(?:.d*)?|.d+)")). 猛了一點

197. Strobogrammatic Number II.java Level: Medium

耗了一點時間。本以為需要DP一下，把做過的n存一下。後來發現，其實就是剝皮，一層一層，是一個central-depth-first的，鑽到底時候，return n=1,或者n=2的case，然後開始backtracking。難的case先不handle.到底之後來一次O(n) scan. 總共的時間起碼是O(n/2) + O(n), 所以還是O(n)

198. Strobogrammatic Number.java Level: Easy

根據題意枚舉, 再根據規則basic implementation

199. Subarray Sum Closest.java Level: Medium

200. Subarray Sum.java Level: Easy

分析出，如果sum[0a]=x, 然後sum[0b]=x, 說明sum(a ~ b] = 0.

這樣理解後，用hashMap存每個sum[0~i]的值和index i. 如果有重複，就找到了一組sum為0的數組。

201. Subset.java Level: Medium

最基本的遞歸題目。

坑：記得一開頭sort一下 nums。因為要升序。那麼整體就是O(nlogn)

注意：用level/index來track到哪一步。最後一level就add into rst

方法1: subset的概念，取或者不取,backtracking. 當level/index到底，return 一個list.

方法2: 用for loop backtracking. 記得：每個dfs recursive call是一種獨特可能，先加進rst。

recap:時間久了忘記dfs的兩種路子. for loop dfs/backtracking vs. regular dfs

202. Subsets II.java Level: Medium

遞歸：找准需要pass along的幾個數據結構。

和SubsetI類似，先sort input, 然後遞歸。但是input可能有duplicates.

Using for loop approach: 每個dfs call是一種可能性，直接add into result.

為了除去duplicated result, 如果在遞歸裡面用rst.contains(),就是O(n), which makes overall O(n^2).

這裡有個基於sorted array的技巧：

因為我們有mark index。一旦for loop裡面的i!=index，並且nums[i] == nums[i-1],說明x=nums[i-1]已經用過，不需要再用一次：

[a,x1,x2]，x1==x2

i == index -> [a,x1]

i == index + 1 -> [a,x2]. 我們要skip這一種。

如果需要[a,x1,x2]怎麼辦？其實這一種在index變化時，會在不同的兩個dfs call 裡面涉及到。

Iterative: 寫一寫，用個Queue. Not recommended, Again, rst.contains() cost too much.

203. Subtree.java Level: Easy

找到potential subtree, 比較Children.

一點注意：即使找到T1 == T2, 但很可能只是數字相同（這裡不是binary search tree!!），而children不同。所以同時要繼續recursively isSubtree(T1.left, T2) ...etc.

204. Symmetric Binary Tree.java Level: Easy

Symmetric Tree

注意Symmetric Binary Tree的例子和定義: 是鏡面一樣的對稱. 並不是說左右兩個sub-tree相等。

方法1: Recursively check symmetrically相對應的Node. 每個node的children都和鏡面另外一邊相對的node的children剛好成鏡面反射位置。

方法2: 用stack. 左手邊sub-tree先加left,再加right child; 右手邊sub-tree先加right child, 再加left child。

process時，若symmetric，所有stack裡面出來的node會一一對應。

205. Top K Frequent Elements.java Level: Medium

題目有提醒: 不能用O(nLog(n)) 也就是說明要Log(n): 首先想到就是PriorityQueue, 並且不能queue.offer on the fly. 那麼就先count, O(n); 再priorityQueue, Log(k), k是unique 數字的總量.

206. Top K Frequent Words.java Level: Medium

方法1：Brutle force用HashMap存frequency, 用ArrayList存lists of words。最後返回從尾部向前數的k個。

注意排序時Collection.sort()的cost是O(nLogk)

方法1-1: 還是用HashMap,但create一個Node class, 然後用PriorityQueue.

PriorityQueue裡面用到了 String.compareTo(another String).巧妙。

方法2: Trie && MinHeap屌炸天

http://www.geeksforgeeks.org/find-the-k-most-frequent-words-from-a-file/

207. Topological Sorting.java Level: Medium

比較特別的BFS.

幾個graph的condition：

可能有多個root
directed node, 可以direct backwards.

Steps:

Track all neighbors/childrens. 把所有的children都存在map<label, count>裡面先把所有的root加一遍，可能多個root。並且全部加到queue裡面。

然後以process queue, do BFS:

Only when map.get(label) == 0, add into queue && rst.

這用map track apperance, 確保在後面出現的node, 一定最後process.

208. Trapping Rain Water II.java Level: Hard

用PriorityQueue把選中的height排序。為走位，create class Cell {x,y, height}.

注意幾個理論：

從matrix四周開始考慮，發現matrix能Hold住的水，取決於height低的block。
必須從外圍開始考慮，因為水是被包裹在裡面，外面至少需要現有一層。

以上兩點就促使我們用min-heap: 也就是natural order的PriorityQueue.

process的時候，畫個圖也可以搞清楚，就是四個方向都走走，用curr cell的高度減去周圍cell的高度。若大於零，那麼就有積水。

每個visited的cell都要mark. 去到4個方向的cell,加進queue裡面繼續process.

這裡，有一點，和trapping water I 想法一樣。剛剛從外圍，只是能加到跟外圍cell高度一致的水平面。往裡面，很可能cell高度變化。

這裡要附上curr cell 和 move-to cell的最大高度。

209. Tweaked Identical Binary Tree.java Level: Easy

Recursive 比對左左,左右,右左，右右

210. Two Strings Are Anagrams.java Level: Easy

方法1:char ascii 用count[256]

坑：不要想像這個是個26letter lowercase. may not be true.

方法2: 若是其他字元encoding, 而不只是utf16-encoding (java char)?

那麼就繼續用string去做

211. Ugly Number.java Level: Medium

方法1: PriorityQueue排序。用ArrayList check 新的ugly Number是否出現過。

方法1-1：(解釋不通，不可取)用PriorityQueue排序。神奇的3，5，7走位：按照題目答案的出發，定了3，5，7以什麼規律出現。但是題目並沒有特殊表明。

方法2: DP . Not Done yet.

212. Valid Anagram.java Level: Easy

HashMap

213. Valid Palindrome.java Level: Easy

tutorial:https://www.youtube.com/watch?v=2hNK0Yz53LQ&list=PLZn-UvluQZuNedn1hDzTmNLE8MQWXjKVb

過濾alphanumeric，其他字母掠過

214. Valid Parentheses.java Level: Easy

剝皮過程。解鈴還須繫鈴人

左邊的外皮{[在stack底部

右邊的外皮應該和stack頂上的左外皮一一對應

215. Valid Sudoku.java Level: Easy

用HashSet存visited value.

方法1: 在nest for loop裡面validate row,col,and block.

validate block要利用i 和 j 增長的規律。

說白了，i && j是按照0~n增長的index, 具體怎麼用是可以flexible的。這個方法在同一個nest for loop解決所有運算。

方法2: 單獨做block validation: validate block的時候雖然看到了4層for.其實也就是n^2.

216. Validate Binary Search Tree.java Level: Medium

查看每個parent-child關係。同時把root level上面傳下來max,min界限定住。

217. Word Break II.java Level: Hard

兩個DP一起用.解決了timeout的問題

isWord[i][j], subString(i,j)是否存在dict中？
用isWord加快 isValid[i]: [i ～ end]是否可以從dict中找到合理的解？
從末尾開始查看i：因為我們需要測試isWord[i][j]時候，j>i, 而我們觀察的是[i,j]這區間；
j>i的部分同樣需要考慮，我們還需要知道isValid[0～j+1]。所以isValid[x]這次是表示[x, end]是否valid的DP。
i 從末尾到0, 可能是因為考慮到isWord[i][j]都是在[0~n]之內，所以倒過來數，坐標比較容易搞清楚。
(回頭看Word Break I，也有坐標反轉的做法)
dfs 利用 isValid 和isWord做普通的DFS。

Note: 在Word Break裡面用了set.contains(...), 在isValid裡面，i 從0開始。但是，contains()本身是O(n).

在這道題裡面應該是因為word dictionary太大，加上nest for, 變成O(n^3)所以timeout.

istead,用一個isWord[i][j]，就O(1)判斷了i~j是不是存在dictionary裡面。

218. Word Break.java Level: Medium

方法1:（attempt3 code） state,rst[i]: 從[0～i] inclusive的string是否可以在dict中break開來找到？

function: rst[i] = true if (rst[i - j] && set.contains(s.substring(i - j, i))); j in[0~i]

rst[i - j] 記錄的是[0, i-j]這一段是否可以break後在dict找到。
若true，再加上剩下所有[i-j, i]都能在dict找到，那麼rst[i] = rst[0, i - j] && rst[i-j, i] == true

優化：找dict裡面最長string, 限制j的增大。

(attempt4 code)

與Word BreakII用同樣的DP。 valid[i]: 記錄從i到valid array末尾是否valid.

219. Word Ladder II.java Level: Hard

220. Word Ladder.java Level: Medium

BFS Brutle: 在start string基礎上，string的每個字母都遍歷所有26個字母，換換。

方法2:

用Trie。理應更快. However implementation可能有點重複計算的地方，LeetCode timeout. 需要再做做。

221. Word Pattern.java Level: Easy

每個char代表一個pattern。用HashMap<char, str>. 但不夠，如果a也match dog, b也match dog, 糾錯了。比如pattern = "abba", str = "dog dog dog dog"。因此第二個HashMap<str, char> 反過來。確保pattern和str一一對應。

222. Word Search II.java Level: Hard

Big improvement: use boolean visited on TrieNode!

不要用rst.contains(...), 因為這個是O(n) 在leetcode還是會timeout（lintcode竟然可以pass）!

在Trie search() method 裡面，凡是visit過的，mark一下。

Regular:

for loop on words: inside, do board DFS based on each word.

Time cpmplexity: word[].length * boardWidth * boardHeight * (4^wordMaxLength)

Build Trie with target words: insert, search, startWith.

依然要對board matrix做DFS。

no for loop on words. 直接對board DFS:

每一層,都會有個up-to-this-point的string. 在Trie裡面check它是不是存在。以此判斷。

若不存在，就不必繼續DFS下去了。

Trie solution time complexity, much better:

build Trie: n * wordMaxLength search: boardWidth * boardHeight * (4^wordMaxLength + wordMaxLength[Trie Search])

223. Word Search.java Level: Medium

Backtracking: 比較 Brutle。找到開頭的字母，然後投入一個recursive找字母的工程：每到一個字母，朝四個方向走。他們之中，有一個true就可以。

Note:每次到一個字母，mark一下#. 4個path recurse回來後，mark it back.

Backtracking方法2:

用一個boolean visited[][]

224. Find Anagram Mappings.java Level: Easy

比較簡單, 用HashMap 存index list. 最後再遍歷一遍數組A, 列舉出所有元素. O(n)

225. Judge Route Circle.java Level: Easy

簡單的character checking. 各個方向, 加加減減.

226. Island Perimeter.java Level: Easy

最簡單的方法: 每個格子4個牆;每個shared的牆要-2 (牆是兩面, -1 * 2) 最後合計結果就好.

不必想太多用HashMap做.但是也可以思考一下:

把每個block相連的block全部存在以當下block為key的list裡面. 那麼這裡需要把2D坐標, 轉化成一個index.
最後得到的map, 所有的key-value應該都有value-key的反向mapping, 那麼久可以消除乾淨, 每一次消除就是一個shared wall.
一點點optimization: DFS去找所有的island, 如果island的圖非常大, 而island本身不打,那麼適合optimize. 但是整體代碼過於複雜. 不建議寫.

227. First Unique Character in a String.java Level: Easy

方法1: 按照題意, 找到第一個 first index == last index的字母.

方法2: 用hashmap存字母的index, 有些重複字母的index就會是個list. 找到單一index, 結合成list, sort, return list.get(0)

228. Power of Three.java Level: Easy

方法1: Power of 3: 3 ^ x == n ? 意思是 n / 3 一直除, 最後是可以等於1的, 那麼就有了 n/=3, check n%3, 最後看結果是不是整除到1的做法. 用while loop.

方法2: 如果n是power of 3, 那麼 3 ^ x的這個 x一定是個比n小的數字. 那麼可以在 0 ~ n 之間做binary serach, 但是就比較慢.

方法3: 巧妙的想法.最大的3^x integer是 3^19. 那麼找到這個數, 一定可以被n整除. 一步到位.

229. Plus One.java Level: Easy

簡單的實現, 加1, 進位. 唯一取巧的地方, 最後如果要多一位, 一定是10000...這個模式, 可以走捷徑, 直接來個+1size的array, 然後第一位=1. 注意,轉換成long也不合理,用太多memory.

230. Power of Two.java Level: Easy

跟powerOfThree一樣: 可以loop, check mod; 也可以用binary search找合適的數字.

231. Reverse Vowels of a String.java Level: Easy

方法1: two pointer. 前後兩個指針, 在while loop裡面跑. 注意 i<j, 一旦相遇, 就break. 找到合適的, 就做swap. StringBuffer可以 sb.setCharAt()記得用.

方法2: 拿出所有vowels, 反過來放進去. O(n)

232. Guess Number Higher or Lower.java Level: Easy

binary search 公式

233. Encode and Decode TinyURL.java Level: Medium

其實想到了切入點, 是個可難可簡單的題目. 這裡的encode就是想辦法把url存起來, 然後給個 key. 那麼具體怎麼做這個key, 簡單就可以用一個map, 然後counting. 複雜一點就可以做random letter/number組成key.

234. Wiggle Sort.java Level: Medium

方法1: 排序, nLog(n). 然後把直線上坡變成層疊山峰, 需要每隔幾個(題目中是每隔2位)就做個swap 造成高低不平. Note: 每隔山峰之間是相互沒有關係的, 所以每次只要操心 [i], [i-1]兩個位置就好了.

方法2: O(n) 看好奇數偶數位的規律, 然後根據題目給出的規律, 跑一遍, 每次只關注兩個位置: 把不合適的[i], [i-1]調換位置就好了.

方法3: 跟法2一樣, 只是更巧妙一點罷了: 第一遍想太多. 其實做一個fall-through就能把問題解決，原因是因為：這樣的fall-through每次在乎兩個element，可以一口氣搞定，無關乎再之前的elements。特別的一點：flag來巧妙的掌控山峰和低谷的變化。又是神奇的一幕啊！這樣子的奇觀，見過就要知道了，沒見過的時候有點摸不著頭腦。

235. Queue Reconstruction by Height.java Level: Medium

別無他法, 只能寫一遍例子, 找規律,然後greedy. 需要寫一遍發現的規律比如: 從h大的開始排列, 先放入k小的. 寫comparator的時候要注意正確性. 如果要sort, 並且靈活insert:用arrayList. 自己做一個object. 最後做那個matchCount的地方要思路清晰, 找到最正確的spot, 然後greedy insert.

O(n) space, O(nLog(n)) time, because of sorting.

可能有簡化的餘地, 代碼有點太長. 比如試一試不用額外空間?

236. 2 Sum.java Level: Easy Link 解法1：相對暴力簡潔, HashMap<value, index>，找到一個value, 存一個; 若在HashMap裡面 match 到結果, 就return HashMap里存的index. O(n) space && time.

解法2：Sort array, two pointer 前後++,--搜索。Sort 用時O(nlogn).

第一步 two pointer 找 value.
注意，要利用額外的空間保留original array，用來時候找index. (此處不能用HashMap，因為以value 為key，但value可能重複)
O(n) space, O(nlogn) time.

237. 2 Sum II - Input array is sorted.java Level: Medium

排序好的array. Two pointer移動start和end，核查sum. 注意sum用long.

238. 2 Sum II.java Level: Medium

LintCode的題. 注意找的是greater/bigger than target。

由於給定條件允許O(nLogn):

sort two pointer

while裡面two pointer移動。每次如果num[left]+num[right] > target，那麼其中所有num[left++]的加上num[right]都>target.

也就是,num[right]不動，計算加入挪動left能有多少組，那就是: right-left這麼多。全部加到count上去。

然後right--.換個right去和前面的left部分作比較。

239. Coin Change.java Level: Medium

DP. 找對方程f[x], 積累到amount x最少用多少個coin: #coin是value, index是 [0~x]. 子問題的關係是: 如果用了一個coin, 那麼就應該是f[x - coinValue]那個位置的#coins + 1

注意initialization: 處理邊界, 一開始0index的時候, 用value0. 中間利用Integer.MAX_VALUE來作比較, initialize dp[x] 注意, 一旦 Integer.MAX_VALUE + 1 就會變成負數. 這種情況會在coin=0的時候發生.

方法1: 用Integer.MAX_VALUE 方法2: 用-1, 稍微簡潔一點, 每次比較dp[i]和 dp[i - coin] + 1, 然後save. 不必要做多次min比較.

240. Unique Path.java Level: Medium

可以DP.計數DP. 注意方程式前兩位置加在一起: 前兩種情況沒有overlap, 也不會缺情況. 注意initialization, 歸1. 需要initialize的原因是,也是一個reminder: 在方程中會出現-1index

241. Jump Game.java Level: Medium

給出步數，看能不能reach to end.

Status: DP[i]: 在i點記錄，i點之前的步數是否可以走到i點？ True of false. 其實j in [0~i)中間只需要一個能到達i 就好了 Function: DP[i] = DP[j] && (j + A[j]) ?= i, for all j in [0 ~ i) Return: DP[dp.length - 1];

242. Maximum Product Subarray.java Level: Medium

求最值, DP. 兩個特別處:

正負數情況, 需要用兩個DP array.
continuous prodct 這個條件決定了在Math.min, Math.max的時候, 是跟nums[x]當下值比較的, 如果當下值更適合, 會捨去之前的continous product, 然後重新開始. 這也就註定了需要一個global variable 來hold result.

243. 3 Sum Closest.java Level: Medium

3Sum 的一種簡單形式, 並且都沒有找index, value, 而只是找個sum罷了.

double for loop。 2Sum只能用土辦法 left/right 2 pointers。 O(n^2)

注意：check closest時候用long, 以免int不夠用

244. Triangle Count.java Level: Medium

其實也就是3sum的變形, 或者而說2sum的變形. 主要用2 pointers來做. 注意, 在選index時候每次定好一個 [0 ~ i], 在這裡面找點start, end, 然後i 來組成triangle. Note巧妙點: 在此之中, 如果一種start/end/i 符合, 那麼從這個[start~end]中, 大於start的都可以, 所以我們count+= end-start. 反而言之, <end的其他index, 就不一定能符合nums[start] + nums[end] > nums[i]

245. 3 Sum.java Level: Medium

方法1: sort array, for loop + two pointer. O(n) 處理duplicate wthin triplets: 如果最外圈的移動點i重複, 一直順到結尾的最後一個再用. 如果是triplet內有重複, 用完start point, 移動到結尾.

Previous notes: 注意:

找 value triplets, 多個結果。注意，並非找index。
要升序, 第一層for loop 從最後一個元素挑起, 保證了順序。
去掉duplicate: check用過的同樣的數字，都跳掉。不需要用同樣的數字再計算一邊已有結果。

步驟:

For loop 挑個數字A.
2Sum 出一堆2個數字的結果
Cross match 步驟1裡面的A.

時間 O(n^2), 兩個nested loop

另外, 還是可以用HashMap來做2Sum。稍微短點。還是要注意handle duplicates.

246. 4 Sum.java Level: Medium

方法1：

利用2Sum的原理，把4Sum分為連個2Sum。左一個pair,右一個pair，每個pair裡面放2個數字。
以一個點，i，作為分界口，也要列舉出所有i之前的pair,作為基礎。
再嘗試從所有i+1後面,找合適的2nd pair。

可以用HashSet, 可以直接比較list裡面每一個元素, 保證set不重複. Previous Notes: 在造class Pair時候，要做@override的function: hashCode(), equals(Object d). 平時不太想得起來用。參見 http://lifexplorer.me/leetcode-3sum-4sum-and-k-sum/

方法2： 3Sum外面再加一層. 參考3Sum. 時間O(n^3)。但此方法在k-sum時候，無疑過於費時間. O(n^k)

247. k Sum.java Level: Hard

DP. 公式如何想到, 還需要重新理解.

dp[i][j][m]: # of possibilities such that from j elements, pick m elements and sum up to i. i: [0~target]

dp[i][j][m] = dp[i][j-1][m] + dp[i - A[j - 1]][j-1][m-1] (i not included) (i included)

248. Trapping Rain Water.java Level: Hard

方法1: 主要想法和方法2一致: 在山坡下坡的基礎上, 一直用stack堆積bottom. 最後遇到上升之前, 此時bottom可以用來跟stack之前堆積的所有下坡index做比較, 算跟他們高度相差的積水. 用了stack記錄下坡, 然後用個while loop一挖到底的想法非常棒.

方法2: 2 Pointers，雙面夾擊：

找中間最高bar的index
兩面往中心掃：每次加上（topBarIndex - currIndex）* (elevation from previous index).也就是每次加一個橫條。
每次還要減去block自身的height。

249. Longest Continuous Increasing Subsequence.java Level: Easy

簡單的DP:dp[i]存在i點時連續上升#. dp[i]時可能為0, 一旦斷開.

方法1: dp[i], maintain max 方法2: 用一個數存current count, maintain max. 也是DP, 稍微簡化.

250. Longest Increasing Subsequence.java Level: Medium

方法1: [0 ~ i], 0<i<n: 以i為結尾, 每個不同的i會得出的max-length. 所以每個結尾i都要被考慮一遍. dp[i]: represent the max length aggregated up to index i.

Previous Note: i位和之前的0i-1 都遠關係。複雜一點。每次都考慮oi的所有情況。所以double for loop

方法2: O(n log n)? 還沒有做. 是否for loop裡面用binary search?

251. Unique Binary Search Tree.java Level: Medium

Not quite clear. 根據左右分割而總結出了原理, 每次分割, 左右兩邊都會有一定數量的permutation, 總體上的情況數量當然是相乘. 然後每一個不同的分割點都加一遍: f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-2)*f(1) + f(n-1)*f(0)

然後把數學公式轉換成DP的方程, 有點玄學的意思啊! 不好想.

252. Trim a Binary Search Tree.java Level: Easy

方法1: 適合複習BST. 用DFS對待每個node. 注意BST的特徵: 所有left nodes都小於當下node, 所有right nodes都大於當下node.

根據題意用[L,R]切割.如果node.val<L, 直接連node帶左邊全丟掉, return node.right. 處理R也是一樣. 分制是, DFS leftNode, rightNode. 然後接在node.left, node.right.

方法2: 用迭代, 還沒有寫.

253. Unique Paths II.java Level: Medium

典型的坐標型DP. 考慮最終結尾需要的狀態:如何組成,寫出公式. 公式中注意處理能跳掉的block, 到不了, 即為 0 path.

254. Counting Bits.java Level: Medium

Bit題目用num的數值本身表示DP的狀態. 這裡, dp[i] 並不是和 dp[i-1]有邏輯關係; 而是dp[i] 和dp[i>>1], 從binary representation看出有直接關係.

255. Bomb Enemy.java Level: Medium

分方向考慮的方法很容易想到,但是四個方向移動的代碼比較繁瑣. 往上炸: 要從頂向下考慮往下炸: 要從下向上考慮

熟練寫2D array index 的變換.

256. Paint House.java Level: Easy

考慮DP最後一個位置的情況. 發現給出了一些特殊條件, 需要附帶在DP[i-1]上, 那麼就定義二維數組

257. Decode Ways.java Level: Review

確定末尾的2種狀態: single letter or combos. 然後計算出單個letter的情況, 和雙數的情況 note: calculate number from characters, need to - 0 to get the correct integer mapping. 注意: check value != 0, 因為0 不在條件之中(A-Z)

258. House Robber.java Level: Easy

最基本的dp。

看最後結尾狀態的前一個或前兩個的情況，再綜合考慮當下的。

思考的適合搞清楚當下的和之前的情況的關係。

滾動數組的優化，就是確定了是這類「只和前一兩個位子「相關的Fn而推出的。

259. House Robber II.java Level: Medium

和House Robber I 類似, DP. 根據dp[i-1]是否被rob來討論dp[i]: dp[i] = Math.max(dp[i-1], dp[i - 2] + nums[i - 1]);

特別的是，末尾的last house 和 first house相連。這裡就需要分別討論兩種情況:

第一個房子被rob
第一個房子沒被rob

分出兩個branch, 可以看做兩種狀態. 可以考慮用兩個DP array, 也可以加一維度, 補充這個狀態.

260. Best Time to Buy and Sell Stock I.java Level: Easy

理解意思是關鍵: 每天都就交易價格，n天只讓買賣一次，那就找個最低價買進，找個最高價賣出。記錄每天最小值Min是多少。O(n) 每天都算和當下的Min買賣，profit最大多少.

這裡就可以DP, memorize the min[i]: the minimum among [0 ~ i]; 然後用當天的price做減法算max. 更進一步, 用一個min來表示min[i], 因為計算中只需要當下的min.

Brutle: 每天都試著買進，然後之後的每一天嘗試賣出. double for loop, O(n^2). timeout. 其中很多都是沒必要的計算：[7, 1, 5, 3, 6, 4]。 if we know buyin with 1 is cheapest, we dont need to buyin at 5, 3, 6, 4 later on; well only sell on higher prices.

261. Best Time to Buy and Sell Stock II.java Level: Easy

這道題有幾種其他不同的思路:

Greedy, 每次有相鄰的diff符合profit條件, 就賣了, 最後把所有的diff加在一起. 計算delta, 其實簡單粗暴, 也還不錯.
如下, 從低谷找peek, sell.
繁瑣一點的DP. BuyOn[], SellOn[] 從末尾看起
DFS計算所有(timeout).Improvement on DFS -> DP -> calculate sellOn[i] and buyOn[i], and then return buyOn[i]. 有點難想, 但是代碼簡單, 也是O(n)

找漲幅最大的區間，買賣：找到低谷，買進:peek = start + 1 時候，就是每次往前走一步;若沒有上漲趨勢，繼續往低谷前進。漲到峰頂，賣出:一旦有上漲趨勢，進一個while loop，漲到底, 再加個profit.

profit += prices[peek - 1] - prices[start]; 挺特別的。當沒有上漲趨勢時候，peek-1也就是start, 所以這裡剛好profit += 0.

O(n)

262. Best Time to Buy and Sell Stock III .java Level: Hard

比stock II 多了一個限制：只有2次賣出機會。

方法1: DP加狀態: 只賣2次, 把買賣分割成5個狀態模塊. 在模塊index 0, 2, 4: 沒有持有股票. 1. 一直在此狀態, max profit不變; 2. 剛賣掉, dp[i][前狀態] + profit 在模塊index 1, 3: 持有股票. 1. 一直在此狀態, daily profit. 2. 剛剛買進, 狀態改變, 但是沒有profit yet: dp[i][前狀態]

注意: 把每天的partial profit (diff)加在一起, 最終的overall profit是一樣的. 唯一更好的是, 不需要記錄中間買入的時間點.

方法2: 也就是：找峰頭；然後往下再找一個峰頭。

怎麼樣在才能Optimize兩次巔峰呢？

從兩邊同時開始找Max！（棒棒的想法）

leftProfit是從左往右，每個i點上的最大Profit。 rightProfit是從i點開始到結尾，每個點上的最大profit. 那麼在i點上，就是leftProfit，和右邊rightProfit的分割點。在i點，leftProfit+rightProfit相加，找最大值。

三個O(n),還是O(n)

263. Best Time to Buy and Sell Stock IV.java Level: Hard

方法1: DP. 根據StockIII, 不難發現StockIV就是把狀態劃分為2k+1份. 那麼同樣的代碼, 移植. 注意1: 如果k很大, k>n/2, 那麼長度為n的數組裡面, 最多也只能n/2個transaction, 那麼題目簡化為stockII, 給n數組, 無限次transaction. 注意2: n可以用滾動數組(prev/now)代替. 注意3: 最後狀態是沒有stock的都該考慮, 做一個 for 循環比較max. 當然, 來一個profit variable, 不斷比較, 也是可以的.

方法2: 記得要理解：為什麼 i-1天的賣了又買，可以和第 i 天的賣合成一次交易？

因為每天交易的price是定的。所以賣了又買，等於沒賣！這就是可以合併的原因。要對價格敏感啊少年。

Inspired from here:

http://liangjiabin.com/blog/2015/04/leetcode-best-time-to-buy-and-sell-stock.html

局部最優解 vs. 全局最優解：

local[i][j] = max(global[i – 1][j – 1] + diff, local[i – 1][j] + diff)

global[i][j] = max(global[i – 1][j], local[i][j])

local[i][j]: 第i天，當天一定進行第j次交易的profit

global[i][j]: 第i天，總共進行了j次交易的profit.

local[i][j]和global[i][j]的區別是：local[i][j]意味著在第i天一定有交易（賣出）發生。

當第i天的價格高於第i-1天（即diff > 0）時，那麼可以把這次交易（第i-1天買入第i天賣出）跟第i-1天的交易（賣出）合併為一次交易，即local[i][j]=local[i-1][j]+diff；

當第i天的價格不高於第i-1天（即diff<=0）時，那麼local[i][j]=global[i-1][j-1]+diff，而由於diff<=0，所以可寫成local[i][j]=global[i-1][j-1]。

(Note:在我下面這個solution裡面沒有省去 +diff）

global[i][j]就是我們所求的前i天最多進行k次交易的最大收益，可分為兩種情況：

如果第i天沒有交易（賣出），那麼global[i][j]=global[i-1][j]；

如果第i天有交易（賣出），那麼global[i][j]=local[i][j]。

264. Paint House II.java Level: Review

一般的DP被加了狀態變成2D. 考慮最後位, 而前一位i-1又被i位的顏色限制, 於是在考慮 min dp[i] 時候, 又多了一層iteration. 所以變成了O(NK^2)

注意:

序列型dp[i]表示前i-1個的結果. 所以dp最好設定為 int[n + 1] size. 然而, 顏色在這裡是狀態, 所以保留在 j: [ 0~k)
[[8]] 這樣的edge case. 跑不進for loop, 所以特殊handle.

Optimization: 如果已知每次都要從cost裡面選兩個不同的最小cost,那麼先把最小挑出來, 就不必有第三個for loop O(NK)

265. 3 Sum Smaller.java Level: Medium

一般的O(n3)肯定不行。在此基礎上優化。發現j,k滿足條件時候，(k - j)就是所有 sum <target的情況了。而一旦>target, 又因為j不能後退，只能k--，那麼問題就被鎖定了. 這樣可以做到O(n2)

266. Array Partition I.java Level: Easy

從結果出發, 只需要找到加法的結果，而不強調具體配對。找到排列取單數位的規律，再考慮負數和正數的相同規律，即可找到排列求解的方法。

267. 1-bit and 2-bit Characters.java Level: Easy

方法1: Greedy. 從第一個bit開始數: 如果遇到1, 一定是跳兩位;如果遇到0, 一定是跳一位. loop to end, and see if index reaches the end.

方法2: 用DP硬做了一下:

如果i位是0, 那麼前面dp[i-1]或者dp[i-2] true就夠了.
如果i位是1, 那麼i-1位必須是1才滿足規則, 並且 dp[i-2]需要true.

268. Non-decreasing Array.java Level: Easy

比較升序的時候, 必須要估計到 i-1, i, i+1三個數位. 寫出來i-1, i+1之間的關係, 然後做合理的fix.

需要真的fix數組, 因為loop through做比較時會用到fix後的數字.

269. Max Consecutive Ones.java Level: Easy

Basic. Math.max track結果。記得在有對外操作的loop後，一定要把result object清理乾淨。

270. Find All Numbers Disappeared in an Array.java Level: Easy

方法1: 換到正確的位置。需要小心handle i, 因為不知道換到nums[i]上的是什麼，所以必須原地清理乾淨方能move on.

方法2: 做標記！很巧妙地運用了標記的方法, 標記成負數，證明visit過。 Preserve原數的負數，這樣可以繼續用此負數的絕對值來尋找原數所該被定的位置。非常巧妙！

方法3: 做標記！跟方法2類似，也是做標記，這一次是加上一個大於n的數（因為題目給了n的border），最後check一下就好。為不超Integer.MAX_VALUE, 每次加n前，取餘數。

做標記的方法固然快，但是相對來說比較hacky，在常規的代碼中，估計不會用到.

271. Maximum Average Subarray I.java Level: Easy

簡單的求sum, 同時求max, 結尾求餘數就好.

272. Largest Number At Least Twice of Others.java Level: Easy

找最大值, 和第二大的值, 看是否符合題意, 就行了. 分析題意, 最簡單方法, 可以loop 兩遍: 找最值; 作比較. 但其實, 舉個反例: 有一個不滿足, 就夠反對這個at least twice of alllll others.

273. Toeplitz Matrix.java Level: Easy

似乎沒什麼演算法特點, 就是array基本運算, 然後分割成一個helper function去做重複計算, 剪短代碼. 注意check MxN 的分界線.