【LeetCode】 高效算法刷题思路、算法题目分类 - 持续更新_下程好dfa073

刷 LeetCode 上的算法题对于掌握算法还是非常有在帮助的，但上面的题目太多太杂，
如果不做以归类，有目的性的刷题，最终肯定会有些心得，但同时也会浪费大量的时间。

但作为一个没刷多少题的 LeetCode 新手小白来说，对题目分类有点虚了。

本文是参考网上已有的 LeetCode 高手，并且结合自身的情况，进行归整，
希望归整出一份从㳀入深出，适合自已的高效刷题方法。

各种分类的题目也不是要全部刷完，视自已的掌握情况而定，简单的做几题就够了，比较难掌握的需要多刷一些题巩固。

好，我们开始吧^_^

算法分类

以下是具体的题目，先把是题号给出来，后面慢慢整理。

1、排序/排列算法

60 https://leetcode.com/problems/permutation-sequence
求第k个排列数。数学解法，可以找一下规律。比如对于1234的排列数，一共有24种。我们从左到右依次决定排列数是哪些。首先第一个数有4种可选的，一共有24种，那么每种就是6个，我们用 k / 6，看它落在哪个区间，就取哪个数字。
之后，还有三个数可选，因为一共有6种，所以每种有2个，我们计算k / 2……以此类推得到所有位的数字。因为k从0计数算起来更简单，所以我们一开始做k--。

75. 颜色分类
215. 数组中的第K个最大元素
76. 前 K 个高频元素
77. 根据字符出现频率排序
996 https://leetcode.com/problems/number-of-squareful-arrays/
这道题要求找到满足条件的排列数个数。可以在生成排列数的同时检查是否满足条件。
1
2
3
4
5
6
7
8
9
10

2、双指针

* 011. [Container With Most Water](TwoPointers/11_ContainerWithMostWater.py)
* 015. [3Sum](TwoPointers/15_3Sum.py)
* 016. [3Sum Closest](TwoPointers/16_3SumClosest.py)
* 018. [4Sum](TwoPointers/18_4Sum.py)
* 019. [Remove Nth Node From End of List](TwoPointers/19_RemoveNthNodeFromEndOfList.py)
* 042. [Trapping Rain Water](TwoPointers/42_TrappingRainWater.py)
* 075. [Sort Colors](TwoPointers/75_SortColors.py)
* 080. [Remove Duplicates from Sorted Array II](TwoPointers/80_RemoveDuplicatesArrayII.py)
* 088. [Merge Sorted Array](TwoPointers/88_MergeSortedArray.py)
* 125. [Valid Palindrome](TwoPointers/125_ValidPalindrome.py)
* 141. [Linked List Cycle](TwoPointers/141_LinkedListCycle.py)
* 142. [Linked List Cycle II](TwoPointers/142_LinkedListCycleII.py)
* 209. [Minimum Size Subarray Sum](TwoPointers/209_MinimumSizeSubarraySum.py)
* 283. [Move Zeroes](TwoPointers/283_MoveZeroes.py)
* 287. [Find the Duplicate Number](TwoPointers/287_FindTheDuplicateNumber.py)
* 345. [Reverse Vowels of a String](TwoPointers/345_ReverseVowelsOfString.py)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3、字符串

* 006. [ZigZag Conversion](String/06_ZigZagConversion.py)
* 008. [String to Integer](String/08_StringtoInteger.py)
* 014. [Longest Common Prefix](String/14_LongestCommonPrefix.py)
* 017. [Letter Combinations of a Phone Number](String/17_LetterCombinationsPN.py)
* 028. [Implement strStr()](String/28_ImplementstrStr.py)
* 038. [Count and Say](String/38_CountAndSay.py)
* 058. [Length of Last Word](String/58_LengthOfLastWord.py)
* 067. [Add Binary](String/67_AddBinary.py)
* 068. [Text Justification](String/68_TextJustification.py)
* 151. [Reverse Words in a String](String/151_ReverseWordsInString.py)
* 165. [Compare Version Numbers](String/165_CompareVersionNumbers.py)
* 344. [Reverse String](String/344_ReverseString.py)
1
2
3
4
5
6
7
8
9
10
11
12

4、位运算

* 029. [Divide Two Integers](BitManipulation/29_DivideTwoIntegers.py)
* 078. [Subsets](BitManipulation/78_Subsets.py)
* 136. [Single Number](BitManipulation/136_SingleNumber.py)
* 137. [Single Number II](BitManipulation/137_SingleNumberII.py)
* 169. [Majority Element](BitManipulation/169_MajorityElement.py)
* 190. [Reverse Bits](BitManipulation/190_ReverseBits.py)
* 191. [Number of 1 Bits](BitManipulation/191_NumberOf1Bits.py)
* 201. [Bitwise AND of Numbers Range](BitManipulation/201_BitwiseANDofNumbersRange.py)
* 231. [Power of Two](BitManipulation/231_PowerOfTwo.py)
* 260. [Single Number III](BitManipulation/260_SingleNumberIII.py)
* 268. [Missing Number](BitManipulation/268_MissingNumber.py)
* 318. [Maximum Product of Word Lengths](BitManipulation/318_MaximumProductOfWordLengths.py)
* 338. [Counting Bits](BitManipulation/338_CountingBits.py)
* 371. [Sum of Two Integers](BitManipulation/371_SumOfTwoIntegers.py)
* 342. [Power of Four](BitManipulation/342_PowerOfFour.py)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

5、数组与矩阵

