LeetCode经典题目合集：面试刷题攻略

在计算机科学领域，算法和数据结构是必不可少的部分。而LeetCode作为全球知名的算法和数据结构在线编程平台，已经成为许多公司面试的必备环节。本文将为你介绍LeetCode上的经典题目，并给出解题思路和代码示例。通过刷这些题目，你可以提升算法和数据结构能力，为面试和工作做好准备。
一、二分查找
题目描述：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其下标。如果目标值不存在于数组中，则返回-1。
解题思路：使用二分查找算法，在每一步比较中间元素与目标值的大小关系，缩小搜索范围。
示例代码（Python）：

def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1

二、动态规划
题目描述：给定一个矩阵，将矩阵中的数字按照从小到大的顺序排列，同时保持矩阵中每列的相对顺序不变。
解题思路：使用动态规划算法，定义一个二维数组dp，其中dp[i][j]表示将矩阵的前i行第j列元素放在当前位置的最小代价。遍历矩阵中的每个元素，对于当前元素，遍历其所在列的所有元素，比较将当前元素放在不同位置的代价大小，更新dp数组。最后按照dp数组的值从小到大排序即可。
示例代码（Python）：

def matrix_sort(matrix):
m, n = len(matrix), len(matrix[0])
dp = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
for k in range(i):  # 遍历前i行的第j列元素
if matrix[i][j] < matrix[k][j]:  # 比较将当前元素放在不同位置的代价大小
dp[i][j] = max(dp[i][j], dp[k][j] + 1)
return sorted(matrix, key=lambda x: dp[len(matrix) - 1][x - 1])  # 按照dp数组的值从小到大排序并返回结果

三、深度优先搜索（DFS）与广度优先搜索（BFS）
题目描述：给定一个无向图，找出从起点到终点经过所有节点的路径。
解题思路：使用深度优先搜索（DFS）或广度优先搜索（BFS）算法。对于DFS，从起点开始遍历所有相邻节点，然后递归地继续遍历这些节点的相邻节点，直到到达终点或无法继续扩展。对于BFS，从起点开始遍历所有相邻节点，然后依次遍历它们的相邻节点，直到到达终点或无法继续扩展。在遍历过程中记录路径并检查是否满足经过所有节点的条件。
示例代码（Python）：
```python
def dfs_bfs(graph, start, end):
visited = set() # 记录已访问的节点
path = [] # 记录路径
def dfs(node):
if node not in visited:
visited.add(node)
path.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
if node == end:
print(‘’.join(map(str, path)))
path.pop()
else:
path.pop()
visited.remove(node)
def bfs(node):
queue = [node] # 使用队列进行广度优先搜索
while queue:
node = queue.pop(0)
if node not in visited