Leetcode 刷题顺序补正

中文互联网上传播的这份刷题顺序应该是来自某个英文课程, 但里面大部分题Leetcode上有, 所以被以讹传讹为”Leetcode刷题顺序”了。这里做一点笔记和修正, 仅供参考。

1. 滑动窗口

Maximum Sum Subarray of Size K (medium) LC325

Smallest Subarray with a given sum (easy) 查无此题

Longest Substring with K Distinct Characters (medium) LC340

Fruits into Baskets (medium) LC904

No-repeat Substring (hard) LC3

Longest Substring with Same Letters after Replacement (medium) LC424

Longest Subarray with Ones after Replacement (medium) LC1004

2. 双指针

Pair with Target Sum (easy) LC494(x) 面试题 16.24(?)

Remove Duplicates (easy) LC26

Squaring a Sorted Array (easy) LC977

Triplet Sum to Zero (medium) LC15

Triplet Sum Close to Target (medium) LC16

Triplets with Smaller Sum (medium) LC259(LOCKED)

Subarrays with Product Less than a Target (medium) LC713

Dutch National Flag Problem (medium) LC75 (真的是双指针吗)

3. 快慢指针

LinkedList Cycle (easy) LC141

Start of LinkedList Cycle (medium) LC142

Happy Number (medium) LC202

Middle of the LinkedList (easy) LC876

4. 区间合并

Merge Intervals (medium) LC56 #排序 #差分数组

Insert Interval (medium) LC57

Intervals Intersection (medium) LC986

Non Overlapping Intervals (medium) LC435 联动LC300最长递增子序列

5. 循环排序

Cyclic Sort (easy) 查无此题

Find the Missing Number (easy) LC268

Find all Missing Numbers (easy) LC448

First Missing Positive (Hard) LC 41

Find the Duplicate Number (medium) LC287 (联动3.LC142快慢指针解法)

Find all Duplicate Numbers (easy) LC442

6. 链表翻转

Reverse a LinkedList (easy) LC206

Reverse a Sub-list (medium) LC92

Reverse every K-element Sub-list (hard) LC25 (联动LC92, 有这个前置方法就是简单题)

7. 树上BFS

Binary Tree Level Order Traversal (medium) LC102

Reverse Level Order Traversal (medium) LC107

Zigzag Traversal (medium) LC103

Level Averages in a Binary Tree (easy) LC637

Minimum Depth of a Binary Tree (easy) LC111

Level Order Successor (easy) 查无此题

https://www.geeksforgeeks.org/level-order-successor-of-a-node-in-binary-tree/

Connect Level Order Siblings (medium)

https://interviewdaemon.com/courses/binary-tree-breadth-first-search/lessons/connect-all-level-order-siblings-in-binary-tree/

8. 树上DFS

Binary Tree Path Sum (hard) LC124

All Paths for a Sum (medium) LC113

Sum of Path Numbers (medium) LC437

Path With Given Sequence (medium) 查无此题

Count Paths for a Sum (medium) LC437 ?

9. 双堆

Find the Median of a Number Stream (medium) LC295

Sliding Window Median (hard) LC480

Maximize Capital (hard) LC502

10. 子集 多重DFS

Subsets (medium) LC78

Subsets With Duplicates (medium) LC90

Permutations (medium) LC46

String Permutations by changing case (medium) LC784

Balanced Parentheses (hard) ? 分类错误 查无此题?

Unique Generalized Abbreviations (hard) LC320 LOCKED

https://blog.csdn.net/jmspan/article/details/51231829

11. 二分变体

Order-agnostic Binary Search (easy) // 升序/降序未知的二分搜索? 通过首尾判断一下升降序即可 查无此题

Ceiling of a Number (medium) 查无此题

Next Letter (medium) 查无此题

Number Range (medium) 查无此题

Search in a Sorted Infinite Array (medium) 查无此题

https://www.geeksforgeeks.org/find-position-element-sorted-array-infinite-numbers/

Minimum Difference Element (medium) 查无此题

Bitonic Array Maximum (easy) 查无此题

https://www.includehelp.com/icp/maximum-value-in-a-bitonic-array.aspx

12. 前K个

Top ‘K’ Numbers (easy) 查无此题

Kth Smallest Number (medium) LC215

‘K’ Closest Points to the Origin (easy) LC973

Connect Ropes (easy) 查无此题

https://www.geeksforgeeks.org/connect-n-ropes-minimum-cost/

Top ‘K’ Frequent Numbers (medium) LC347

Frequency Sort (medium) LC451 最大算例对List用sort会有奇怪的错序问题

Kth Largest Number in a Stream (easy) LC703

‘K’ Closest Numbers (medium) LC658 #二分

Maximum Distinct Elements (medium) 查无此题

https://www.geeksforgeeks.org/maximum-distinct-elements-removing-k-elements/

Sum of Elements (hard) LC327? 前缀和O(n^2) 归并排序O(nlogn)

Rearrange String (medium) LC767?

13. 多路归并

Merge K Sorted Lists (hard) LC23 顺序合并, 二分归并合并, 使用优先队列合并

