关注B站可以观看更多实战教学视频：hallo128的个人空间

Python 数据结构和算法面试题，使用 Jupyter Notebook 编写

1. 反转链表

python"># 单链表节点类定义
class ListNode:def __init__(self, value=0, next=None):self.value = valueself.next = next# 反转链表的函数
def reverse_linked_list(head):prev = Nonecurrent = headwhile current:next_node = current.nextcurrent.next = prevprev = currentcurrent = next_nodereturn prev# 测试链表反转
def print_list(head):while head:print(head.value, end=" -> ")head = head.nextprint("None")# 构造链表 1 -> 2 -> 3 -> 4 -> None
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
print("Original list:")
print_list(head)# 反转链表
reversed_head = reverse_linked_list(head)
print("Reversed list:")
print_list(reversed_head)

2. 合并两个有序链表

python">class ListNode:def __init__(self, value=0, next=None):self.value = valueself.next = nextdef merge_two_sorted_lists(l1, l2):dummy = ListNode()current = dummywhile l1 and l2:if l1.value < l2.value:current.next = l1l1 = l1.nextelse:current.next = l2l2 = l2.nextcurrent = current.next# 如果某个链表还有剩余，直接链接到结果if l1:current.next = l1if l2:current.next = l2return dummy.next# 测试
l1 = ListNode(1, ListNode(3, ListNode(5)))
l2 = ListNode(2, ListNode(4, ListNode(6)))merged_head = merge_two_sorted_lists(l1, l2)
print_list(merged_head)

3. 二分查找

python">def binary_search(arr, target):left, right = 0, len(arr) - 1while left <= right:mid = (left + right) // 2if arr[mid] == target:return midelif arr[mid] < target:left = mid + 1else:right = mid - 1return -1# 测试
arr = [1, 3, 5, 7, 9, 11]
target = 7
index = binary_search(arr, target)
print(f"Element {target} found at index {index}")

4. 快速排序

python">def quicksort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) // 2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quicksort(left) + middle + quicksort(right)# 测试
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quicksort(arr)
print(f"Sorted array: {sorted_arr}")

5. 最小栈

python">class MinStack:def __init__(self):self.stack = []self.min_stack = []def push(self, val):self.stack.append(val)if not self.min_stack or val <= self.min_stack[-1]:self.min_stack.append(val)def pop(self):if self.stack:if self.stack[-1] == self.min_stack[-1]:self.min_stack.pop()return self.stack.pop()def top(self):if self.stack:return self.stack[-1]def getMin(self):if self.min_stack:return self.min_stack[-1]# 测试
min_stack = MinStack()
min_stack.push(-2)
min_stack.push(0)
min_stack.push(-3)
print(min_stack.getMin())  # 输出 -3
min_stack.pop()
print(min_stack.top())     # 输出 0
print(min_stack.getMin())  # 输出 -2

6. 爬楼梯问题（动态规划）

python">def climb_stairs(n):if n <= 2:return ndp = [0] * (n + 1)dp[1], dp[2] = 1, 2for i in range(3, n + 1):dp[i] = dp[i - 1] + dp[i - 2]return dp[n]# 测试
n = 5
print(f"Number of ways to climb {n} stairs: {climb_stairs(n)}")

7. 岛屿数量（DFS）

python">def num_islands(grid):if not grid:return 0def dfs(grid, i, j):if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == '0':returngrid[i][j] = '0'dfs(grid, i + 1, j)dfs(grid, i - 1, j)dfs(grid, i, j + 1)dfs(grid, i, j - 1)count = 0for i in range(len(grid)):for j in range(len(grid[0])):if grid[i][j] == '1':dfs(grid, i, j)count += 1return count# 测试
grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]
]
print(f"Number of islands: {num_islands(grid)}")

8. 寻找最长回文子串

python">def longest_palindrome(s):if len(s) < 2:return sstart, max_len = 0, 1for i in range(1, len(s)):# 偶数长度的回文low, high = i - 1, iwhile low >= 0 and high < len(s) and s[low] == s[high]:if high - low + 1 > max_len:start = lowmax_len = high - low + 1low -= 1high += 1# 奇数长度的回文low, high = i - 1, i + 1while low >= 0 and high < len(s) and s[low] == s[high]:if high - low + 1 > max_len:start = lowmax_len = high - low + 1low -= 1high += 1return s[start:start + max_len]# 测试
s = "babad"
print(f"Longest palindrome in '{s}': {longest_palindrome(s)}")

