Leetcode 題型分類與解題方向
我發現這些 leetcode 好像依照不同的題型會有類似的解法，所以請 AI 幫我統整每一個種類題型的解題方向。大致上可以分成 9 種類型，如果遇到這類型可以先往每個類別中列出的解題方法來思考，在這裡做個紀錄
1. Array Problems
- Two Pointers: Used for problems like finding pairs, subarrays, or for partitioning arrays.
- Example: 283 (Move Zeroes), 11 (Container With Most Water).
- Sorting: Often needed before applying binary search or two-pointer techniques.
- Example: 56 (Merge Intervals).
- Binary Search: For finding specific elements or ranges in a sorted array.
- Example: 34 (Find First and Last Position of Element).
2. String Problems
- Sliding Window: Useful for finding the longest substring with certain properties.
- Example: 3 (Longest Substring Without Repeating Characters).
- HashMap/HashSet: For character frequency counts or to check for unique characters.
- Example: 387 (First Unique Character in a String).
3. Linked List Problems
- Fast and Slow Pointers: For detecting cycles or finding the middle of the list.
- Example: 141 (Linked List Cycle), 19 (Remove Nth Node From End of List).
- Reversing a Linked List: Important for palindrome checks or simply reversing the list.
- Example: 206 (Reverse Linked List).
4. Tree/Graph Problems
- Depth-First Search (DFS): For traversing nodes and backtracking.
- Example: 104 (Maximum Depth of Binary Tree), 17 (Letter Combinations of a Phone Number).
- Breadth-First Search (BFS): Useful for finding the shortest path or level order traversal.
- Example: 102 (Binary Tree Level Order Traversal).
- Dynamic Programming on Trees: For problems like finding the maximum path sum.
- Example: 124 (Binary Tree Maximum Path Sum).
5. Dynamic Programming
- Knapsack Problems: Problems related to finding the optimal subset.
- Example: 322 (Coin Change).
- Fibonacci Sequence: Used in problems like climbing stairs or house robbing.
- Example: 70 (Climbing Stairs), 198 (House Robber).
- Grid DP: For pathfinding in grids (e.g., unique paths, minimum path sum).
- Example: 62 (Unique Paths).
6. Backtracking
- Generating Combinations/Permutations: Used when you need to explore all possibilities.
- Example: 22 (Generate Parentheses), 39 (Combination Sum).
- Pruning: Often, you can optimize backtracking by skipping unnecessary paths.
- Example: 51 (N-Queens).
7. Greedy Algorithms
- Interval Scheduling: Choosing the best option at each step for problems like merging intervals.
- Example: 452 (Minimum Number of Arrows to Burst Balloons).
- Coin Change Problem: Choosing the largest denomination first.
- Example: 455 (Assign Cookies).
8. Bit Manipulation
- XOR Operations: Commonly used in problems involving pairs or unique elements.
- Example: 136 (Single Number).
- Bitwise Shifts: Useful for checking or setting specific bits.
- Example: 190 (Reverse Bits).
9. Math Problems
- Number Theory: Problems involving prime numbers, GCD/LCM, or modulo operations.
- Example: 50 (Pow(x, n)), 326 (Power of Three).
- Simulation: Simulating the process described in the problem.
- Example: 415 (Add Strings), 29 (Divide Two Integers).
AI 建議:
By recognizing these patterns, you can often apply similar strategies across different problems, making it easier to solve new ones. If you'd like a deeper dive into any of these categories or specific problem examples, feel free to ask!
