[Review]LeetCode Top 100 Liked Questions(1)
所有代码可以在github上下载：https://github.com/proverbs/LTC
以下难易度评级为个人评级，非官方评级
个人认为比较有代表性的题目，标题将加粗
- Two Sum[easy]
https://leetcode.com/problems/two-sum/description/
从左向右扫，维护当前位置左侧的数字是否出现过（hashmap实现） - Add Two Numbers[easy]
https://leetcode.com/problems/add-two-numbers/description/
链表对应位置直接相加 - Longest Substring Without Repeating Characters[medium]
https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
双指针确定滑窗位置，set维护滑窗中字母是否出现。熟悉这种套路之后这题也是easy - Median of Two Sorted Arrays[easy]
https://leetcode.com/problems/median-of-two-sorted-arrays/description/
归并排序的数组合并方法 - Longest Palindromic Substring[hard]
https://leetcode.com/problems/longest-palindromic-substring/description/
暴力O(n^2)可以过
我用的二分+区间hash（需要手写，如果怕重复，可以多重hash），O(nlogn)
还有O(n)的方法，Manacher 算法 - Regular Expression Matching[hard]
https://leetcode.com/problems/regular-expression-matching/description/
dp[i][j]表示s的前i个和p的前j个匹配是否可行，但是恶心在条件转移非常复杂，需要考虑各种情况 - Container With Most Water[hard]
https://leetcode.com/problems/container-with-most-water/description/
一开始没有思路。考虑构成最大容器的左右边界，如果一个边它的左右两侧都有比它高的边，那么它不可能构成最大容器，所以可以删除。那么，最终剩下的所有边界构成单峰形。考虑i,j两条边构成的容器，其中较短的向中间移动则构成的新容器可能会更大，但是如果较长的向中间移动，则构成的新容器必然更小。所以得到贪心策略。最终做法，如果不删边对算法也不会有影响。 - 3Sum[easy]
https://leetcode.com/problems/3sum/description/
和2sum一样，a+b=-c，枚举c，然后用2sum的方法求解 - Letter Combinations of a Phone Number[easy]
https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/
dfs - Remove Nth Node From End of List[easy]
https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/
指针操作 - Valid Parentheses[easy]
https://leetcode.com/problems/valid-parentheses/description/
非常经典，通用的括号匹配方法——使用栈匹配 - Merge Two Sorted Lists[easy]
https://leetcode.com/problems/merge-two-sorted-lists/description/
归并排序的合并思想 - Generate Parentheses[east]
https://leetcode.com/problems/generate-parentheses/description/
dfs - Merge k Sorted Lists[easy]
https://leetcode.com/problems/merge-k-sorted-lists/description/
和Merge Two Sorted Lists类似，只不过想要快速的比较k个队头元素的大小需要使用优先队列或者堆这类数据结构。
代码里有heap的简单使用方式。 - Next Permutation[easy]
https://leetcode.com/problems/next-permutation/description/
从右向左，找第一个下降的数字，然后从这个数字到结尾排序 - Longest Valid Parentheses[hard]
https://leetcode.com/problems/longest-valid-parentheses/description/
利用之前提到的栈的括号匹配方法，只不过栈中还要保存这个括号的下标
还可以用dp[i]表示以i开头的最长匹配括号串长度，可由dp[i + 1]转移 - Search in Rotated Sorted Array[easy]
https://leetcode.com/problems/search-in-rotated-sorted-array/description/
很经典的题。二分查找先找出断点位置，然后再二分查找需要的数字 - Search for a Range[easy]
https://leetcode.com/problems/search-for-a-range/description/
二分查找，找不小于target+1的第一个数字，再找不小于target的第一个数字 - Combination Sum[easy]
https://leetcode.com/problems/combination-sum/description/
爆搜 - Trapping Rain Water[hard]
https://leetcode.com/problems/trapping-rain-water/description/
题目中的图给人启发：每个点的水位高度=min(这个点左侧最大值，这个点右侧最大值)
这两个最大值可以从左右两遍dp一下就可以了 - Permutations[easy]
https://leetcode.com/problems/permutations/description/
按字典序暴搜 - Rotate Image[medium]
https://leetcode.com/problems/rotate-image/description/
我写的方法超级麻烦，不说了。
比较好的方法是，既然我们会沿主对角线翻转，那么沿副对角翻转=水平翻转+沿主对角线翻转+水平翻转 - Group Anagrams[easy]
https://leetcode.com/problems/group-anagrams/description/
sort - Maximum Subarray[easy]
https://leetcode.com/problems/maximum-subarray/description/
最简单的dp - Jump Game[easy]
https://leetcode.com/problems/jump-game/description/
维护一个最远可达位置 - Merge Intervals[easy]
https://leetcode.com/problems/merge-intervals/description/
sort+维护最远可达位置 - Unique Paths[easy]
https://leetcode.com/problems/unique-paths/description/
dp或者直接组合数计算 - Minimum Path Sum[easy]
https://leetcode.com/problems/minimum-path-sum/description/
这个题本身很水，dp。
但这题有个拓展——传纸条问题，也就是两条不同路径，sum最小。dp[k][i][j]表示走了k步，其中向下走了i步和j步的两个位置到左上角的sum最小值。 - Climbing Stairs[easy]
https://leetcode.com/problems/climbing-stairs/description/
dp - Edit Distance[medium]
https://leetcode.com/problems/edit-distance/description/
dp[i][j]表示word1前i个和word2前j个匹配的最小距离，对于每个位置，根据3种操作有3种转移方式。 - Sort Colors[medium]
https://leetcode.com/problems/sort-colors/description/
第一种方法，统计每个数字的个数，然后在数组中直接填充；
第二种方法，从左向右扫描，动态更新每个数字下一个可插入位置的下标 - Minimum Window Substring[medium]
https://leetcode.com/problems/minimum-window-substring/description/
双指针确定滑窗位置，set维护滑窗中字母是否出现。和Longest Substring Without Repeating Characters一样 - Subsets[easy]
https://leetcode.com/problems/subsets/description/
2^n爆搜 - Word Search[easy]
https://leetcode.com/problems/word-search/description/
爆搜 - Largest Rectangle in Histogram[hard]
https://leetcode.com/problems/largest-rectangle-in-histogram/description/
很经典的stack应用。
枚举i作为面积的最高度，只需要知道左右两侧比h[i]小的第一个的位置。用stack维护单调减的队列即可。 - Maximal Rectangle[hard]
https://leetcode.com/problems/maximal-rectangle/description/
和上一道题一样，先枚举一下矩形区域的底部坐标即可 - Binary Tree Inorder Traversal[easy]
https://leetcode.com/problems/binary-tree-inorder-traversal/description/
dfs。
为什么加粗，是因为可以思考一下如何用非递归形式实现3种遍历。（我不管，反正我用手工栈） - Unique Binary Search Trees[medium]
https://leetcode.com/problems/unique-binary-search-trees/description/
类似区间dp - Validate Binary Search Tree[easy]
https://leetcode.com/problems/validate-binary-search-tree/description/
第一种方法，递归直接判断；
第二种方法，中序遍历是否有序 - Symmetric Tree[easy]
https://leetcode.com/problems/symmetric-tree/description/
树形结构上的题一般都递归做 - Binary Tree Level Order Traversal[easy]
https://leetcode.com/problems/binary-tree-level-order-traversal/description/
树的bfs - Maximum Depth of Binary Tree[easy]
https://leetcode.com/problems/maximum-depth-of-binary-tree/description/
dfs - Construct Binary Tree from Preorder and Inorder Traversal[medium]
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
根据先序遍历确定根，然后根据中序遍历确定左右子树节点，递归构造 - Flatten Binary Tree to Linked List[medium]
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/description/
使用递归函数：将子树化为链表，并返回链表首尾指针 - Best Time to Buy and Sell Stock[easy]
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/
动态维护当前最小值 - Binary Tree Maximum Path Sum[easy]
https://leetcode.com/problems/binary-tree-maximum-path-sum/description/
如果是多叉树，需要两次dp，分别算出节点向下的最大和第二大路径长度。
而二叉树则确定了最大和第二大路径长度：左子树最大路径长度和右子树最大路径长度（或者相反），所以更简单 - Longest Consecutive Sequence[medium]
https://leetcode.com/problems/longest-consecutive-sequence/description/
dp+hashmap - Single Number[medium]
https://leetcode.com/problems/single-number/description/
这里只讨论不用额外空间的做法：异或 - Word Break[medium]
https://leetcode.com/problems/word-break/description/
注意这个题不可以搜索和贪心匹配，所以需要使用dp - Linked List Cycle[hard]
https://leetcode.com/problems/linked-list-cycle/description/
以下解都不使用额外空间！真的有难度，反正我是想不到。
原题解：2个指针，其中一个每次移动1步，另一个每次移动2步，有环则必然相遇。
拓展1：求环的起点
拓展1解：设链表头到环的起点有x步，相遇点距环起点b步，环长s；则2k=x+ns+b, k=x+ms+b；相减2k-k = k = (n-m)s=x+ms+b；则x+b=(n-2m)s；也就是说从环起点走x+b步可以回到环起点；也就是说从链表头走x+(x+b)步可以到环起点；所以从相遇点走x步可到环起点。但是环起点未知，所以使用第3个指针从链表头开始，与相遇点指针每次移动1步，相遇时则为环起点。
拓展2：数组长度0-n(共n+1个数字)，每个数字为1-n中的一个，求重复数字
拓展2解：这样的数组其实是链表！！解法和拓展1相同。