一、引言
在计算机编程的世界里，LeetCode 是一个非常知名的刷题平台，它上面有各种各样难度级别的题目，从中等题到困难题，每一个难度层次都像是编程路上的一道道关卡。很多小伙伴在刷中等题的时候还能应付自如，但一旦遇到困难题，就感觉像是碰到了一堵难以逾越的墙。今天咱们就来聊聊怎么从中等题顺利过渡到困难题，总结一些突破技巧以及高频考点。
二、刷中等题的基础巩固
2.1 熟练掌握数据结构
数据结构是编程的基础，就好比盖房子的地基。在 LeetCode 刷题中，常见的数据结构有数组、链表、栈、队列、树、图等。
以数组为例，在 Python 中，数组可以用列表来表示。下面是一个简单的数组操作示例：
# 创建一个数组
arr = [1, 2, 3, 4, 5]
# 访问数组元素
print(arr[2]) # 输出 3
# 修改数组元素
arr[3] = 10
print(arr) # 输出 [1, 2, 3, 10, 5]
链表的操作相对复杂一些，我们来看一个简单的链表节点定义和遍历示例：
# 定义链表节点类
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 创建链表
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
# 遍历链表
current = head
while current:
print(current.val)
current = current.next
2.2 掌握基本算法思想
基本的算法思想如贪心算法、动态规划、分治法等在中等题中经常会用到。
贪心算法的核心思想是在每一步都做出当前看起来最优的选择。比如，在找零钱问题中，我们总是优先选择面值最大的硬币。以下是一个简单的找零钱示例：
# 找零钱问题，使用贪心算法
def coin_change(coins, amount):
coins.sort(reverse=True)
count = 0
for coin in coins:
while amount >= coin:
amount -= coin
count += 1
return count if amount == 0 else -1
coins = [25, 10, 5, 1]
amount = 63
print(coin_change(coins, amount)) # 输出 6
动态规划则是通过把原问题分解为相对简单的子问题，并保存子问题的解来避免重复计算。比如，斐波那契数列可以用动态规划来解决：
# 斐波那契数列，使用动态规划
def fibonacci(n):
if n == 0:
return 0
if n == 1:
return 1
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
print(fibonacci(6)) # 输出 8
三、从中等题到困难题的突破技巧
3.1 深入理解问题本质
困难题往往不会像中等题那样直接给出问题的描述，而是需要我们自己去挖掘问题的本质。比如，有些题目看起来是在处理数组，但实际上可能是要运用图论的知识。
以 LeetCode 上的“课程表”问题为例，题目描述是给定课程数量和课程之间的先修关系，判断是否可以完成所有课程的学习。这个问题本质上就是一个图的拓扑排序问题。以下是 Python 实现：
from collections import defaultdict, deque
def canFinish(numCourses, prerequisites):
# 构建图和入度数组
graph = defaultdict(list)
in_degree = [0] * numCourses
for pre in prerequisites:
graph[pre[1]].append(pre[0])
in_degree[pre[0]] += 1
# 初始化队列
queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
count = 0
# 拓扑排序
while queue:
node = queue.popleft()
count += 1
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return count == numCourses
numCourses = 2
prerequisites = [[1, 0]]
print(canFinish(numCourses, prerequisites)) # 输出 True
3.2 多维度思考问题
对于困难题，单一的思路往往是不够的，我们需要从多个维度去思考问题。比如，在解决搜索问题时，我们可以考虑广度优先搜索（BFS）和深度优先搜索（DFS）两种不同的搜索方式。
以“岛屿数量”问题为例，我们可以用 DFS 来解决：
def numIslands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(i, j):
if i < 0 or i >= rows or j < 0 or j >= cols or grid[i][j] != '1':
return
grid[i][j] = '#'
dfs(i + 1, j)
dfs(i - 1, j)
dfs(i, j + 1)
dfs(i, j - 1)
for i in range(rows):
for j in range(cols):
if grid[i][j] == '1':
dfs(i, j)
count += 1
return count
grid = [
["1", "1", "0", "0", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "1", "0", "0"],
["0", "0", "0", "1", "1"]
]
print(numIslands(grid)) # 输出 3
我们也可以用 BFS 来解决这个问题：
from collections import deque
def numIslands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def bfs(i, j):
queue = deque([(i, j)])
grid[i][j] = '#'
while queue:
x, y = queue.popleft()
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for dx, dy in directions:
new_x, new_y = x + dx, y + dy
if 0 <= new_x < rows and 0 <= new_y < cols and grid[new_x][new_y] == '1':
queue.append((new_x, new_y))
grid[new_x][new_y] = '#'
for i in range(rows):
for j in range(cols):
if grid[i][j] == '1':
bfs(i, j)
count += 1
return count
grid = [
["1", "1", "0", "0", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "1", "0", "0"],
["0", "0", "0", "1", "1"]
]
print(numIslands(grid)) # 输出 3
3.3 学习优秀代码
在 LeetCode 上，每道题都有很多用户提交的代码。我们可以学习那些优秀的代码，看看别人是怎么解决问题的。通过学习优秀代码，我们可以学到一些巧妙的技巧和优化方法。
比如，在解决“两数之和”问题时，我们可以使用哈希表来优化时间复杂度。以下是一个优秀的 Python 实现：
def twoSum(nums, target):
hash_map = {}
for i, num in enumerate(nums):
complement = target - num
if complement in hash_map:
return [hash_map[complement], i]
hash_map[num] = i
return []
nums = [2, 7, 11, 15]
target = 9
print(twoSum(nums, target)) # 输出 [0, 1]
四、困难题高频考点总结
4.1 高级数据结构
困难题中经常会用到一些高级数据结构，如线段树、树状数组、字典树等。
线段树是一种二叉树，常用于高效处理区间查询和更新操作。以下是一个简单的线段树实现示例：
class SegmentTree:
def __init__(self, arr):
self.n = len(arr)
self.tree = [0] * (4 * self.n)
self.build(arr, 0, 0, self.n - 1)
def build(self, arr, node, start, end):
if start == end:
self.tree[node] = arr[start]
else:
mid = (start + end) // 2
left_child = 2 * node + 1
right_child = 2 * node + 2
self.build(arr, left_child, start, mid)
self.build(arr, right_child, mid + 1, end)
self.tree[node] = self.tree[left_child] + self.tree[right_child]
def query(self, node, start, end, l, r):
if r < start or l > end:
return 0
if l <= start and r >= end:
return self.tree[node]
mid = (start + end) // 2
left_child = 2 * node + 1
right_child = 2 * node + 2
left_sum = self.query(left_child, start, mid, l, r)
right_sum = self.query(right_child, mid + 1, end, l, r)
return left_sum + right_sum
arr = [1, 3, 5, 7, 9, 11]
seg_tree = SegmentTree(arr)
print(seg_tree.query(0, 0, len(arr) - 1, 1, 3)) # 输出 15
4.2 复杂算法思想
困难题中还会涉及到一些复杂的算法思想，如动态规划的变形、图论算法等。
比如，在“最长递增子序列的个数”问题中，需要结合动态规划和计数的思想。以下是 Python 实现：
def findNumberOfLIS(nums):
if not nums:
return 0
n = len(nums)
lengths = [1] * n
counts = [1] * n
for i in range(n):
for j in range(i):
if nums[j] < nums[i]:
if lengths[j] + 1 > lengths[i]:
lengths[i] = lengths[j] + 1
counts[i] = counts[j]
elif lengths[j] + 1 == lengths[i]:
counts[i] += counts[j]
max_length = max(lengths)
return sum(count for length, count in zip(lengths, counts) if length == max_length)
nums = [1, 3, 5, 4, 7]
print(findNumberOfLIS(nums)) # 输出 2
4.3 优化技巧
在困难题中，优化技巧非常重要。比如，在处理大规模数据时，我们需要考虑空间复杂度和时间复杂度的优化。
以“滑动窗口最大值”问题为例，我们可以使用双端队列来优化时间复杂度。以下是 Python 实现：
from collections import deque
def maxSlidingWindow(nums, k):
if not nums:
return []
n = len(nums)
result = []
queue = deque()
for i in range(n):
# 移除队列中不在窗口内的元素
if queue and queue[0] == i - k:
queue.popleft()
# 移除队列中比当前元素小的元素
while queue and nums[queue[-1]] < nums[i]:
queue.pop()
queue.append(i)
# 当窗口形成后，记录最大值
if i >= k - 1:
result.append(nums[queue[0]])
return result
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(maxSlidingWindow(nums, k)) # 输出 [3, 3, 5, 5, 6, 7]
五、应用场景
LeetCode 刷题不仅仅是为了通过面试，在实际的工作中，这些算法和数据结构的知识也有很多应用场景。
在游戏开发中，图论算法可以用于路径规划，如 A* 算法。在数据库系统中，索引的实现可能会用到 B 树和 B+ 树等数据结构。在搜索引擎中，倒排索引是一种非常重要的数据结构，用于快速查找包含特定关键词的文档。
六、技术优缺点
6.1 优点
掌握这些算法和数据结构知识可以提高我们的编程能力和解决问题的能力。在面试中，能够熟练解决 LeetCode 上的困难题可以增加我们的竞争力。在实际工作中，这些知识可以帮助我们优化代码的性能，提高系统的效率。
6.2 缺点
刷 LeetCode 题需要花费大量的时间和精力。而且，有些题目的解法可能比较复杂，对于初学者来说可能难以理解。此外，LeetCode 上的题目和实际工作中的问题可能存在一定的差距，需要我们灵活运用所学知识。
七、注意事项
在刷 LeetCode 题时，我们需要注意以下几点：
不要盲目刷题，要注重总结和归纳。每做完一道题，要思考一下这道题的解题思路和方法，以及是否有其他的解法。
要注重代码的质量和可读性。在面试中，除了要给出正确的解法，代码的质量和可读性也很重要。
要合理安排时间，不要因为刷题而忽略了其他方面的学习和实践。
八、文章总结
通过以上的介绍，我们了解了从中等题到困难题的突破技巧以及困难题的高频考点。刷 LeetCode 题是一个不断学习和进步的过程，我们需要在巩固基础的前提下，不断提高自己的思维能力和编程技巧。同时，我们也要注意将所学知识应用到实际工作中，提高自己的综合能力。希望大家在 LeetCode 刷题的道路上越走越远，取得好成绩。