Kth Smallest Number in M Sorted Lists (Medium) 查无此题, 应该与下题类似

Kth Smallest Number in a Sorted Matrix (medium) LC378 堆/优先队列

Smallest Number Range (hard) LC632 归并思想

https://blog.csdn.net/Dora_Yh/article/details/78079152

14. 0-1背包

0/1 Knapsack (medium) 经典01背包

Equal Subset Sum Partition (medium) LC416

Partition To K Equal Sum Subsets (medium) LC698 #记忆化搜索 #回溯

Minimum Subset Sum Difference (hard) 查无此题 // ↓自顶向下DP, 递归 // 与LC416类似, 不同的是416要求两划分的子集和相等, 这题要求差最小

https://medium.com/swlh/dynamic-programming-0-1-knapsack-python-code-222e607a2e8

Zero and One (hard) LC474 多重背包

15. 拓扑排序

Topological Sort (medium)

Tasks Scheduling (medium) LC207

Tasks Scheduling Order (medium) LC210

All Tasks Scheduling Orders (hard) 查无此题

Alien Dictionary (hard) LOCKED

https://xiaoguan.gitbooks.io/leetcode/content/LeetCode/269-alien-dictionary-hard.html

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

https://github.com/asutosh97/educative-io-contents/blob/master/Grokking%20Dynamic%20Programming%20Patterns%20for%20Coding%20Interviews.md

1. 0/1 Knapsack, 0/1 背包,6 个题

0/1 Knapsack,0/1 背包问题

Equal Subset Sum Partition,相等子集划分问题

Subset Sum,子集和问题 (存在性可以构造和数组记忆+遍历子集, 求个数最好DP)

Minimum Subset Sum Difference,子集和的最小差问题

Count of Subset Sum,相等子集和的个数问题 见上文, 可以暴力, 最好DP

Target Sum,寻找目标和的问题 LC494

2. Unbounded Knapsack,无限背包,5 个题

Unbounded Knapsack,无限背包

Rod Cutting,切钢条问题

https://www.jianshu.com/p/06c1ea9f01d2 见scratch_30, 应该正确

Coin Change,换硬币问题 LC322

Minimum Coin Change,凑齐每个数需要的最少硬币问题

Maximum Ribbon Cut,丝带的最大值切法 #完全背包, 注意转移条件

https://blog.csdn.net/nobleman__/article/details/79357609

3. Fibonacci Numbers,斐波那契数列,6 个题

Fibonacci numbers,斐波那契数列问题 LC509

Staircase,爬楼梯问题 LC70

Number factors,分解因子问题

https://blog.csdn.net/qq_42898536/article/details/109523993

Minimum jumps to reach the end,蛙跳最小步数问题

https://leetcode.com/discuss/interview-question/algorithms/125002/minimum-number-of-jumps

https://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array

Minimum jumps with fee,蛙跳带有代价的问题 LOCKED, 多一个代价函数, 多重背包?

https://www.educative.io/courses/grokking-dynamic-programming-patterns-for-coding-interviews/7nDNy6JDP1G

House thief,偷房子问题

https://www.geeksforgeeks.org/find-maximum-possible-stolen-value-houses/

4. Palindromic Subsequence,回文子系列,5 个题

Longest Palindromic Subsequence,最长回文子序列 LC516

Longest Palindromic Substring,最长回文子字符串 LC5

Count of Palindromic Substrings,回文子字符串的个数问题 LC647?

Minimum Deletions in a String to make it a Palindrome,怎么删掉最少字符构成回文 // 找到最长回文子序列的长度, 用总长度删去即可, 联动LC516

https://www.geeksforgeeks.org/minimum-number-deletions-make-string-palindrome/

Palindromic Partitioning,怎么分配字符,形成回文 LC131 回溯??? LC132 DP

5. Longest Common Substring,最长子字符串系列,13 个题

Longest Common Substring,最长相同子串

https://hjweds.gitbooks.io/leetcode/content/longest-common-substring.html

Longest Common Subsequence,最长相同子序列 LC1143

Minimum Deletions & Insertions to Transform a String into another,字符串变换 // 编辑距离

https://www.geeksforgeeks.org/minimum-number-deletions-insertions-transform-one-string-another/

Longest Increasing Subsequence,最长上升子序列 LC300

Maximum Sum Increasing Subsequence,最长上升子序列和 // 参考LC491

Shortest Common Super-sequence,最短超级子序列 LC1092

Minimum Deletions to Make a Sequence Sorted,最少删除变换出子序列

https://www.geeksforgeeks.org/minimum-number-deletions-make-sorted-sequence/

Longest Repeating Subsequence,最长重复子序列

https://www.geeksforgeeks.org/longest-repeating-subsequence/

Subsequence Pattern Matching,子序列匹配 LC792

Longest Bitonic Subsequence,最长字节子序列

https://www.geeksforgeeks.org/longest-bitonic-subsequence-dp-15/

Longest Alternating Subsequence,最长交差变换子序列

https://www.geeksforgeeks.org/longest-alternating-subsequence/

Edit Distance,编辑距离 LC72

Strings Interleaving,交织字符串 LC97