9. 最长递增子序列（LIS）

python">def length_of_lis(nums):if not nums:return 0dp = [1] * len(nums)for i in range(1, len(nums)):for j in range(i):if nums[i] > nums[j]:dp[i] = max(dp[i], dp[j] + 1)return max(dp)# 测试
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(f"Length of longest increasing subsequence: {length_of_lis(nums)}")

10. 三数之和

python">def three_sum(nums):nums.sort()res = []for i in range(len(nums) - 2):if i > 0 and nums[i] == nums[i - 1]:continueleft, right = i + 1, len(nums) - 1while left < right:total = nums[i] + nums[left] + nums[right]if total < 0:left += 1elif total > 0:right -= 1else:res.append([nums[i], nums[left], nums[right]])while left < right and nums[left] == nums[left + 1]:left += 1while left < right and nums[right] == nums[right - 1]:right -= 1left += 1right -= 1return res# 测试
nums = [-1, 0, 1, 2, -1, -4]
print(f"Three sum combinations: {three_sum(nums)}")

11. 滑动窗口最大值

python">from collections import dequedef max_sliding_window(nums, k):dq = deque()res = []for i in range(len(nums)):# 移除窗口外的元素if dq and dq[0] < i - k + 1:dq.popleft()# 移除小于当前元素的值（保持队列单调递减）while dq and nums[dq[-1]] < nums[i]:dq.pop()dq.append(i)# 当窗口达到大小k时，记录当前的最大值if i >= k - 1:res.append(nums[dq[0]])return res# 测试
nums = [1,3,-1,-3,5,3,6,7]
k = 3
print(f"Max values in each sliding window: {max_sliding_window(nums, k)}")

12. 编辑距离（动态规划）

python">def min_distance(word1, word2):m, n = len(word1), len(word2)dp = [[0] * (n + 1) for _ in range(m + 1)]for i in range(m + 1):dp[i][0] = ifor j in range(n + 1):dp[0][j] = jfor i in range(1, m + 1):for j in range(1, n + 1):if word1[i - 1] == word2[j - 1]:dp[i][j] = dp[i - 1][j - 1]else:dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])return dp[m][n]# 测试
word1 = "horse"
word2 = "ros"
print(f"Edit distance between '{word1}' and '{word2}': {min_distance(word1, word2)}")

13. 合并区间

python">def merge_intervals(intervals):intervals.sort(key=lambda x: x[0])merged = []for interval in intervals:if not merged or merged[-1][1] < interval[0]:merged.append(interval)else:merged[-1][1] = max(merged[-1][1], interval[1])return merged# 测试
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
print(f"Merged intervals: {merge_intervals(intervals)}")

14. 二叉树的最大深度

python">class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef max_depth(root):if not root:return 0left_depth = max_depth(root.left)right_depth = max_depth(root.right)return max(left_depth, right_depth) + 1# 测试
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20, TreeNode(15), TreeNode(7))print(f"Maximum depth of the binary tree: {max_depth(root)}")

15. 最短路径问题（Dijkstra 算法）

python">import heapqdef dijkstra(graph, start):min_heap = [(0, start)]  # (distance, node)distances = {node: float('inf') for node in graph}distances[start] = 0while min_heap:current_dist, current_node = heapq.heappop(min_heap)if current_dist > distances[current_node]:continuefor neighbor, weight in graph[current_node].items():distance = current_dist + weightif distance < distances[neighbor]:distances[neighbor] = distanceheapq.heappush(min_heap, (distance, neighbor))return distances# 测试
graph = {'A': {'B': 1, 'C': 4},'B': {'A': 1, 'C': 2, 'D': 5},'C': {'A': 4, 'B': 2, 'D': 1},'D': {'B': 5, 'C': 1}
}start_node = 'A'
print(f"Shortest distances from {start_node}: {dijkstra(graph, start_node)}")