经典问题整理

基础问题

• 二叉树的遍历 / Morris 遍历
  1. 94. Binary Tree Inorder Traversal
  2. 144. Binary Tree Preorder Traversal
  3. 145. Binary Tree Postorder Traversal
  4. 102. Binary Tree Level Order Traversal
  5. 589. N-ary Tree Preorder Traversal
  6. 590. N-ary Tree Postorder Traversal
• 二叉树的性质
  1. 1361. Validate Binary Tree Nodes
• 二叉搜索树
  1. 285. Inorder Successor in BST
• 字典树
  1. 208. Implement Trie (Prefix Tree)
• 排序 / 顺序统计
  1. 215. Kth Largest Element in an Array
  2. 912. Sort an Array

非常经典

• 单调栈
  1. 84. Largest Rectangle in Histogram
  2. 962. Maximum Width Ramp
  3. 795. Number of Subarrays with Bounded Maximum
• 单调队列
  1. 239. Sliding Window Maximum
  2. 683. K Empty Slots
  3. 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
• 双指针
  1. 443. String Compression
  2. 31. Next Permutation
  3. 1498. Number of Subsequences That Satisfy the Given Sum Condition
• KMP
  1. 1392. Longest Happy Prefix
• 字典树
  1. 1707. Maximum XOR With an Element From Array
• 区间问题
  1. 56. Merge Intervals
  2. 57. Insert Interval
  3. 1272. Remove Interval
• 扫描线
  1. 218. The Skyline Problem
• BFS
  1. 815. Bus Routes
• 滑动窗口
  1. 992. Subarrays with K Different Integers
• 并查集
  1. 803. Bricks Falling When Hit
  2. 765. Couples Holding Hands
• 动态规划
  • 一般 dp
    1. 10. Regular Expression Matching
    2. 44. Wildcard Matching
  • 区间 dp
    1. 471. Encode String with Shortest Length
    2. 1039. Minimum Score Triangulation of Polygon
  • 背包 dp
    1. 1774. Closest Dessert Cost
    2. 1049. Last Stone Weight II
  • 子集 dp
    1. 465. Optimal Account Balancing
  • 悬线 dp
    1. 85. Maximal Rectangle
  • 概率 dp
    1. 688. Knight Probability in Chessboard
  • 数位 dp
    1. 902. Numbers At Most N Given Digit Set
    2. 1067. Digit Count in Range
    3. 600. Non-negative Integers without Consecutive Ones
  • 倍增 dp
    1. 466. Count The Repetitions
  • 划分 dp
    1. 1278. Palindrome Partitioning III
  • 优化
    • 前缀 / 后缀 优化
      1. 265. Paint House II
    • 单调队列优化
      1. 1696. Jump Game VI
• 曼哈顿距离
  1. 1478. Allocate Mailboxes
• 矩阵相关
  1. 1504. Count Submatrices With All Ones
  2. 1727. Largest Submatrix With Rearrangements
  3. 1277. Count Square Submatrices with All Ones
• 二分搜索
  1. 4. Median of Two Sorted Arrays
  2. Acwing 1452. 寻找矩阵的极小值 / 1901. Find a Peak Element II
  3. 792. Number of Matching Subsequences
• 二分答案
  1. 875. Koko Eating Bananas
  2. 719. Find K-th Smallest Pair Distance
• 差分数组
  1. 995. Minimum Number of K Consecutive Bit Flips
  2. 1674. Minimum Moves to Make Array Complementary
• 优先队列
  1. 778. Swim in Rising Water
  2. 1786. Number of Restricted Paths From First to Last Node
• 贪心
  • Huffman
    1. 1199. Minimum Time to Build Blocks
  • 区间
    1. 1024. Video Stitching
    2. 630. Course Schedule III
    3. 1353. Maximum Number of Events That Can Be Attended
  • 其他
    1. 767. Reorganize String
    2. 1405. Longest Happy String
• 状态压缩
  1. 864. Shortest Path to Get All Keys
• 树状数组
  1. 493. Reverse Pairs
  2. 1782. Count Pairs Of Nodes
  3. 1409. Queries on a Permutation With Key
• 链表
  1. 287. Find the Duplicate Number
  2. 剑指 Offer 03. 数组中重复的数字
  3. 234. Palindrome Linked List
  4. 148. Sort List
• 等价变换
  1. Nowcoder. 有趣的排序
  2. Lintcode 307. Transform String
  3. Lintcode 313. Minimum Insertion
  4. 1354. Construct Target Array With Multiple Sums
• 栈
  1. 32. Longest Valid Parentheses
  2. 1190. Reverse Substrings Between Each Pair of Parentheses
• 树
  1. 536. Construct Binary Tree from String
  2. 222. Count Complete Tree Nodes
  3. 958. Check Completeness of a Binary Tree
  4. 285. Inorder Successor in BST
  5. 1530. Number of Good Leaf Nodes Pairs
• 深度优先搜索
  1. 1254. Number of Closed Islands
• 图论
  • 拓扑排序
    1. 207. Course Schedule
  • 最小生成树 / 并查集
    1. 1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
    2. 305. Number of Islands II
  • Floyed
    1. 399. Evaluate Division
  • Dijkstra
    1. 743. Network Delay Time
  • 二染色问题
    1. 785. Is Graph Bipartite?
  • NP 问题
    1. 753. Cracking the Safe
    2. 943. Find the Shortest Superstring
• 数学
  • 最大公因数
    1. 1808. Maximize Number of Nice Divisors
• LCA
  1. 1676. Lowest Common Ancestor of a Binary Tree IV
• 构造答案
  1. 667. Beautiful Arrangement II
  2. 1253. Reconstruct a 2-Row Binary Matrix
• 基数排序
  1. 164. Maximum Gap
• 哈希
  1. 1930. Unique Length-3 Palindromic Subsequences
• 滚动哈希
  1. 1923. Longest Common Subpath

有坑的问题

1. 152. Maximum Product Subarray
2. 665. Non-decreasing Array
3. 1497. Check If Array Pairs Are Divisible by k

冷门问题

• 随机化
  • 蓄水池抽样
    1. 382. Linked List Random Node
  • 拒绝采样法
    1. 478. Generate Random Point in a Circle
  • 概率分布
    1. 478. Generate Random Point in a Circle
  • 洗牌算法
    1. 384. Shuffle an Array
• 计算几何
  • 凸包
    1. 587. Erect the Fence
  • 最近点对
    1. Lintcode 966. 平面最近点对
• 图论
  • 最小生成树
    1. 1761. Minimum Degree of a Connected Trio in a Graph
  • 二分图匹配
    1. Luogu P3386 【模板】二分图最大匹配
  • Tarjan
    1. 1192. Critical Connections in a Network
  • 欧拉回路
    1. 2097. Valid Arrangement of Pairs
    2. 332. Reconstruct Itinerary
• Manacher
  1. 5. Longest Palindromic Substring
• 高斯消元
  1. Luogu P3389 【模板】高斯消元法