面试代码高频题.zip

面试代码题往往聚焦于**基础数据结构（数组、链表、树、哈希表）** 和**经典算法思想（双指针、动态规划、递归回溯、贪心）**。以下按高频场景分类整理，附解题思路和 Python 实现，覆盖 80% 以上的面试高频考点。 ### 一、数组与字符串（高频中的高频） #### 1. 两数之和（LeetCode 1） **问题**：给定整数数组 `nums` 和目标值 `target`，返回两个数的索引，使它们的和为 `target`。 **思路**：哈希表优化，遍历数组时存储已访问元素的值和索引，单次遍历完成查找。 ```python def twoSum(nums, target): num_map = {} # 存储 {值: 索引} for i, num in enumerate(nums): complement = target - num if complement in num_map: return [num_map[complement], i] num_map[num] = i return [] # 题目保证有解，可省略 ``` **复杂度**：时间 O(n)，空间 O(n)。 #### 2. 三数之和（LeetCode 15） **问题**：找出数组中所有和为 0 的三元组，不重复。 **思路**：排序 + 双指针。排序避免重复，固定一个数后用双指针找另外两个数，跳过重复元素。 ```python def threeSum(nums): nums.sort() res = [] n = len(nums) for i in range(n - 2): # 跳过重复的固定值 if i > 0 and nums[i] == nums[i-1]: continue left, right = i + 1, n - 1 while left < right: total = nums[i] + nums[left] + nums[right] if total < 0: left += 1 elif total > 0: right -= 1 else: res.append([nums[i], nums[left], nums[right]]) # 跳过重复的左指针 while left < right and nums[left] == nums[left+1]: left += 1 # 跳过重复的右指针 while left < right and nums[right] == nums[right-1]: right -= 1 left += 1 right -= 1 return res ``` **复杂度**：时间 O(n²)，空间 O(1)（忽略排序的 O(log n)）。 #### 3. 最长回文子串（LeetCode 5） **问题**：找出字符串中最长的回文子串。 **思路**：中心扩展法。回文对称中心可能是字符（奇数长度）或两个字符中间（偶数长度），遍历每个中心并扩展。 ```python def longestPalindrome(s): def expand(left, right): # 从 left/right 向两边扩展，返回最长回文子串 while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return s[left+1:right] # 退出时多扩了一步，需回退 if not s: return "" res = "" for i in range(len(s)): # 奇数长度（中心为 i） odd = expand(i, i) # 偶数长度（中心为 i 和 i+1） even = expand(i, i+1) # 更新最长回文 res = max(res, odd, even, key=len) return res ``` **复杂度**：时间 O(n²)，空间 O(1)。 ### 二、链表操作 #### 1. 反转链表（LeetCode 206） **问题**：反转单链表。 **思路**：迭代法（双指针），用 `prev` 记录前一个节点，`curr` 遍历并反转指针。 ```python class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def reverseList(head): prev = None curr = head while curr: next_temp = curr.next # 保存下一个节点 curr.next = prev # 反转指针 prev = curr # 移动 prev curr = next_temp # 移动 curr return prev # prev 成为新头 ``` **复杂度**：时间 O(n)，空间 O(1)。 #### 2. 环形链表（LeetCode 141） **问题**：判断链表是否有环。 **思路**：快慢指针。快指针每次走 2 步，慢指针每次走 1 步，若相遇则有环。 ```python def hasCycle(head): if not head or not head.next: return False slow = head fast = head.next while slow != fast: if not fast or not fast.next: # 快指针走到终点，无环 return False slow = slow.next fast = fast.next.next return True ``` **复杂度**：时间 O(n)，空间 O(1)。 ### 三、树与二叉树 #### 1. 二叉树的层序遍历（LeetCode 102） **问题**：按层打印二叉树节点值（从上到下，从左到右）。 **思路**：BFS（广度优先搜索），用队列存储每一层的节点，逐层遍历。 ```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def levelOrder(root): if not root: return [] res = [] from collections import deque q = deque([root]) while q: level_size = len(q) # 当前层的节点数 level = [] for _ in range(level_size): node = q.popleft() level.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) res.append(level) return res ``` **复杂度**：时间 O(n)，空间 O(n)（队列最多存储一层节点，最坏为 O(n)）。 #### 2. 对称二叉树（LeetCode 101） **问题**：判断二叉树是否对称（镜像对称）。 **思路**：递归，比较左子树的左节点与右子树的右节点，左子树的右节点与右子树的左节点。 ```python def isSymmetric(root): def isMirror(left, right): if not left and not right: # 都为空，对称 return True if not left or not right: # 一个空一个非空，不对称 return False # 节点值相等，且左左=右右，左右=右左 return (left.val == right.val and isMirror(left.left, right.right) and isMirror(left.right, right.left)) return isMirror(root, root) if root else True ``` **复杂度**：时间 O(n)，空间 O(n)（递归栈深度，最坏为链表时 O(n)）。 ### 四、动态规划（DP） #### 1. 爬楼梯（LeetCode 70） **问题**：每次可爬 1 或 2 阶，求爬到第 n 阶的方法数。 **思路**：DP 状态转移，`dp[i] = dp[i-1] + dp[i-2]`（最后一步爬 1 阶或 2 阶），优化空间为 O(1)。 ```python def climbStairs(n): if n <= 2: return n a, b = 1, 2 # dp[1]=1, dp[2]=2 for _ in range(3, n+1): a, b = b, a + b # 滚动更新 return b ``` **复杂度**：时间 O(n)，空间 O(1)。 #### 2. 最长递增子序列（LeetCode 300） **问题**：找出数组中最长的严格递增子序列长度（子序列可不连续）。 **思路**：DP + 二分优化。`dp[i]` 表示长度为 i+1 的子序列的最小尾元素，遍历数组时用二分找插入位置。 ```python def lengthOfLIS(nums): import bisect dp = [] for num in nums: # 找到 dp 中第一个 >= num 的位置，替换为 num（维持递增） idx = bisect.bisect_left(dp, num) if idx == len(dp): dp.append(num) # 延长子序列 else: dp[idx] = num return len(dp) ``` **复杂度**：时间 O(n log n)，空间 O(n)。 ### 五、排序与查找 #### 1. 二分查找（LeetCode 704） **问题**：在有序数组中查找目标值，返回索引（不存在返回 -1）。 **思路**：左右指针收缩范围，每次比较中间值与目标。 ```python def search(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid elif nums[mid] < target: