leetcode经典100题套路公式

### LeetCode Top 100 题目模式与解决方法 LeetCode 的 Top 100 经典题目涵盖了多种算法和数据结构的核心概念。以下是这些题目中的常见模式以及对应的解决方案。 #### 数据结构分类 1. **数组** 数组类问题是基础，通常涉及双指针、滑动窗口等技巧。 - 双指针用于处理有序数组或寻找特定条件下的两个数[^1]。 ```python def two_sum(nums, target): left, right = 0, len(nums) - 1 while left < right: current_sum = nums[left] + nums[right] if current_sum == target: return [left, right] elif current_sum < target: left += 1 else: right -= 1 return [] ``` 2. **链表** 链表操作常涉及到反转、删除节点等问题。 - 使用虚拟头结点简化边界情况的处理[^2]。 ```python class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def reverse_list(head): prev = None curr = head while curr is not None: temp = curr.next curr.next = prev prev = curr curr = temp return prev ``` 3. **栈与队列** 这些数据结构适用于括号匹配、BFS 和 DFS 等场景。 - BFS 常见于图遍历或者最短路径问题[^3]。 ```python from collections import deque def bfs(graph, start_node): visited = set() queue = deque([start_node]) while queue: node = queue.popleft() if node not in visited: visited.add(node) for neighbor in graph[node]: if neighbor not in visited: queue.append(neighbor) return list(visited) ``` 4. **树** 树形结构主要考察二叉搜索树 (BST) 特性和递归实现。 - 中序遍历可以验证 BST 是否合法[^4]。 ```python def is_valid_bst(root): stack, inorder = [], float('-inf') while stack or root: while root: stack.append(root) root = root.left root = stack.pop() if root.val <= inorder: return False inorder = root.val root = root.right return True ``` 5. **动态规划** 动态规划通过子问题分解来优化复杂度。 - 背包问题是一个典型的例子[^5]。 ```python def knapsack(weights, values, capacity): dp = [[0]*(capacity+1) for _ in range(len(values)+1)] for i in range(1, len(values)+1): for w in range(capacity+1): if weights[i-1] <= w: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1]) else: dp[i][w] = dp[i-1][w] return dp[-1][-1] ``` 6. **回溯法** 回溯法适合组合、排列等相关问题。 - N皇后问题展示了如何利用剪枝减少不必要的计算[^6]。 ```python def solve_n_queens(n): result = [] cols = set(); diag1 = set(); diag2 = set() def backtrack(row, path): if row == n: result.append(path[:]) return for col in range(n): d1 = row - col; d2 = row + col if col in cols or d1 in diag1 or d2 in diag2: continue cols.add(col); diag1.add(d1); diag2.add(d2) path.append('.'*col + 'Q' + '.'*(n-col-1)) backtrack(row+1, path) cols.remove(col); diag1.remove(d1); diag2.remove(d2) path.pop() backtrack(0, []) return result ``` 7. **贪心算法** 贪心策略在某些情况下能够快速找到全局最优解。 - 区间调度是最常见的应用之一[^7]。 ```python def interval_scheduling(intervals): intervals.sort(key=lambda x: x[1]) # Sort by end time. count = 0; last_end_time = float('-inf') for start, end in intervals: if start >= last_end_time: count += 1 last_end_time = end return count ``` 8. **位运算** 位运算是高效解决问题的一种方式。 - 找到只出现一次的数字可以通过异或完成[^8]。 ```python def single_number(nums): res = 0 for num in nums: res ^= num return res ``` 9. **字符串** 字符串处理经常需要用到 KMP 或者 Manacher 算法。 - 判断回文串可以用中心扩展法[^9]。 ```python def longest_palindrome(s): if not s: return "" def expand_around_center(left, right): while left >= 0 and right < len(s) and s[left]==s[right]: left -= 1; right += 1 return s[left+1:right] longest = "" for i in range(len(s)): odd = expand_around_center(i,i) even = expand_around_center(i,i+1) longer = odd if len(odd)>len(even) else even if len(longer) > len(longest): longest = longer return longest ``` #### 总结 以上列举了一些经典的 LeetCode 解决方案及其背后的理论依据。每种类型的题目都有其独特的求解思路，掌握这些通用模板有助于提高刷题效率并加深理解。