数组题
LeetCode 001 Two Sum
LeetCode 2073 Time Needed to Buy Tickets
整数题
整洁题
LeetCode 273 Integer to English Words
LeetCode 054 Spiral Matrix
LeetCode 048 Rotate Image
LeetCode 166 Fraction to Recurring Decimal
LeetCode 008 String to Integer (atoi) 合法整数
LeetCode 065 Valid Number 合法小数指数
Map
LeetCode 003 Longest Substring Without Repeating Characters
LinkedList
注意事项： [4步]
- fake_node
- while it or it.next
- 删除节点.next = None
- it = it.next
快慢指针找循环，找中点(注意中位数有1-2个, 用fast是否为None来判断)
LeetCode 142 Linked List Cycle II
LeetCode 234 Palindrome Linked List
反转LL及其模板
LeetCode 206 Reverse Linked List
LeetCode 092 Reverse Linked List II
其他：
LeetCode 021 Merge Two Sorted Lists
LeetCode 002 Add Two Numbers
LeetCode 138 Copy List with Random Pointer
LeetCode 023 Merge k Sorted Lists
Stack
递减栈
适用条件： 数组元素之间大小关系(包括相等)且顺序不能变，可以动态处理(一个个处理)
Stack
LeetCode 503 Next Greater Element II
LeetCode 042 Trapping Rain Water
LeetCode 316 Remove Duplicate Letters
LeetCode 1209 Remove All Adjacent Duplicates in String II
LeetCode 239 Sliding Window Maximum
BST的非递归遍历
BST的非递归中序，前序，后序遍历
LeetCode 272 Closest Binary Search Tree Value II
Iterator题目基本是List转Stack
LeetCode 173 Binary Search Tree Iterator
Heap
Heap
LeetCode 347 Top K Frequent Elements
LeetCode 253 Meeting Rooms II endTime的Heap (最常见)
LeetCode 218 The Skyline Problem 高度的Heap
Heap + BFS
LeetCode 264 Ugly Number II
LeetCode 373 Find K Pairs with Smallest Sums
LeetCode 378 Kth Smallest Element in a Sorted Matrix
数据结构
题目大多都是HashMap + LL 或 HashMap + List
LeetCode 1429 First Unique Number
LeetCode 380 Insert Delete GetRandom O(1)
LeetCode 146 LRU Cache
LeetCode 460 LFU Cache
Trie
LeetCode 588 Design In-Memory File System
LeetCode 211 Design Add and Search Words Data Structure search含TrieNode参数 + DFS
LeetCode 212 Word Search II search含TrieNode参数
Iterator
LeetCode 251 Flatten 2D Vector
LeetCode 281 Zigzag Iterator
LeetCode 341 Flatten Nested List Iterator
LeetCode 173 Binary Search Tree Iterator
数组二分法:
LeetCode 981 Time Based Key-Value Store
LeetCode 2080 Range Frequency Queries
其他：
LeetCode 155 Min Stack
Two pointers
同向双指针： 应用条件需要连续一段达到target，然后连续一段达不到target，梅花间竹
Two pointers
LeetCode 243 Shortest Word Distance
LeetCode 209 Minimum Size Subarray Sum
LeetCode 438 Find All Anagrams in a String
LeetCode 076 Minimum Window Substring
LeetCode 340 Longest Substring with At Most K Distinct Characters 最长类型
LeetCode 395 Longest Substring with At Least K Repeating Characters 最长类型
相向双指针
Hash(value -> index, value -> count)适用条件： 数组元素之间的关系，相加相减等于target，复杂度为O(n)
LeetCode 1010 Pairs of Songs With Total Durations Divisible by 60 value -> count变体
Two points适用条件： 数组元素之间的关系，相加相减等于target，元素相等或有序，复杂度为O(n)
回文题首先考虑用相向双指针
LeetCode 125 Valid Palindrome
LeetCode 680 Valid Palindrome II
Sorting
Quick sort
Partition的应用, O(1)空间且注意循环外处理最后一部分：
LeetCode 283 Move Zeroes
LeetCode 443 String Compression
LeetCode 075 Sort Colors
LeetCode 696 Count Binary Substrings
LeetCode 041 First Missing Positive
Quick select
Merge sort
LeetCode 244 Shortest Word Distance II
LeetCode 315 Count of Smaller Numbers After Self
LeetCode 493 Reverse Pairs
Bucket sort
LeetCode 347 Top K Frequent Elements
LeetCode 2080 Range Frequency Queries
Binary Search
Binary Search
LeetCode 278 First Bad Version
LeetCode 153 Find Minimum in Rotated Sorted Array
LeetCode 033 Search in Rotated Sorted Array
LeetCode 540 Single Element in a Sorted Array
LeetCode 275 H-Index II
Binary Select
适用条件：试某个数接近于最优解，全部试一遍就是*logn的复杂度
LeetCode 378 Kth Smallest Element in a Sorted Matrix
LeetCode 004 Median of Two Sorted Arrays
Tree
检查方法： None, 一个节点，两个节点(只有左或右)，三个节点
nonlocal方法，不用定义全局变量见LeetCode 543 Diameter of Binary Tree
LeetCode 104 Maximum Depth of Binary Tree
LeetCode 230 Kth Smallest Element in a BST
LeetCode 114 Flatten Binary Tree to Linked List
LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal
LeetCode 314 Binary Tree Vertical Order Traversal
方法：用Map记录子节点到父节点关系等价于形成双向Tree
LeetCode 1650 Lowest Common Ancestor of a Binary Tree III
LeetCode 236 Lowest Common Ancestor of a Binary Tree
LeetCode 863 All Nodes Distance K in Binary Tree
BFS
适用条件： 可行性，最大和最小值且每个点不能重复访问
注意事项： [3步]建图没有边的节点也要加到邻接表, 输入参数不等于迭代参数, 返回-1,
图BFS
LeetCode 200 Number of Islands 连通集问题, 对所有节点BFS
LeetCode 1048 Longest String Chain 多源最长路劲，对所有节点BFS
LeetCode 1197 Minimum Knight Moves
LeetCode 133 Clone Graph
LeetCode 297 Serialize and Deserialize Binary Tree
LeetCode 127 Word Ladder
LeetCode 301 Remove Invalid Parenthesess
LeetCode 055 Jump Game
LeetCode 1654 Minimum Jumps to Reach Home
LeetCode 286 Walls and Gates 多始点一次BFS
LeetCode 490 The Maze 一组节点作为一层的BFS
LeetCode 815 Bus Routes 一组节点作为一层的BFS
[LeetCode 1293 Shortest Path in a Grid with Obstacles Elimination] 多状态BFS
拓扑排序
LeetCode 210 Course Schedule II
LeetCode 310 Minimum Height Trees
LeetCode 269 Alien Dictionary
DFS
适用条件： 种数(优先用DP，次选用DFS)，可行性
图DFS/填位法
排列
LeetCode 526 Beautiful Arrangement
组合
LeetCode 039 Combination Sum
LeetCode 077 Combinations
LeetCode 216 Combination Sum III
LeetCode 017 Letter Combinations of a Phone Number 填位法
LeetCode 051 N-Queens 填位法
LeetCode 037 Sudoku Solver 填位法, 单边DFS + 循环DFS
LeetCode 093 Restore IP Addresses 分割型，结果分组型DFS
LeetCode 291 Word Pattern II 分割型, 单边DFS + 循环DFS
LeetCode 079 Word Search 图DFS + 分割型
LeetCode 126 Word Ladder II 图DFS
记忆性搜索
LeetCode 140 Word Break II 分割型
LeetCode 095 Unique Binary Search Trees II Catalan型DFS
LeetCode 241 Different Ways to Add Parentheses Catalan型DFS
DP
适用条件： 最值，种数，可行性。输入数据有序,暴力法非多项式
注意事项： [5步]多1, 初始化, 多1, 少1, 答案
DP
LeetCode 070 Climbing Stairs 单序列型
LeetCode 091 Decode Ways 单序列型
LeetCode 198 House Robber 单序列型
LeetCode 377 Combination Sum IV 数值到个数DP
LeetCode 322 Coin Change 数值到个数DP
LeetCode 518 Coin Change 2 数值到个数DP(元素无序)
LeetCode 063 Unique Paths II 坐标型DP
LeetCode 064 Minimum Path Sum 坐标型DP
LeetCode 221 Maximal Square 坐标型DP
LeetCode 174 Dungeon Game 坐标型DP
LeetCode 718 Maximum Length of Repeated Subarray 匹配型DP
LeetCode 300 LIS 匹配型DP
LeetCode 139 Word Break 匹配型DP
LeetCode 072 Edit Distance 匹配型DP
LeetCode 044 Wildcard Matching 匹配型DP
LeetCode 010 Regular Expression Matching 匹配型DP
LeetCode 516 Longest Palindromic Subsequence 区间型DP
LeetCode 312 Burst Balloons 区间型DP
Karat 002 Longest Common Continuous Subarray 打印路径
LeetCode 300 Longest Increasing Subsequence 打印路径
LeetCode 368 Largest Divisible Subset 打印路径
LeetCode 1143 Longest Common Subsequence 打印路径
多状态DP需要同时赋值
LeetCode 152 Maximum Product Subarray 多状态DP
LeetCode 926 Flip String to Monotone Increasing 多状态DP
LeetCode 256 Paint House 多状态DP
多状态DP-fg双函数(g为累计DP) - 和前状态不能相邻
LeetCode 337 House Robber III 多状态DP-fg双函数
LeetCode 309 Best Time to Buy and Sell Stock with Cooldown 多状态DP-fg双函数
Floyd
LeetCode 329 Longest Increasing Path in a Matrix
其他
动态计算连接数，其他均用BFS
Union Find
LeetCode 721 Accounts Merge
[双向BFS]LeetCode 127 Word Ladder
[线段树]LeetCode 729 My Calendar I
最大的k个/最大的前k个数(无序数值数组)
LeetCode 347 Top K Frequent Elements
优先考虑Heap，因为Heap支持动态和静态数据。适用范围最广，动态包括Data stream，不将整个数组读入从而优化复杂度
LeetCode 295 Find Median from Data Stream
LeetCode 378 Kth Smallest Element in a Sorted Matrix
Binary select，数值法计算个数，不能用于动态，实现较复杂
LeetCode 004 Median of Two Sorted Arrays
Quick select, binary select的特殊版，只能用于一维数组
数组区间内动态最大值最小值或保留数组顺序(数值数组)
由于保留顺序，首选stack
LeetCode 2104 Sum of Subarray Ranges
二维坐标最短距离
BFS首选，然后DP。若状态转移是无序用BFS，否则DP(可从上到下，从左到右)
BFS
LeetCode 1197 Minimum Knight Moves
LeetCode 909 Snakes and Ladders
DP
LeetCode 174 Dungeon Game 坐标型DP
累计思想
将相连的批量计算提高效率或者满足累计条件
LeetCode 032 Longest Valid Parentheses 统计左括号个数保证其一直为非负数
LeetCode 134 Gas Station 保证gas一直为非负数
数组的presum
加入presum[0] = 0
LeetCode 696 Count Binary Substrings
LeetCode 560 Subarray Sum Equals K
LeetCode 238 Product of Array Except Self
子矩阵的presum
同数组，presum矩阵大小为长度 + 11
2
3res = presum[x][y] - left - top + diag
presum[i][j] = row_sum + (presum[i - 1][j] if i > 0 else 0)
LeetCode 304 Range Sum Query 2D - Immutable
LeetCode 427 Construct Quad Tree
括号题或者字符串运算题
括号题或者字符串运算题优先用Stack
LeetCode 020 Valid Parentheses
LeetCode 032 Longest Valid Parentheses
LeetCode 1249 Minimum Remove to Make Valid Parentheses 括号下标
LeetCode 678 Valid Parenthesis String
LeetCode 022 Generate Parentheses
LeetCode 071 Simplify Path
字符串运算题
LeetCode 227 Basic Calculator II
LeetCode 224 Basic Calculator
LeetCode 394 Decode String
游戏题
数据结构设计 + 模拟
[LeetCode 348 Design Tic-Tac-Toe] 设计游戏
LeetCode 051 N-Queens 求游戏所有解
LeetCode 037 Sudoku Solver 求游戏是否有解
区间重合题
条件区间重合且区间始点有序。用端点排序法(更常用)或Heap(处理重合情况下的计算)
LeetCode 253 Meeting Rooms II
LeetCode 056 Merge Intervals
LeetCode 759 Employee Free Time
LeetCode 1235 Maximum Profit in Job Scheduling
LeetCode 871 Minimum Number of Refueling Stops
LeetCode 218 The Skyline Problem 端点排序法 + Heap
所有子串和子数组
用presum, stack, DP
LeetCode 560 Subarray Sum Equals K
LeetCode 696 Count Binary Substrings
LeetCode 907 Sum of Subarray Minimums
LeetCode 2104 Sum of Subarray Ranges
Leetcode 828 Count Unique Characters of All Substrings of a Given String
26字母存储法
条件，若题目含所有字母，且求最值，需要存储每个字母对应的结果
LeetCode 395 Longest Substring with At Least K Repeating Characters
LeetCode 1857 Largest Color Value in a Directed Graph
水王法
candidate取首元素，遍历每一个元素，若candidate不符合条件就换成当前元素为candidate
LeetCode 169 Majority Element
LeetCode 277 Find the Celebrity
LeetCode 134 Gas Station
Word相关题目
DFS: word pattern, word search
BFS: word ladder
DP: word break