* 026. [Remove Duplicates from Sorted Array](Array/26_RemoveDuplicatesFromSortedArray.py)
* 027. [Remove Element](Array/27_RemoveElement.py)
* 031. [Next Permutation](Array/31_NextPermutation.py)
* 041. [First Missing Positive](Array/41_FirstMissingPositive.py)
* 054. [Spiral Matrix](Array/54_SpiralMatrix.py)
* 056. [Merge Intervals](Array/56_MergeIntervals.py)
* 057. [Insert Interval](Array/57_InsertInterval.py)
* 059. [Spiral Matrix II](Array/59_SpiralMatrixII.py)
* 073. [Set Matrix Zeroes](Array/73_SetMatrixZeroes.py)
* 118. [Pascal's Triangle](Array/118_PascalTriangle.py)
* 119. [Pascal's Triangle II](Array/119_PascalTriangleII.py) 
* 164. [Maximum Gap](Array/164_MaximumGap.py)
* 189. [Rotate Array](Array/189_RotateArray.py)
* 228. [Summary Ranges](Array/228_SummaryRanges.py)
* 240搜索二维矩阵 II
* 283. [Move Zeroes](Array/283_MoveZeroes.py)
* 287 寻找重复数
* 289. [Game of Life](Array/289_GameOfLife.py)
378有序矩阵中第K小的元素
485最大连续1的个数
565数组嵌套
566重塑矩阵
645 错误的集合
667优美的排列 II
697数组的度
769最多能完成排序的块
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

6、搜索/二分查找

4 https://leetcode.com/problems/median-of-two-sorted-arrays/
双指针二分问题。把两个数组x,y划分为两个大小相等（或差1）的集合，维护数据maxLeft, minRight，哪边不满足maxLeft < minRight就移动一下指针。

11 https://leetcode.com/problems/container-with-most-water/
双指针二分问题。指针记录首尾位置，哪边更矮哪边的指针向中间移动，同时更新最大容水面积。

15 https://leetcode.com/problems/3sum/
双指针二分问题。

16 https://leetcode.com/problems/3sum-closest/
双指针二分问题。对于排好序的数组，首先确定三个数位置在中间的那个数字，然后在它左右搜索另外两个数，如果大于目标，则右指针左移，否则左指针右移。 

18 https://leetcode.com/problems/4sum/
双指针二分问题。和3sum相比，要先选定两个数，而不是一个数。

33 https://leetcode.com/problems/search-in-rotated-sorted-array/
根据下标二分问题。检查二分后的半段是否满足递增条件，如果满足且数据落在这一区间，就在这一区间查找，否则到另一区间查找。

34 https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
根据下标二分问题。要点是改变low或high的时候把当前数字mid也包含进来，因为它也可能是结果。

* 069. [Sqrt(x)](BinarySearch/69_Sqrt_x.py)

74 https://leetcode.com/problems/search-a-2d-matrix/
根据下标二分问题。

081. [Search in Rotated Sorted Array II](BinarySearch/81_SearchInRotatedSortedArrayII.py)


153. [Find Minimum in Rotated Sorted Array](BinarySearch/153_FindMinimumInRotatedSortedArray.py)
154. [Find Minimum in Rotated Sorted Array II](BinarySearch/154_FindMinimumInRotatedSortedArrayII.py)

162 https://leetcode.com/problems/find-peak-element/
根据下标二分问题。每次检查mid左右两个数和mid的关系，再决定如何进行下一步。

222. [Count Complete Tree Nodes](BinarySearch/222_CountCompleteTreeNodes.py)
230. [Kth Smallest Element in a BST](working/230_KthSmallestElementInBST.py)

250 https://leetcode.com/problems/search-a-2d-matrix-ii
 双指针二分问题。从矩阵的右上角开始搜索，到下标越界后退出。

275. [H-Index II](BinarySearch/275_H-IndexII.py)
276. [First Bad Version](BinarySearch/278_FirstBadVersion.py)

315 https://leetcode.com/problems/count-of-smaller-numbers-after-self/
先额外存一个排序好的数组。然后查找lower_bound，看有多少个数比它小，并把这个数从排序数组中移除。

278. [Valid Perfect Square](BinarySearch/367_ValidPerfectSquare.py)

475 https://leetcode.com/problems/heaters/

二分查找上下界问题。对加热器进行排序，通过二分查找距离最近的热水器，并求所有最近距离的最大值。

528 https://leetcode.com/problems/random-pick-with-weight/
二分查找上下界问题。首先计算一个累积的频数，根据总频数来进行随机，之后通过二分查找得到当前随机数对应的下标。

704 https://leetcode.com/problems/binary-search/
标准二分查找

875 https://leetcode.com/problems/koko-eating-bananas/
二分猜答案问题。也就是在一定的求解空间中找到最小满足条件的值，使得KoKo能够以最慢的速度在特定时间内吃完所有香蕉。

911 https://leetcode.com/problems/online-election/
二分查找上下界问题。主要是根据时间来二分，先预先计算好当前时间点对应的选举人，存到hashmap中。之后通过二分找到时间，再通过hash找到对应选举人。

1011 https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/
二分猜答案问题。也就是在一定的求解空间中找到最小满足条件的值，使得货船能够以最小的容量在特定时间内运完所有货物。

1146 https://leetcode.com/problems/snapshot-array/
 二分查找上下界问题。每次修改值的时候记录一下当前快照的值，然后每次查找当前下标特定快照id时的值时，二分查找小于等于这一快照id对应的值即
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

7、递归

* 022. [Generate Parentheses](Backtracking/23_GenerateParentheses.py)
* 039. [Combination Sum](Backtracking/39_CombinationSum.py)
* 046. [Permutations](Backtracking/46_Permutations.py) 
* 047. [Permutations II](Backtracking/47_PermutationsII.py)
* 051. [N-Queens](Backtracking/51_NQueens.py)
* 052. [N-Queens II](Backtracking/52_NQueensII.py)
* 060. Permutation Sequence
* 077. [Combinations](Recursion/77_Combinations.py)
* 079. [Word Search](Backtracking/79_WordSearch.py)
* 089. [Gray Code](Recursion/89_GrayCode.py)
* 090. [Subsets II](Backtracking/90_SubsetsII.py)
* 093. [Restore IP Addresses](Backtracking/93_RestoreIPAddresses.py)
* 101. [Symmetric Tree](Recursion/101_SymmetricTree.py)
* 131. [Palindrome Partitioning](Backtracking/131_PalindromePartitioning.py)
* 216. [Combination Sum III](Backtracking/216_CombinationSumIII.py)
* 257
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

8、分治法

50. Pow(x, n)
95. 不同的二叉搜索树 II
* 215. [Kth Largest Element in an Array](DivideConquer/215_KthLargestElementArray.py)
* 240. [Search a 2D Matrix II](DivideConquer/240_Search2DMatrixII.py)
* 241. [为运算表达式设计优先级Different Ways to Add Parentheses](DivideConquer/241_DifferentWaysToAddParentheses.py)
1
2
3
4
5

9、链表

* 002. [Add Two Numbers](LinkedList/02.AddTwoNumbers.py)
* 019 https://leetcode.com/problems/remove-nth-node-from-end-of-list/
* 021. [Merge Two Sorted Lists](LinkedList/21_MergeTwoSortedLists.py)
* 024. [Swap Nodes in Pairs](LinkedList/24_SwapNodesInPairs.py)
* 025. [Reverse Nodes in k-Group](LinkedList/25_ReverseNodesIn-k-Group.py)
* 061. [Rotate List](LinkedList/61_RotateList.py)
* 076. [Minimum Window Substring](LinkedList/76_MinimumWindowSubstring.py)
* 082. [Remove Duplicates from Sorted List II](LinkedList/82_RemoveDuplicatesFromSortedListII.py)
* 083. [Remove Duplicates from Sorted List](LinkedList/83_RemoveDuplicatesFromSortedList.py)
* 086. [Partition List](LinkedList/86_PartitionList.py)
* 092. [Reverse Linked List II](LinkedList/92_ReverseLinkedListII.py)
* 138. [Copy List with Random Pointer](LinkedList/138_CopyListWithRandomPointer.py)
* 143. [Reorder List](LinkedList/143_ReorderList.py)
* 147. [Insertion Sort List](LinkedList/147_InsertionSortList.py)
* 148. [Sort List](LinkedList/148_SortList.py)
* 160. [Intersection of Two Linked Lists](LinkedList/160_IntersectionOfTwoLinkedLists.py)
* 203. [Remove Linked List Elements](LinkedList/203_RemoveLinkedListElements.py)
* 206. [Reverse Linked List](LinkedList/206_ReverseLinkedList.py)
* 234. [Palindrome Linked List](LinkedList/234_PalindromeLinkedList.py)
* 237. [Delete Node in a Linked List](LinkedList/237_DeleteNodeInLinkedList.py)
* 328. [Odd Even Linked List](LinkedList/328_OddEvenLinkedList.py)
* 445.两数相加II
* 725.分隔链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

10、堆、栈和队列

10.1 堆

* 023. [Merge k Sorted Lists](Heap/23_MergeKSortedLists.py)
把所有数据加入堆里，再pop出来构建新链表。

* 295. [Find Median from Data Stream](Heap/295_FindMedianFromDataStream.py)
* 347. [Top K Frequent Elements](Heap/347_TopKFrequentElements.py)

215 https://leetcode.com/problems/kth-largest-element-in-an-array/
维护最大为K的堆。时间复杂度O(NlogK)。

692 https://leetcode.com/problems/top-k-frequent-words/
维护最大为K的堆。

793 https://leetcode.com/problems/k-closest-points-to-origin/
维护最大为K的堆。

1383 https://leetcode.com/problems/maximum-performance-of-a-team/
维护最大为K的堆。这里首先将所有人按照效率排序，优先选高效的，然后逐步剔除速度慢的人。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

10.2 栈

* 020. [Valid Parentheses](Stack/20_ValidParentheses.py)
* 032. [Longest Valid Parentheses](Stack/32_LongestValidParentheses.py)
 42 https://leetcode.com/problems/trapping-rain-water/

维护递减的单调栈。遇到大于栈顶的，就pop，因为当前栈顶元素左右两边的高度都一定比它高，所以可以同时计算它（横向的）蓄水量。

84  https://leetcode.com/problems/largest-rectangle-in-histogram
维护递增的单调栈，当发现当前数字比栈顶要小的时候，此时栈顶元素是最大的（大于栈里的下一个元素，也大于当前元素），所以可以计算以当前栈顶元素为高的矩形面积，并比较是不是最大的。

* 085. [Maximal Rectangle](Stack/85_MaximalRectangle.py)
* 094. [Binary Tree Inorder Traversal](Stack/94_BinaryTreeInorderTraversal.py)
150 https://leetcode.com/problems/evaluate-reverse-polish-notation/
栈模拟递归。遇到运算符就pop两个数字进行计算，并把结果push进去。

* 155. [Min Stack](Stack/155_MinStack.py)
* 224. [Basic Calculator](Stack/224_BasicCalculator.py)
* 225. [Implement Stack using Queues](Stack/225_ImplementStackusingQueues.py)
* 227. [Basic Calculator II](Stack/227_BasicCalculatorII.py)
* 232. [Implement Queue using Stacks](Stack/232_ImplementQueueUsingStacks.py)
316 https://leetcode.com/problems/remove-duplicate-letters/

维护递增的单调栈。首先，统计每个数字出现的次数，每次访问过就把出现次数减一。递增的单调栈对应着最小字典序的结果，已经在栈中的加一个visit标记，避免重复入栈，如果遇到比栈顶更小的，并且栈顶对应的字符在后面也有出现，可以考虑之后再入栈这一字符。所以可以把栈顶pop出来，替换为新的字符，并更新visit标记。

331 https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/

栈模拟递归。这道题需要记录一个count值，表示当前树还有多少个地方可以插入新的节点（包括插入数字和插入Null）。如果插入的是数字节点，那么会多一个可用的位置（新的节点占用了一个，但又新增了两个）；如果插入的是null,那么它只会占用一个，所以会少一个可用的位置。每次遇到没有可用位置的时候，意味着当前字符串非法。扫描到最后时，如果可用位置还有剩余，也意味着当前字符串非法。

341 https://leetcode.com/problems/flatten-nested-list-iterator/

栈模拟递归。先把所有数据逆序入栈，如果栈顶是数字就直接返回，如果栈顶是链表，把链表所有值逆序入栈，然后pop当前数据，再循环检查栈顶是否为数字。

385 https://leetcode.com/problems/mini-parser/

栈模拟递归。解析括号，直接使用递归解析更加简单。

402 https://leetcode.com/problems/remove-k-digits

维护递增的单调栈。出现了比栈顶小的，就可以移除栈顶的元素，此时k减去1。

456 https://leetcode.com/problems/132-pattern/

维护递减的单调栈。从后往前遍历，相当于寻找231paterrn。遇到更大的数就pop出来，同时记录栈顶的值（作为第二大的数），之后判断接下来的值小于这个第二大的数即可。

503 https://leetcode.com/problems/next-greater-element-ii/

维护递减的单调栈。不过由于题目要求是循环的，需要两个pass，第二个pass处理循环生效的next greater，同时需要把下标已经超出范围的队首数据及时pop出来。

739 https://leetcode.com/problems/daily-temperatures/

维护递减的单调栈。因为要找到比它高的第一个温度，所以遇到递减的都缓存起来，等到有更高的再一次性更新。

1019 https://leetcode.com/problems/next-greater-node-in-linked-list/

维护递减的单调栈。这道题对象是链表，不像数组可以快速通过下标索引，所以比较方便的做法是在栈中同时记录数字和对应的下标，并且默认填0，如果找到了比它大的第一个数，再修改下标对应的数字。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

11、贪心思想

45 https://leetcode.com/problems/jump-game-ii/submissions/
可以使用搜索完成。但标准做法是贪心，从当前位置跳到下一个位置时，选择下一个能跳到最远位置的地方。

55 https://leetcode.com/problems/jump-game/
暴力算法是n2。贪心思想是从后往前查询能跳到当前位置的，如果找到了，更新当前位置。最终位置如果能到0就返回true。

121. 买卖股票的最佳时机
* 122. [买卖股票的最佳时机 IIBest Time to Buy and Sell Stock II](Greedy/122_BestTimeToBuyAndSellStockII.py)

134 https://leetcode.com/problems/gas-station
如果A->B无法完成到达，那么中间也没有答案（之前累积的结果都是正的，最后一个位置让它不再为正数；如果把起始指针向后移动，情况只会更糟）；如果气体总和大于消耗量，那么必然有解。

* 316. [Remove Duplicate Letters](Greedy/316_RemoveDuplicateLetters.py)
* 330. [Patching Array](Greedy/330_PatchingArray.py)

378 https://leetcode.com/problems/monotone-increasing-digits/
从后往前遍历，找到最后一个i + 1小于i的pair,之后的数字都设置为9，找到小于的时候，把上一个数字减一。

406. 根据身高重建队列
435. 无重叠区间
452. 用最少数量的箭引爆气球

455. 分发饼干

630 https://leetcode.com/problems/course-schedule-iii/
按照结束时间排序，如果当前课程无法在ddl前完成了，就去掉一个时间最长的课程。贪心的标准做法是按结束时间排序后尽可能选，选不了的就放弃。但是这道题的区别在于它的开始时间并不是确定的。

789 https://leetcode.com/problems/escape-the-ghosts/
如果能和鬼在终点相遇，那么也会在其他地方相遇。

870 https://leetcode.com/problems/advantage-shuffle/
In ordered to maximize the advantage of array A with respect to B, we had better choose the smallest element in array A that is larger than the element in B. After each selection, we erase the data we choose in A to avoid repetition.

948  https://leetcode.com/problems/bag-of-tokens/
排序。从左边消耗，能量不够了从右边取，直到无法补充能量，或首尾指针相遇。

955 https://leetcode.com/problems/delete-columns-to-make-sorted-ii/
从左到右扫描，如果有一个数字不满足字典序，那么删掉该列，否则保留。

1147 https://leetcode.com/problems/longest-chunked-palindrome-decomposition/
左边右边开始依次匹配，匹配到了就加一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

12、树

* 094. [Binary Tree Inorder Traversa](Tree/94_BinaryTreeInorderTraversal.py)		
树的中序遍历。非递归的做法是使用栈，先入栈所有左子树，pop出来的时候入栈当前节点的右子树的所有左子树。

* 095. [Unique Binary Search Trees II](Tree/95_UniqueBinarySearchTreesII.py)
* 096. [Unique Binary Search Trees](Tree/96_UniqueBinarySearchTrees.py)
* 98 https://leetcode.com/problems/validate-binary-search-tree
检查是否是合法二叉搜索树。对于所有结点，检查是否满足大于左子树，小于右子树。

* 099. [Recover Binary Search Tree](Tree/99_RecoverBinarySearchTree.py)
* 100. [Same Tree](Tree/100_SameTree.py)
* 105. [Construct Binary Tree from Preorder and Inorder Traversal](Tree/105_ConstructBinaryTreePreorderInorder.py)
根据中序和前序重建树。前序第一个作为根，在中序找到这个数字，左边的是左子树，右边的是右子树。 

* 106. [Construct Binary Tree from Inorder and Postorder Traversal](Tree/106_ConstructBinaryTreeInorderPostorder.py)
* 108. [Convert Sorted Array to Binary Search Tree](Tree/108_ConvertSortedArrayToBinarySearchTree.py)
* 109. [Convert Sorted List to Binary Search Tree](Tree/109_ConvertSortedListToBinarySearchTree.py)
* 110. [Balanced Binary Tree](Tree/110_BalancedBinaryTree.py)
* 111. [Minimum Depth of Binary Tree](Tree/111_MinimumDepthofBinaryTree.py)
* 112. [Path Sum](Tree/112_PathSum.py)
* 113. [Path Sum II](Tree/113_PathSumII.py)
* 114. [Flatten Binary Tree to Linked List](Tree/114_FlattenBinaryTreeToLinkedList.py)
* 116. [Populating Next Right Pointers in Each Node](Tree/116_PopulatingNextRightPointersInEachNode.py)
* 117. [Populating Next Right Pointers in Each Node II](Tree/117_PopulatingNextRightPointersInEachNodeII.py)
* 124. [Binary Tree Maximum Path Sum](Tree/124_BinaryTreeMaximumPathSum.py)
* 144. [Binary Tree Preorder Traversal](Tree/144_BinaryTreePreorderTraversal.py)
树的前序遍历。非递归的做法是使用栈，先入栈右子树，再入栈左子树。

* 145. [Binary Tree Postorder Traversal](Tree/145_BinaryTreePostorderTraversal.py)
树的后序遍历。非递归的做法是使用栈，先入栈左子树，再入栈右子树，再把结果反过来。

* 173. [Binary Search Tree Iterator](Tree/173_BinarySearchTreeIterator.py)
* 199 https://leetcode.com/problems/binary-tree-right-side-view/
树的层次遍历。输出每层最后一个结点。

* 208. [Implement Trie (Prefix Tree)](Tree/208_ImplementTrie.py)
* 211. [Add and Search Word](211_AddandSearchWord.py)
* 222 https://leetcode.com/problems/count-complete-tree-nodes/
统计完全二叉树的节点个数。可以先判断当前子树是不是满二叉树，是的话直接返回2^n - 1，否则递归查找。

* 226. [Invert Binary Tree](Tree/226_InvertBinaryTree.py)
* 230 https://leetcode.com/problems/kth-smallest-element-in-a-bst/
中序遍历，输出第k个数字。

* 235. [Lowest Common Ancestor of a Binary Search Tree](Tree/235_LowestCommonAncestorOfBinarySearchTree.py)
* 236. [Lowest Common Ancestor of a Binary Tree](Tree/236_LowestCommonAncestorOfBinaryTree.py)
* 297. [Serialize and Deserialize Binary Tree](Tree/297_SerializeAndDeserializeBinaryTree.py)
* 331. [Verify Preorder Serialization of a Binary Tree](Tree/331_VerifyPreorderSerializationOfBinaryTree.py)

* 865 https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes
同1123。

* 1026 https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/
返回当前节点子节点的最大值和最小值，计算差并更新结果。

* 1123 https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves
最小公共祖先，选择左右节点中高度比较小的结点对应的答案，如果高度一样，返回自己。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

13、广度优先搜索BFS

在求单源最短路径中，我们可能会遇到两种情况，一种是无权的最短路径，另一种是有权的最短路径。
对于无权的最短路径，因为我们是按层访问的，所以我们只需要跟踪当前搜索层数；一旦我们访问到了某个结点，那么当前的层数就一定是到达它的最短路径。
而对于有权的最短路径，我们往往采取贪心的策略，在已经确定了最短路径的结点中，选择它们相邻的未访问过的结点的最小权重路径，加入访问结点集合中。
在有权的情况下，我们常常会用到一个dist容器，用于存储出发点到当前点的最短路径，并且在发现了更短的路径后，需要更新dist里的数据，这是考虑到以下情况：

当我们访问到蓝色结点时，我们会同时更新它的邻居的最短距离，比如将橙色结点更新为dist[blue] + 8; 但是此时我们只是确定了蓝色结点的路径是最短的，还无法保证橙色结点的路径是最短的；因此需要在绿色结点访问到橙色结点时，更新橙色结点的最短路径。

102 https://leetcode.com/problems/binary-tree-level-order-traversal/

树的层次遍历。基础题。

* 103. [Binary Tree Zigzag Level OrderTraversal](BreadthFirstSearch/103_BinaryTreeZigzagLevelOrderTraversal.py)
* 104. [Maximum Depth Of BinaryTree](BreadthFirstSearch/104_MaximumDepthOfBinaryTree.py)
* 107. [Binary Tree Level Order Traversal II](BreadthFirstSearch/107_BinaryTreeLevelOrderTraversalII.py)


126 https://leetcode.com/problems/word-ladder-ii/

单源无权最短路径。难点在于要记录所有的路径。我的做法是先用宽搜得到最短路径的邻接关系，之后再利用深搜从后往前归纳所有路径，然后把路径倒序。

127 https://leetcode.com/problems/word-ladder/submissions/
单源无权最短路径。

* 130. [Surrounded Regions](BreadthFirstSearch/130_SurroundedRegions.py)
* 199. [Binary Tree Right Side View](BreadthFirstSearch/199_BinaryTreeRightSideView.py)


207 https://leetcode.com/problems/course-schedule/

拓扑排序。计算所有点入度，入度为0的点放入队列。每pop一个节点，它的邻居入度都减一，如果出现了入度为0的点，再放入队列。如果访问的节点数等于课程数，那么可以完成所有课程。

301 https://leetcode.com/problems/remove-invalid-parentheses/

搜索所有可能的去除组合，判断是否是有效括号，如果是就加入结果。

310 https://leetcode.com/problems/minimum-height-trees/
 类拓扑排序。找到只有一个邻居的点加入队列，每pop一个节点，它的邻居的邻接表就减去这一节点，直到只剩下一/两个节点。

* 322. [Coin Change](BreadthFirstSearch/322_CoinChange.py)

513 https://leetcode.com/problems/find-bottom-left-tree-value/

树的层次遍历。深搜应该也可以的。

515 https://leetcode.com/problems/find-largest-value-in-each-tree-row/

树的层次遍历。

542 https://leetcode.com/problems/01-matrix/

多源无权最短路径。和单源相比，也就是把所有的0加入起始队列就可以了。

743 https://leetcode.com/problems/network-delay-time/

单源有权最短路径。相当于求到每个点的最短路径，然后去其中最大值。

752 https://leetcode.com/problems/open-the-lock/

单源无权最短路径。把锁的状态记录为字符串即可。

773 https://leetcode.com/problems/sliding-puzzle/

单源无权最短路径。特别的时需要用字符串来记录所有状态量，找到目标状态量后就退出，我们总能保证找到时用到的步数是最少的。

778 https://leetcode.com/problems/swim-in-rising-water/

宽度优先搜索。使用优先队列，每次选择值最小的作为下一个，并更新最大值作为结果。

787 https://leetcode.com/problems/cheapest-flights-within-k-stops/

单源有权最短路径。由于有k的次数限制，用宽搜会更加直观。记录当前到达终点的最短路径，如果有更短的，把新的节点加入队列。

847 https://leetcode.com/problems/shortest-path-visiting-all-nodes/

 单源无权最短路径（带状态）。判断重复节点访问需要考虑当前状态：访问过哪些节点。

854 https://leetcode.com/problems/k-similar-strings/

宽度优先搜索。每次匹配一个字符，第K次后退出。

863 https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/

先从树建图，然后做层次遍历。

864 https://leetcode.com/problems/shortest-path-to-get-all-keys/

单源无权最短路径（带状态）。判断重复节点访问需要考虑当前状态：带了几把钥匙。

909 https://leetcode.com/problems/snakes-and-ladders/

单源无权最短路径。比较麻烦的一点是要换算位置和对应数字，此外要特殊处理梯子，因为遇到了梯子/蛇一定要滑过去，所以我们可以当作把这一位置作为跳板直接到达了梯子末端，就好像没有来过这一位置一样。

934 https://leetcode.com/problems/shortest-bridge/

多源无权最短路径。先用深搜给一个岛屿加上标记，之后的做法就类似于542了，取最小的最短路径即可。

1091 https://leetcode.com/problems/shortest-path-in-binary-matrix/

单源无权最短路径。

1129 https://leetcode.com/problems/shortest-path-with-alternating-colors/

单源无权最短路径，但有限制条件。这道题要求每次走不同颜色的路径，需要注意的是不同颜色路径到同一个结点的访问状态需要分别维护。

1135 https://leetcode.com/contest/biweekly-contest-5/problems/connecting-cities-with-minimum-cost/ 

最小生成树。使用优先队列， 从一个空集合开始，加入任一顶点，并找到该集合中顶点连接的权重最小的边，把该边连接的点也加入集合。直到所有的点都加入了集合，意味着找到了最小生成树。

1136 https://leetcode.com/contest/biweekly-contest-5/problems/parallel-courses/

 拓扑排序。

(1) 对于有向图，记录所有顶点的入度（指向该顶点的边的个数）

(2) 找到所有入度为0的顶点，把顶点放入队列

 (3) 从队列pop出一个元素，该顶点则是当前满足条件的顶点，可将计数加一，并把它指向的顶点的入度都减一，重复(2)(3)直到队列为空

 如果已经找不到入度为0的顶点，而当前计数还没有覆盖到所有顶点，那么说明有向图中可能出现了环路。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

14、深度优先搜索DFS

17 https://leetcode.com/problems/letter-combinations-of-a-phone-number/

暴力搜索所有可能的电话号码组合。

22 https://leetcode.com/problems/generate-parentheses

暴力搜索所有可能的括号组合。需要传入当前需要的'('和')'数量。

37 https://leetcode.com/problems/sudoku-solver/

暴力搜索可能的解。发现无法继续时就回退到上一步。

39 https://leetcode.com/problems/combination-sum/

暴力搜索所有可能的等于sum的组合。为了避免生成重复，先进行排序，按照非递减的顺序找下一个数字。

40 https://leetcode.com/problems/combination-sum-ii/

暴力搜索所有可能的等于sum的组合。和39相比存在重复，选择的时候跳过重复即可。

51 https://leetcode.com/problems/n-queens/

 回溯。

52 https://leetcode.com/problems/n-queens-ii/

 回溯。

* 098. [Validate Binary Search Tree](DepthFirstSearch/98_ValidateBinarySearchTree.py)

90 https://leetcode.com/problems/subsets-ii

暴力搜索所有可能的集合结果。

113 https://leetcode.com/problems/path-sum-ii/

 暴力搜索所有可能的等于sum的组合。

* 126. [Word Ladder II](DepthFirstSearch/126_WordLadderII.py)
* 129. [Sum Root to Leaf Numbers](DepthFirstSearch/129_SumRootToLeafNumbers.py)

133 https://leetcode.com/problems/clone-graph/

* 140. [Word Break II](DepthFirstSearch/140_WordBreakII.py)

递归拷贝。如果已经拷贝过，就直接设置指针，没有拷贝过，就去拷贝。

200 https://leetcode.com/problems/number-of-islands/

每搜索一趟就能遍历一个岛屿，搜索后加上visit标记，一共搜了几次就有几个岛屿。

241 https://leetcode.com/problems/different-ways-to-add-parentheses/

分治。先记录左边运算结果，再计算右边运算结果，最后把两个结果合并起来。

* 301. [Remove Invalid Parentheses](DepthFirstSearch/301_RemoveInvalidParentheses.py)

* 306. [Additive Number](DepthFirstSearch/306_AdditiveNumber.py)

698 https://leetcode.com/problems/partition-to-k-equal-sum-subsets/

记忆化搜索。首先求出划分为k份后每个集合的总和目标值，每次取一个没有访问过的数据作为下一个累加数据，每找到一个目标值后份数减一，目标值重置为0。看能否恰好减为0。

417 https://leetcode.com/problems/pacific-atlantic-water-flow/

记忆化搜索。返回值是pair对，记录当前位置能否到达两个海洋，如果它能到达的位置能到达海洋，那么它也能到达。最后扫一遍所有数据，找到两个都为true的加入结果。

529 https://leetcode.com/problems/minesweeper/

搜索遍历。每次扫描到某个空白节点后都判断它能够被填充，不能则返回，能则继续搜索，并修改指向内容，作为visit访问标记。

785 https://leetcode.com/problems/is-graph-bipartite/

二分图判断。给每个节点染色，并且检查它的邻居和它的颜色是否相等，如果存在相等说明不是二分图。

851 https://leetcode.com/problems/loud-and-rich/

建立有向图，搜索遍历所有比它富有的人，取其中最安静的。

967 https://leetcode.com/problems/numbers-with-same-consecutive-differences/

搜索所有满足条件的结果。

1034 https://leetcode.com/problems/coloring-a-border/

 深度优先搜索。先全涂一个色，然后对边界和非边界分别涂色。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

15、图

* 133. [Clone Graph](Graph/133_CloneGraph.py)
* 207. [Course Schedule](Graph/207_CourseSchedule.py)
* 210. [Course Schedule II](Graph/210_CourseScheduleII.py)
1
2
3

16、哈希表

* 001. [Two Sum](HashTable/01_TwoSum.py)
* 003. [Longest Substring Without Repeating Characters](HashTable/03_LongestSubstringWithoutRepeatingCharacters.py)
* 018. `4Sum`
* 30 https://leetcode.com/problems/substring-with-concatenation-of-all-words/
用hash记录目标值，从每个下标开始搜索当前字符串是否满足条件，满足则加入结果。

* 036. [Valid Sudoku](HashTable/36_ValidSudoku.py)
哈希检测重复。

* 049. [Group Anagrams](HashTable/49_GroupAnagrams.py)
所有的字符串hash到字典序。

* 128. [Longest Consecutive Sequence](HashTable/128_LongestConsecutiveSequence.py)
* 146. [LRU Cache](HashTable/146_LRUCache_pythonic.py)
* 149. [Max Points on a Line](HashTable/149_MaxPointsOnLine.py)
* 187. [Repeated DNA Sequences](HashTable/187_RepeatedDNASequences.py)
* 205. [Isomorphic Strings](HashTable/205_IsomorphicStrings.py)
* 217. [Contains Duplicate](HashTable/217_ContainsDuplicate.py)
* 219. [Contains Duplicate II](working/219_ContainsDuplicateII.py)
* 242. [Valid Anagram](HashTable/242_ValidAnagram.py)
* 257. [Binary Tree Paths](DepthFirstSearch/257_BinaryTreePaths.py)
* 274. [H-Index](HashTable/274_H-Index.py)
* 290. [Word Pattern](HashTable/290_WordPattern.py)
* 299. [Bulls and Cows](HashTable/299_BullsAndCows.py)
* 347 https://leetcode.com/problems/top-k-frequent-elements/
维护每个数字出现频率，每个频率对应数字，然后从高频率往低搜索。

* 349. [Intersection of Two Arrays](HashTable/349_IntersectionOfTwoArrays.py)
* 350. [Intersection of Two Arrays II](HashTable/350_IntersectionOfTwoArraysII.py)

* 467 https://leetcode.com/problems/unique-substrings-in-wraparound-string/
哈希计数。遇到特定值的时候就添对应容器加计数，最后把所有计数累加起来得到结果。

* 523
同560类型题。

* 560 https://leetcode.com/problems/subarray-sum-equals-k/
使用哈希表记录之前出现的前缀和sum - k。

* 781 https://leetcode.com/problems/rabbits-in-forest/
值为n的可以和其它n + 1个值为n的成组，统计每个值出现的次数，看它们可以组成多少组相同颜色的兔子，然后乘以组中兔子个数。

* 890 https://leetcode.com/problems/find-and-replace-pattern/
维护两个哈希，a中第i位数字和b中第i位数字相互映射，检测之后的相同数字是否也满足这种映射。

* 895 https://leetcode.com/problems/maximum-frequency-stack/
维护两个哈希。一个哈希记录每个数字出现的频率，一个哈希记录每个频率出现的数字，因为可能有多个，可存入栈中。每次取最大频率对应的栈顶值，并移除。如果最大频率变为0，那么移除这一频率。

* 930 https://leetcode.com/problems/binary-subarrays-with-sum/
记录连续0出现的数字，计算所有(zeros[i] + 1) * (zeros[i + S] + 1)的累加。

* 954 https://leetcode.com/problems/array-of-doubled-pairs
记录每个数字出现频率。按绝对值排序，对于每个数字，查找是否存在2 * x的数字，如果存在，就把它移除，否则返回false。

* 974 https://leetcode.com/problems/subarray-sums-divisible-by-k/
使用hash记录当前前缀和%K，如果前面存在相同的数字，那么意味着存在这样的连续子数组。

* 981 https://leetcode.com/problems/time-based-key-value-store/
维护unordered_map<int,map<int,int>>的结果，二分查找每个key对应的时间戳。

* 1044 https://leetcode.com/problems/longest-duplicate-substring/
哈希字符串匹配。先二分，再哈希查找是否存在长度为k的重复字符串。

* 1072 https://leetcode.com/problems/flip-columns-for-maximum-number-of-equal-rows/
假设当前行是结果。查找和它相等，以及和它恰好相反的子串数量，取最大值。

* 1074 https://leetcode.com/problems/number-of-submatrices-that-sum-to-target/
对任何两行/列的前缀和，求子数组的前缀和。

* 1124 https://leetcode.com/problems/longest-well-performing-interval/
等价于找和大于0的最长区间。

* 1138 https://leetcode.com/problems/alphabet-board-path/
哈希记录每个字母的下标。按照曼哈顿距离挪过去。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

17、字典树

208 https://leetcode.com/problems/implement-trie-prefix-tree/
实现字典树。包含查询单词，和查询单词是否包含前缀。
1
2

18、动态规划

5 https://leetcode.com/problems/longest-palindromic-substring/

爬台阶类型问题。考虑字符串的中心字符会更加方便，为了处理奇数和偶数，可以开成2 * n - 1的dp。或者直接从中心往两边扩展，查找最长的。

10 https://leetcode.com/problems/regular-expression-matching/

匹配类型问题。状态方程稍微有些麻烦，如果当前匹配（包括.匹配），则从i - 1, j - 1转换到i ,j ,但如果当前匹配为 *，因为*可代表匹配0个，可选择匹配或不匹配。

32 https://leetcode.com/problems/longest-valid-parentheses/

 最长子串类型问题。

dp[ i ] 代表以i为结尾的最长有效括号字符串的长度。

如果检测到s[i + 1] = ')'且s[i - 1 - dp[i] = '(', 则有dp[ i + 1 ] = dp[ i ] + 2； （嵌套括号）

如果检测到 以 i - dp[i] 下标为结尾处也对应了有效括号字符串，那么 dp[i + 1] += dp[ i - dp[i] ]  （并列括号）

44 https://leetcode.com/problems/wildcard-matching/

匹配类型问题。

62 https://leetcode.com/problems/unique-paths/

 爬台阶类型问题。从上方或左方汇总结果。

63 https://leetcode.com/problems/unique-paths-ii

爬台阶类型问题。从上方或左方汇总结果，有障碍则不汇总。

64 https://leetcode.com/problems/minimum-path-sum/

 爬台阶类型问题。从上方或左方叠加最小值。

72 https://leetcode.com/problems/edit-distance/

爬台阶类型问题（2D）。要么选择替换，要么选择添加一个，选择其中转换次数最小的。

85 https://leetcode.com/problems/maximal-rectangle/

最大面积问题。先计算每一列的前缀和，可以把每一行看作横坐标，当前的值看作高度，得到一个直方图一样的东西，接下来只需计算直方图中的最大矩形面积。时间复杂度O(N3)，用单调栈做是O(N2)

87 https://leetcode.com/problems/scramble-string/

记忆化搜索。在所有可能的交换结果中找是否存在满足条件的。

91 https://leetcode.com/problems/decode-ways

爬台阶类型问题。当前要么解析一个字节，要么解析两个字节。

95 https://leetcode.com/problems/unique-binary-search-trees-ii/

       记忆化搜索。权值在(i, j) 之间的树可以存起来，作为更大的树的子树。

96 https://leetcode.com/problems/unique-binary-search-trees-ii/

       爬台阶类型问题。同上，但无需存储所有结果了。从左右子树汇总结果。

97 https://leetcode.com/problems/interleaving-string/

匹配类型问题。需从多种选择中找到满足条件的。

115 https://leetcode.com/problems/distinct-subsequences/

匹配类型问题。

120: https://leetcode.com/problems/triangle/

爬台阶类型问题。相当于带权重的一次爬台阶。

123 https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

分治。分成两部分，叠加两边最大的结果。

132 https://leetcode.com/problems/palindrome-partitioning-ii/

划分类型问题。先计算出所有可能的回文串，dp[ i ] 代表前 i 个字符的最小划分，找到以 i 结尾的所有回文串，取划分最小的那个作为结果。

139 https://leetcode.com/problems/word-break/

划分类型问题。

140 https://leetcode.com/problems/word-break-ii

划分类型问题。和139差不多，但是有些test case 实在太烦人了。

152 https://leetcode.com/problems/maximum-product-subarray

多状态转换类型问题。需要维护当前的最大值和最小值，在两者之间因为正负数可以发生转换。

174 https://leetcode.com/problems/dungeon-game/

爬台阶类型问题。但是需要从终点到起点反向求解，才能得到合法的递推关系，记录的是到达当前位置需要的hp。

188 https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

多状态转换类型问题（带次数限制）。存在手上持有股票和手上不持有股票状态，多了一个最大k次交易的限制条件，因为在状态转移方程中，需要多考虑一个k的维度。

213 https://leetcode.com/problems/dungeon-game/

多状态转换类型问题。需要考虑当前偷，当前不偷，第一次偷了，第一次没偷。

221 https://leetcode.com/problems/maximal-square/

最大面积问题。看三个重叠的正方形加上当前位置能否凑成更大的正方形。

264 https://leetcode.com/problems/ugly-number-ii/

数字类问题。大的丑数是小的丑数乘以2，3，5得到的，每次选择最小的作为下一个。

279 https://leetcode.com/problems/perfect-squares

数字类问题。查找当前数字减去一个平方数对应的最小拆分次数。

300 https://leetcode.com/problems/longest-increasing-subsequence/

最长子序列问题。经典dp。

304 https://leetcode.com/problems/range-sum-query-2d-immutable/

最大面积问题。类似221。

309 https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

多状态转换类型问题。持有股票状态，卖出股票状态，冷却状态。

312 https://leetcode.com/problems/burst-balloons

区间题。需要考虑每个区间的长度，从小往大更新。

313 https://leetcode.com/problems/super-ugly-number/

数字类问题。同264。

321 https://leetcode.com/problems/create-maximum-number

分治。左最大 + 右最大的组合中挑一个最大的。

322 https://leetcode.com/problems/coin-change/

背包类型问题。总金额为背包容量，记录每个金额的最小次数。

338 https://leetcode.com/problems/counting-bits

数字类型问题。简单dp。

343 https://leetcode.com/problems/integer-break/

数字类型问题。乘积取最大的。

354 https://leetcode.com/problems/russian-doll-envelopes/

最大子序列问题。二分法做速度会更快。

357 https://leetcode.com/problems/count-numbers-with-unique-digits

数字类型问题。

363 https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k

最大面积问题。同时用到了二分，思考这道题可以先从数组入手，再扩展到矩阵。

368 https://leetcode.com/problems/largest-divisible-subset/

最长子序列和问题。不仅需要求出最长的，还需要输出最长的，所以需要记录路径。

375 https://leetcode.com/problems/guess-number-higher-or-lower-ii

 分治。在最优解下，取左右最大的 + k。问题描述让人很困惑，不知道它需要的是最优解下的情况。

416 https://leetcode.com/problems/partition-equal-subset-sum/

背包类型问题。总和的一半为背包总容量，找到能够恰好填满背包的物体。

647 https://leetcode.com/problems/palindromic-substrings/

爬台阶类型问题。回文子串个数，为了处理奇偶回文，可以开一个2 * n + 1长度的dp容器。

650 https://leetcode.com/problems/2-keys-keyboard/

爬台阶类型问题。状态可由上一个因数转换过来。

673 https://leetcode.com/problems/number-of-longest-increasing-subsequence/

最长子序列类型问题。需要开两个数组，在维护最长长度的同时更新最长长度的数量。

714 https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

多状态转换类型问题。存在手上持有股票和手上不持有股票状态。

740 https://leetcode.com/problems/delete-and-earn/

爬台阶类型问题。根据当前数字和前一数字相差是否为1决定从前一数字转换到当前数字，还是从前前一数字转换到当前数字。

764 https://leetcode.com/submissions/detail/234958158/

计算每个格子四边最长的1。

801 https://leetcode.com/problems/minimum-swaps-to-make-sequences-increasing/

多状态转换问题。交换和不交换两种。

808 https://leetcode.com/problems/soup-servings

记忆化搜索。直接模拟题意即可，但有一个数学上的trick，并没有想到。

813 https://leetcode.com/problems/largest-sum-of-averages

划分类型问题（带次数限制）。递推考虑的不只是从前i个数字到前i + 1个数字，还需要考虑从划分为k到划分为k + 1组，相当于在后面叠加一组。

877 https://leetcode.com/problems/stone-game/

拿左拿右取最大的那种结果。非递归写法是从后往前推导。

931 https://leetcode.com/problems/minimum-falling-path-sum/

爬台阶类型问题。可以从上一层的左中右选择最小的。

935 https://leetcode.com/problems/knight-dialer

爬台阶类型问题。n + 1长度的从n 长度的累加得到。

956 https://leetcode.com/problems/tallest-billboard

背包类型问题。要点在于记录的是两个背包的差值。

960 https://leetcode.com/problems/delete-columns-to-make-sorted-iii/

最长子序列类型问题。求n个字符串都符合的最长字典序子序列即可。

983 https://leetcode.com/problems/minimum-cost-for-tickets/

背包类型问题。一年总天数为背包容量。

1024 https://leetcode.com/problems/video-stitching/

背包类型问题。片段总长度为背包容量。

1027 https://leetcode.com/problems/longest-arithmetic-sequence/description/

最长子序列类型问题。之前状态可存hash中。

1039 https://leetcode.com/problems/minimum-score-triangulation-of-polygon/

记忆化搜索。需要以边作为子问题划分的基础。

1043 https://leetcode.com/problems/partition-array-for-maximum-sum/

限制长度的划分。注意划分为k个连续集合，和划分的连续集合中最多k个数字，以及划分为k个可不连续的子集的区别。

1048 https://leetcode.com/problems/longest-string-chain/

爬台阶类型问题。从k - 1长度转换到k长度，取其中总长最大的。

1105. https://leetcode.com/problems/filling-bookcase-shelves/

背包类型问题（2D）。当前书可以单独放，也可以选择和前面n本一起放。

1139 https://leetcode.com/problems/largest-1-bordered-square

最大面积问题。类似85，由于是边框问题，要同时考虑横向累积和纵向累积，而85只需考虑其中一个就够了。

1143 https://leetcode.com/problems/longest-common-subsequence/

最长公共子序列。经典dp。

1155 https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/

背包类型问题。带次数限制，可多次使用的完全背包。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269

19、滑动窗口

* 007. [Reverse Integer](Math/07_ReverseInteger.py)
* 009. [Palindrome Number](Math/09_PalindromeNumber.py)
* 012. [Integer to Roman](Math/12_IntegertoRoman.py)
* 013. [Roman to Integer](Math/13_RomantoInteger.py)
* 048. [Rotate Image](Math/48_RotateImage.py)
* 043. [Multiply Strings](Math/43_MultiplyStrings.py)
* 050. [Pow(x, n)](Math/50_Pow.py)
* 060. [Permutation Sequence](Math/60_PermutationSequence.py)
* 066. [Plus One](Math/66_PlusOne.py)
* 069. Sqrt(x)
* 166. [Fraction to Recurring Decimal](Math/166_FractionToRecurringDecimal.py)
* 168. [Excel Sheet Column Title](Math/168_ExcelSheetColumnTitle.py)
* 171. [Excel Sheet Column Number](Math/171_ExcelSheetColumnNumber.py)
* 172. [Factorial Trailing Zeroes](Math/172_FactorialTrailingZeroes.py)
* 179. [Largest Number](Math/179_LargestNumber.py)
* 202. [Happy Number](Math/202_HappyNumber.py)
* 204. [Count Primes](Math/204_CountPrimes.py)
* 223. [Rectangle Area](Math/223_RectangleArea.py)
* 233. [Number of Digit One](Math/233_NumberOfDigitOne.py)
* 238. [Product of Array Except Self](Math/238_ProductOfArrayExceptSelf.py)
* 258. [Add Digits](Math/258_AddDigits.py)
* 263. [Ugly Number](Math/263_UglyNumber.py)
* 273. [Integer to English Words](Math/273_IntegerToEnglishWords.py)
* 292. [Nim Game](Math/292_NimGame.py)
* 326. [Power of Three](Math/326_PowerOfThree.py)
* 319. [Bulb Switcher](Math/319_BulbSwitcher.py)
* 335. [Self Crossing](Math/335_SelfCrossing.py)
* 343. [Integer Break](Math/343_IntegerBreak.py)

3 https://leetcode.com/problems/longest-substring-without-repeating-characters/
维护一个不含重复字符的滑动窗口。需要记录每个字符最后出现的位置，当遇到重复字符的时候，就把窗口首部调到上一次出现这个字符的下一个位置。

76 https://leetcode.com/problems/minimum-window-substring/
滑动窗口题。维护一个包含t中所有字符的最小滑动窗口，首先用一个hashmap记录所有t中的字符和出现次数，在s中每遇到一次计数器加一，找到了符合条件的窗口后，尝试向右移动窗口左指针，直到恰好能够满足条件为止。更新当前最小滑动窗口。

209 https://leetcode.com/problems/minimum-size-subarray-sum/
维护一个大于等于sum的最小滑动窗口。

239 https://leetcode.com/problems/sliding-window-maximum/
求滑动窗口中的最大值。(1) 使用ordered_map，动态更新，取首元素, NlogK。(2) 维护一个指向最大值的指针，当指针不再在窗口内时，向后移动这一指针到合适的位置。最坏时间复杂度是O（NK），但均摊表现比1还要好。（3）使用单调队列，维护单调递减的队列，队首不再在窗口内时弹出队首，有更大的元素弹出队尾。当前最大元素为队尾元素。接近O（N）。

424  https://leetcode.com/problems/longest-repeating-character-replacement/
维护一个最多包含k个额外字符的滑动窗口。需要记录当前出现次数最多字符的出现次数来判断窗口是否合法，如果超过了，就把首指针向后挪一位，同时更新最多出现次数。对每个合法窗口，取其中的最大值。

438 https://leetcode.com/problems/find-all-anagrams-in-a-string
主要思路是维护两个hashmap,一个记录期望出现的字符，一个记录当前出现的字符。
当前出现的字符随着窗口滚动不停更新，每次移动窗口后，都判断当前窗口是否满足条件。同时维护一个满足条件的count变量，通过比较当前出现字符和期望出现字符的个数来更新，当count等于期望字符串的长度时，意味着当前窗口满足条件。

480 https://leetcode.com/problems/sliding-window-median/
求滑动窗口的中位值。可以维护一个mutilmap。

576 https://leetcode.com/problems/permutation-in-string/
同438。

904 https://leetcode.com/problems/fruit-into-baskets/
查找最多出现k个字符的最大滑动窗口。可以维护一个包含所有字符出现最后下标的哈希表，每次查到数字超过k个，就把begin指针移到最小的最后出现下标的下一个。

978 https://leetcode.com/problems/longest-turbulent-subarray/
检查前后两个数字是否满足大于或者小于的关系，如果满足计数器加一，否则清空。扫描两次处理奇数偶数情况。

992 https://leetcode.com/problems/subarrays-with-k-different-intergers
计算滑动窗口中恰好出现k个不同字符的窗口数目。这道题的一个可以通过的暴力算法是n2的，找到一个满足条件的滑动窗口后，把begin指针后移，直到不到满足为止。统计出现个数。我们需要维护一个可以快速找到k个数字中，最后出现位置最早的那个数字出现的位置，使我们能够快速移动begin指针。

1004 https://leetcode.com/problems/max-consecutive-ones-iii/
维护最多包含k个0的滑动窗口，一旦超过了k个0，把队首的0 pop出来。不断更新当前滑动窗口中的数据个数，并取最大值返回即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

20、数学

6 https://leetcode.com/problems/zigzag-conversion/
类似编码解码一样的zigzag打印。

43 https://leetcode.com/problems/multiply-strings/
字符串计算乘法。

48 https://leetcode.com/problems/rotate-image/
打印旋转矩阵。

54 https://leetcode.com/problems/spiral-matrix/
打印旋转矩阵。

223 https://leetcode.com/problems/rectangle-area/
计算矩形面积。

228 https://leetcode.com/problems/summary-ranges/
连续数字打印成特定格式。

537 https://leetcode.com/problems/complex-number-multiplication/
计算复数相加。

885 https://leetcode.com/problems/spiral-matrix-iii/
打印旋转矩阵。

1104 https://leetcode.com/problems/path-in-zigzag-labelled-binary-tree/
zigzag打印2^n.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

21、有穷自动 DFA算法

* 065. [Valid Number](DFA/65_ValidNumber.py)
1

22、并查集

128 https://leetcode.com/problems/longest-consecutive-sequence/
把相邻元素合并到一个集合中，取数量最大的那个集合作为结果。哈希的做法是先把所有值放到哈希里，对每个值查找n+1和n-1的值有哪些，记录两端长度。找到了从哈希表中移除。

684 https://leetcode.com/problems/redundant-connection/
类似于最小生成树。每遇到一对节点把它们Union一下，如果已经在一个集合了，就返回这对边，说明是要被去掉的。

924 https://leetcode.com/problems/minimize-malware-spread
优先去除所在集合只包含它一个初始节点的初始节点，如果有多个这样的节点，取集合较大的。如果集合大小一样，或者该集合包含了多个初始节点，取下标最小的。
1
2
3
4
5
6
7
8

23、区间重叠

56 https://leetcode.com/problems/merge-intervals/
先排序，再逐个检查当前区间能否和结果队列中最后一个区间合并。

57 https://leetcode.com/problems/insert-interval/
先把在新区间之前的都加入结果，和新区间存在重叠的取最大最小作为边界，在新区间之后的都加入结果。

435 https://leetcode.com/problems/non-overlapping-intervals/
先排序，一旦检测到重叠，移除end位置比较大的元素。

452 https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/
维护一个当前最小的重叠区域，如果新的区间和这个区间重叠，那么缩小这个区间，否则重置。每重置一次计数加一。
1
2
3
4
5
6
7
8
9
10
11

24、其它

* 030. [Substring with Concatenation of All Words](Combination/30_SubstringWithConcatenationOfAllWords.py)
* 037. [Sudoku Solver](Combination/37_SudokuSolver.py)
* 140. [Word Break II](Combination/140_WordBreakII.py)
* 146. [LRU Cache](Combination/146_LRUCache.py)
* 300. [Longest Increasing Subsequence](Combination/300_LongestIncreasingSubsequence.py)
* 324. [Wiggle Sort II](Combination/324_WiggleSortII.py)
* 329. [Longest Increasing Path in a Matrix](Combination/329_LongestIncreasingPathInMatrix.py)
* 355. [Design Twitter](Combination/355_DesignTwitter.py)
* 
* 220. [Contains Duplicate III](220_ContainsDuplicateIII.py)
* 229. [Majority Element II](Others/229_MajorityElementII.py)
* 239. [Sliding Window Maximum](Others/239_SlidingWindowMaximum.py)
* 284. [Peeking Iterator](Others/284_PeekingIterator.py)
* 307. [Range Sum Query - Mutable](Others/307_RangeSumQueryMutable.py)    
1
2
3
4
5
6
7
8
9
10
11
12
13
14

25、参考

《[C++]Leetcode超高效刷题顺序及题目详解笔记（持续更新中）》
《leetcode题型分类与总结》
《关于LeetCode刷题及题目列表归纳》

【精】：《Leetcode 题解 - 目录.md》
【精】：《数据结构与算法系列 目录》
《小浩算法》
《每天刷个算法题》
《Leetcode 分类顺序表》

《(小甲鱼）数据结构与算法（全99讲完结版）_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili》