LeetCode/LintCode ReviewPage 题解-

2016-04-22 本文已影响4322人土汪

背景

一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。张土汪：刷leetcode是什么样的体验？

慢慢有一些赞和感谢, 备受鼓舞, 于是我把所做过的题目用一个script跑了一下，编辑成一篇文章。这个总结页面是这么规划的：

题目名称(答案链接)
题目难度
解题关键点

学习过程中, 我认为, 成事四分靠刷题, 六分靠总结. 在漫长的刷题过程中, 我们常常被海量的题目(据说今天已经有700题)压得喘不过气, 而常常忽略总结的必要性.

然而，在真正面试时，刷题的功底最重要的功能就是在听到题目的的时候，能够快速地反应，在脑中找到相应地关键字，再回忆起相应地答案. 这个时候，对题目的熟知和关键点的掌握就非常重要。

当然，倒不是要将这份总结页面倒背如流，但是起码能在听到某个题目时，很快想到该用什么数据结构和方法，给自己有一个快而准的开端，会让面试的过程流畅许多，少一些紧张。成事之后，又能少几个月蹉跎：）

有朋友问，为什么要把自己做的题目和题目总结放在GitHub上面分享？这些不是要私自珍藏的精华吗？

Engineering的本质就是重复利用已有的精华，在已有的地基上创新前进。在我起初刷题的时候，我也蹉跎我也迷茫，不知道去哪找到做题的手感。那时候我找到许多前辈们在自己blog上面的题目解答，分享，给我带来非常多的思路。我是个强调注重自己思考，走完全程的人，在前辈的见解上为基础，按照所指引的方法尝试，优化，最后交上一份自己的答案，建立起自己的知识网络。这每一步，都离不开最初所得到的指点。

当自己结束了刷题旅程后，心中充满感激。为此，我特别把题目的精华写成中文，方便中国人阅读，复习起来也事半功倍。最后，总结了这篇长文章，希望给还在刷题事业中奔跑的中国人助力，希望大家找到自己心仪的工作！

如果对题目有什么不同的见解，我特别希望你能给我留言，或者到我的GitHub上发一个issue/pull-request, 帮助到更多学习中的代码仔!

GitHub Repo

从开始这个Github已经有将近两年时间, 很高兴这个repo可以帮到有需要的人. 我一直认为, 知识本身是无价的, 因此每逢闲暇, 我就会来维护这个repo, 给刷题的朋友们一些我的想法和见解.
所有内容都来自我的GitHub: https://github.com/awangdev/LintCode

下面来简单介绍一下这个repo:

README.md: 所有所做过的题目
ReviewPage.md: 所有题目的总结和归纳（不断完善中）
KnowledgeHash2.md: 对所做过的知识点的一些笔记
SystemDesign.md: 对系统设计的一些笔记
Future Milestone: 我准备将一些有意思的题目，做成视频的形式给大家参考

介绍一下自己和背后默默支持的老板

介绍一下自己！

希望大家学习顺利, 对未来充满希望(程序员也是找到好老板的!)
有问题可以给我写邮件(wangdeve@gmail.com), 或者在GitHub上发issue给我, 或者关注我的YouTubeChannel

干货

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/
1. take each string, count the occurrance of the 26 letters. save in int[]count.
2. hash the int[] count and output a unique hash value.
  hash = hash * a + num
  a = a * b.
3. 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可以被拆解成(aaaa....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<key>来存排位。
每次有更新，就把最新的放在末尾；每次超过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:

1
把所有小于curr node的，全Pop出来, while loop, keep it going.
最后pop出的这个小于Curr的node：它同时也是stack里面pop出来小于curr的最大的一个，最接近curr大小。（因为这个stack最大值靠下面）
把这个最大的小于curr的node放在curr.left.

2
那么，接下去stack里面的一定是大于curr：
那就变成curr的left parent. set stack.peek().right = curr.

3
结尾：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<T>()
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. Pascal's 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[0~a]=x, 然后sum[0~b]=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<Cell>.

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>, 可以直接比较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位和之前的0~i-1 都远关系。复杂一点。
每次都考虑o~i的所有情况。所以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 don't need to buyin at 5, 3, 6, 4 later on; we'll 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 的分界线.

LeetCode/LintCode ReviewPage 题解-

背景

GitHub Repo

介绍一下自己和背后默默支持的老板

干货

Review Page

猜你喜欢

热点阅读