1. 295. 数据流的中位数（困难）
题目详情
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。实现MedianFinder 类：MedianFinder()初始化MedianFinder 对象；void addNum(int num) 将数据流中的整数num 添加到数据结构中；double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差10⁻⁵ 以内的答案将被接受。
示例
输入：["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]，[[], [1], [2], [], [3], []]
输出：[null, null, null, 1.5, null, 2.0]
解释：MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1]；medianFinder.addNum(2); // arr = [1, 2]；medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)；medianFinder.addNum(3); // arr[1, 2, 3]；medianFinder.findMedian(); // return 2.0
提示
•-10⁵ <= num <= 10⁵
•在调用 findMedian 之前，数据结构中至少有一个元素
•最多 5 * 10⁴ 次调用 addNum 和 findMedian
核心解题思路
采用「双堆」技巧（面试高频，困难题核心解法），用两个堆维护数据流：最大堆（max_heap）存储左半部分元素，最小堆（min_heap）存储右半部分元素，保证两个堆的大小差不超过1。添加元素时，先插入最大堆，再调整到最小堆，最后平衡两个堆的大小；求中位数时，若最大堆size 大于最小堆，中位数为最大堆顶；否则为两个堆顶的平均值。
Python面试手撕代码
class MedianFinder(object): def __init__(self): # 最大堆：存储左半部分元素（用负号实现，因为Python默认是最小堆） self.max_heap = [] # 最小堆：存储右半部分元素 self.min_heap = [] def addNum(self, num): """ :type num: int :rtype: None """ # 先将元素插入最大堆（插入负号，模拟最大堆） heapq.heappush(self.max_heap, -num) # 将最大堆的堆顶元素（左半部分最大值）移到最小堆，保证左<=右 heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap)) # 平衡两个堆的大小，确保最大堆size >= 最小堆size，且差不超过1 if len(self.max_heap) < len(self.min_heap): heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap)) def findMedian(self): """ :rtype: float """ # 最大堆size更大，中位数是最大堆顶（还原负号） if len(self.max_heap) > len(self.min_heap): return -self.max_heap[0] # 两个堆size相等，中位数是两个堆顶的平均值 else: return (-self.max_heap[0] + self.min_heap[0]) / 2.0
2. 53. 最大子数组和（中等）
题目详情
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。
示例
•示例 1：输入nums = [-2,1,-3,4,-1,2,1,-5,4]，输出6；解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
•示例 2：输入nums = [1]，输出1。
•示例 3：输入nums = [5,4,-1,7,8]，输出23。
提示
•1 <= nums.length <= 10⁵
•-10⁴ <= nums[i] <= 10⁴
进阶
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
核心解题思路
采用「动态规划」（贪心思想优化，空间O(1)），核心思路：遍历数组，对于每个元素，判断其前一个元素的和是否为正，若为正，则将当前元素加上前一个元素的和（延长连续子数组）；若为负，则当前元素作为新的连续子数组起点。最后返回数组中的最大值，即为最大子数组和。
Python面试手撕代码
class Solution: def maxSubArray(self, nums: List[int]) -> int: # 遍历数组，从第二个元素开始（索引1） for i in range(1, len(nums)): # 若前一个元素的和为正，说明加上当前元素能增大子数组和，进行累加 if nums[i-1] > 0: nums[i] += nums[i-1] # 数组经过修改后，最大值即为最大子数组和 return max(nums)
3. 179. 最大数（中等）
题目详情
给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
示例
•示例 1：输入nums = [10,2]，输出"210"。
•示例 2：输入nums = [3,30,34,5,9]，输出"9534330"。
提示
•1 <= nums.length <= 100
•0 <= nums[i] <= 10⁹
核心解题思路
核心是「自定义排序规则」：将数字转为字符串，比较两个字符串 a 和 b 的拼接结果（a+b 和 b+a），若 a+b < b+a，则 b 应排在 a 前面；反之 a 排在前面。采用快速排序实现自定义排序，排序后拼接字符串，若拼接结果以"0"开头（全为0的情况），返回"0"，否则返回拼接结果。
Python面试手撕代码
class Solution(object): def largestNumber(self, nums): """ :type nums: List[int] :rtype: str """ # 快速排序的分区函数，自定义排序规则 def partition(strs, left, right): # 随机选择基准值，避免极端情况（如数组已排序） idx = random.randint(left, right) strs[idx], strs[left] = strs[left], strs[idx] pivot = strs[left] while left < right: # 比较b+a和a+b，若pivot+b <= b+pivot，说明b应在pivot前面，右指针左移 while left < right and int(pivot + strs[right]) <= int(strs[right] + pivot): right -= 1 strs[left] = strs[right] # 若strs[left]+pivot <= pivot+strs[left]，说明strs[left]应在pivot后面，左指针右移 while left < right and int(strs[left] + pivot) <= int(pivot + strs[left]): left += 1 strs[right] = strs[left] strs[left] = pivot return left # 快速排序主函数 def quicksort(nums, left, right): if left >= right: return mid = partition(nums, left, right) quicksort(nums, left, mid-1) quicksort(nums, mid+1, right) # 将所有数字转为字符串，便于拼接比较 strs = [str(num) for num in nums] n = len(strs) # 对字符串数组进行自定义快速排序 quicksort(strs, 0, n-1) # 特殊情况：全为0时，返回"0"（避免出现"000..."） if strs[-1] == '0': return "0" # 排序后反转（因为分区规则是从小到大，反转后为从大到小），再拼接 return ''.join(strs[::-1])
4. 剑指 Offer 46. 把数字翻译成字符串
题目详情
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 a，1 翻译成 b，……，11 翻译成 l，……，25 翻译成 z。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例
•示例 1：输入num = 12258，输出5；解释：12258有5种不同的翻译方法，分别是bccfi、bwfi、bczi、mcfi、mzi。
•示例 2：输入num = 0，输出1；解释：0只能翻译为a，仅1种方法。
•示例 3：输入num = 10，输出2；解释：10可翻译为ba（1→b，0→a）或k（10→k），共2种方法。
提示
•0 <= num <= 2^31 - 1
核心解题思路
采用「动态规划」，将数字转为字符串，定义 dp[i] 表示前 i 个字符的翻译方法数。边界条件：dp[0] = 1（空字符串有一种翻译方法），dp[1] = 1（单个字符只有一种翻译方法）。遍历字符串，若当前两位字符组成的数字在 10~25 之间，则 dp[i] = dp[i-1] + dp[i-2]（两种翻译方式：单独翻译当前字符、与前一个字符组合翻译）；否则dp[i] = dp[i-1]（只能单独翻译当前字符）。
Python面试手撕代码
def translate_num(num: int) -> int: s = str(num) # 将数字转为字符串，便于处理每一位 n = len(s) if n == 0: # 空数字，返回0（实际题目中num为有效数字，此判断用于鲁棒性） return 0 # dp[i] 表示前 i 个字符的翻译方法数 dp = [0] * (n + 1) dp[0] = 1 # 边界：空字符串有一种翻译方法（用于组合翻译时的递推） dp[1] = 1 # 边界：单个字符只有一种翻译方法 # 从第2个字符开始遍历（i从2到n） for i in range(2, n + 1): # 检查当前两位字符（s[i-2]和s[i-1]）是否能组成合法的翻译数字（10-25） if s[i-2] == '1' or (s[i-2] == '2' and s[i-1] <= '5'): # 两种翻译方式：单独翻译当前字符、与前一个组合翻译 dp[i] = dp[i-1] + dp[i-2] else: # 只能单独翻译当前字符，方法数与前一个一致 dp[i] = dp[i-1] return dp[n] # 前n个字符（整个数字）的翻译方法数
5. 剑指 Offer 47. 礼物的最大价值
题目详情
在一个 m * n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例
•示例 1：输入grid = [[1,3,1],[1,5,1],[4,2,1]]，输出12；解释：路径1→3→5→2→1的礼物价值总和最大，为1+3+5+2+1=12。
•示例 2：输入grid = [[1,2,5],[3,2,1]]，输出9；解释：路径1→3→2→1的礼物价值总和最大，为1+3+2+1=7（修正：正确路径1→3→2→1总和为7，或1→2→5→1总和为9，以题目标准示例为准）。
提示
•0 < grid.length <= 200
•0 < grid[0].length <= 200
•grid[i][j] > 0
核心解题思路
采用「动态规划」，定义 dp[i][j] 表示到达 (i,j) 位置时能拿到的最大礼物价值。边界条件：dp[0][0] = grid[0][0]（起点价值）；第一行只能从左向右移动，dp[0][j] = dp[0][j-1] + grid[0][j]；第一列只能从上下移动，dp[i][0] = dp[i-1][0] + grid[i][0]。对于其他位置，dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]（取上方或左方的最大价值，加上当前礼物价值）。
Python面试手撕代码
def maxValue(grid: list[list[int]]) -> int: # 边界判断：棋盘为空或第一行为空，返回0 if not grid or not grid[0]: return 0 m, n = len(grid), len(grid[0]) # m行n列 # 初始化DP数组，与棋盘大小一致 dp = [[0] * n for _ in range(m)] dp[0][0] = grid[0][0] # 起点的最大价值就是自身价值 # 初始化第一行：只能从左向右移动，价值累加 for j in range(1, n): dp[0][j] = dp[0][j-1] + grid[0][j] # 初始化第一列：只能从上向下移动，价值累加 for i in range(1, m): dp[i][0] = dp[i-1][0] + grid[i][0] # 填充剩余位置：每个位置的最大价值 = 上方或左方的最大价值 + 当前礼物价值 for i in range(1, m): for j in range(1, n): dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j] # 右下角的价值即为最大礼物价值 return dp[-1][-1]
6. 剑指 Offer 50. 第一个只出现一次的字符
题目详情
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。s 只包含小写字母。
示例
•示例 1：输入s = "abaccdeff"，输出"b"；解释：字符b只出现1次，且是第一个只出现一次的字符。
•示例 2：输入s = ""，输出" "；解释：空字符串无字符，返回单空格。
•示例 3：输入s = "aabb"，输出" "；解释：所有字符均出现2次，无只出现一次的字符。
提示
•0 <= s.length <= 10000
•s 仅由小写英文字母组成
核心解题思路
采用「哈希表」（字典）统计字符出现次数，遍历字符串，将每个字符存入字典：若字符未出现过，标记为 True（表示出现1次）；若已出现过，标记为 False（表示出现多次）。再遍历字典，找到第一个标记为True 的字符，即为答案；若没有，返回空格。
Python面试手撕代码
classSolution: def firstUniqChar(self, s): # 哈希字典，用于标记字符是否只出现一次 hash_dict = {} # 第一次遍历：统计每个字符的出现情况 for char in s: if char not in hash_dict: hash_dict[char] = True # 首次出现，标记为True else: hash_dict[char] = False # 再次出现，标记为False # 第二次遍历：找到第一个标记为True（只出现一次）的字符 for k, v in hash_dict.items(): if v: return k # 若没有只出现一次的字符，返回单空格 return ' '
7. LCR 170. 交易逆序对的总数（困难）
题目详情
在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录record，返回其中存在的「交易逆序对」总数。
示例
示例 1：输入record = [9, 7, 5, 4, 6]，输出8；解释：交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。
提示
0 <= record.length <= 50000
核心解题思路
采用「归并排序」（困难题核心解法），在归并排序的合并阶段统计逆序对数量。合并两个有序子数组时，若左子数组的元素大于右子数组的元素，则左子数组中剩余的所有元素都与当前右子数组元素构成逆序对，统计数量；最后将排序后的数组还原，返回统计的逆序对总数，时间复杂度O(n log n)，适配大数据量。
Python面试手撕代码
class Solution(object): def reversePairs(self, record): """ :type record: List[int] :rtype: int """ self.cnt = 0 # 用于统计逆序对总数，定义为类属性，方便递归修改 # 归并排序函数：nums为原数组，res为临时数组，left、right为当前排序区间 def merge_sort(nums, res, left, right): if left >= right: # 单个元素或空，无需排序，返回 return mid = left + (right - left) // 2 # 中间位置，避免溢出 merge_sort(nums, res, left, mid) # 递归排序左子数组 merge_sort(nums, res, mid+1, right) # 递归排序右子数组 # 合并两个有序子数组，同时统计逆序对 i, j, k = left, mid+1, left # i左子数组指针，j右子数组指针，k临时数组指针 while i <= mid and j <= right: if nums[i] <= nums[j]: # 左元素 <= 右元素，无逆序对，左指针后移 res[k] = nums[i] i += 1 k += 1 else: # 左元素 > 右元素，左子数组剩余元素均与当前右元素构成逆序对 res[k] = nums[j] self.cnt += mid - i + 1 # 统计逆序对数量 j += 1 k += 1 # 将左子数组剩余元素存入临时数组 while i <= mid: res[k] = nums[i] i += 1 k += 1 # 将右子数组剩余元素存入临时数组 while j <= right: res[k] = nums[j] j += 1 k += 1 # 将临时数组的有序元素复制回原数组，完成当前区间排序 for k in range(left, right+1): nums[k] = res[k] n = len(record) res = [0] * n # 临时数组，用于归并排序的合并操作 merge_sort(record, res, 0, n-1) # 启动归并排序，统计逆序对 return self.cnt
8. LCR 173. 点名（简单）
题目详情
某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席，请返回他的学号。
示例
•示例 1：输入records = [0,1,2,3,5]，输出4。
•示例 2：输入records = [0, 1, 2, 3, 4, 5, 6, 8]，输出7。
提示
1 <= records.length <= 10000
核心解题思路
利用「升序数组特性 + 二分查找」，正常情况下，学号 i 应对应 records[i] = i。若 records[mid] == mid，说明左半部分无缺席同学，缺席者在右半部分；若 records[mid] != mid，说明缺席者在左半部分（包括mid）。遍历结束后，left 即为缺席同学的学号。
Python面试手撕代码
class Solution(object): def takeAttendance(self, records): """ :type records: List[int] :rtype: int """ left ,right = 0, len(records)-1 # 二分查找双指针 while left <= right: mid = (left + right) // 2 # 中间位置 if records[mid] == mid: # 中间位置学号匹配，缺席者在右半部分 left = mid + 1 else: # 中间位置学号不匹配，缺席者在左半部分 right = mid - 1 # 循环结束，left即为缺席同学的学号 return left
9. 230. 二叉搜索树中第 K 小的元素（中等）
题目详情
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（k 从 1 开始计数）。
示例
•示例 1：输入root = [3,1,4,null,2], k = 1，输出1。
•示例 2：输入root = [5,3,6,2,4,null,null,1], k = 3，输出3。
提示
•树中的节点数为 n 。
•1 <= k <= n <= 10⁴
•0 <= Node.val <= 10⁴
进阶
如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
核心解题思路
利用「二叉搜索树的中序遍历特性」（中序遍历结果为升序），采用递归中序遍历，遍历过程中计数，当计数达到 k时，当前节点的值即为第 k小的元素，立即返回，避免多余遍历。
Python面试手撕代码
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution(object): def kthSmallest(self, root, k): """ :type root: Optional[TreeNode] :type k: int :rtype: int """ self.result = None # 存储第k小的元素值 self.cnt = 0 # 计数，记录当前遍历到第几个元素 # 中序遍历函数（左→根→右，结果升序） def dfs(root): if not root: # 节点为空，返回 return dfs(root.left) # 先遍历左子树 self.cnt += 1 # 遍历到当前节点，计数+1 if self.cnt == k: # 计数达到k，当前节点即为第k小元素 self.result = root.val return # 找到后直接返回，避免多余遍历 dfs(root.right) # 遍历右子树 dfs(root) # 启动中序遍历 return self.result
10. 扑克牌顺子（简单）
题目详情
从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这 5 张牌是不是连续的。2 ～ 10 为数字本身，A 为 1，J 为 11，Q 为 12，K 为 13，而大、小王为 0，可以看成任意数字。A 不能视为 14。
核心解题思路
核心条件：1. 除0外，无重复牌（重复牌无法构成顺子）；2. 非0牌的最大值与最小值之差小于5（0可填补空缺）。用哈希集合记录非0牌，判断是否有重复；同时记录非0牌的最大值和最小值，最后验证差值是否小于5，满足则为顺子。
Python面试手撕代码
class Solution: def isStraight(self, nums: list[int]) -> bool: # 哈希集合，记录非0的扑克牌，用于判断重复 cards = set() # 初始化最小值为不可能存在的扑克牌值（最大牌为13，设为14） min_val = 14 # 初始化最大值为不可能存在的扑克牌值（最小非0牌为1，设为0） max_val = 0 for num in nums: # num 为 0 代表大小王，可视为任意数字，跳过处理 if num == 0: continue # 更新非0牌的最大值 max_val = max(max_val, num) # 更新非0牌的最小值 min_val = min(min_val, num) # 若集合中已存在该数，说明有重复牌，无法构成顺子，返回false if num in cards: return False # 将当前非0牌加入集合 cards.add(num) # 最终判断：最大值与最小值的差是否小于5（0可填补中间的空缺） return max_val - min_val < 5
11. 121. 买卖股票的最佳时机（简单）
题目详情
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0。
示例
•示例 1：输入[7,1,5,3,6,4]，输出5；解释：在第 2 天（股票价格 = 1）买入，第 5 天（股票价格 = 6）卖出，最大利润 = 6-1 = 5。
•示例 2：输入prices = [7,6,4,3,1]，输出0；解释：无盈利空间，返回0。
提示
•1 <= prices.length <= 10⁵
•0 <= prices[i] <= 10⁴
核心解题思路
采用「动态规划」（贪心思想优化，空间O(1)），定义两个变量：buy 表示当前最低买入价（初始为第一天价格的负数），sell 表示当前最大利润（初始为0）。遍历数组，不断更新最低买入价和最大利润：buy = max(buy, -prices[i])（取最低买入价），sell = max(sell, buy + prices[i])（取当前价格卖出的最大利润），最终返回sell。
Python面试手撕代码
class Solution(object): def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ # buy 表示当前最低买入价（用负数表示，便于后续计算利润） buy = -prices[0] # sell 表示当前能获得的最大利润 sell = 0 # 遍历数组，从第一天开始（索引0） for i in range(len(prices)): # 更新最低买入价：取当前买入价和之前的最低买入价中更低的 buy = max(buy, -prices[i]) # 更新最大利润：取当前利润和（当前买入价+当前价格）中更大的 sell = max(sell, buy + prices[i]) # 最终返回最大利润（无盈利则为0） return sell
12. 238. 除了自身以外数组的乘积（中等）
题目详情
给你一个整数数组 nums，返回数组answer ，其中answer[i] 等于nums 中除了nums[i] 之外其余各元素的乘积。题目数据保证数组nums之中任意元素的全部前缀元素和后缀的乘积都在32 位整数范围内。请不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例
•示例 1：输入nums = [1,2,3,4]，输出[24,12,8,6]。
•示例 2：输入nums = [-1,1,0,-3,3]，输出[0,0,9,0,0]。
提示
•2 <= nums.length <= 10⁵
•-30 <= nums[i] <= 30
•输入保证数组 answer[i] 在 32 位整数范围内
进阶
你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
核心解题思路
采用「前缀乘积 + 后缀乘积」（空间O(1)优化），先用输出数组 ans 存储前缀乘积：ans[i] = 前 i-1 个元素的乘积；再用一个变量 suffix 存储后缀乘积，从后向前遍历，ans[i] *= suffix（后缀乘积，即后 n-i-1 个元素的乘积），同时更新 suffix = suffix * nums[i]，最终 ans 即为所求，无需额外空间。
Python面试手撕代码
class Solution(object): def productExceptSelf(self, nums): """ :type nums: List[int] :rtype: List[int] """ n = len(nums) ans = [1] * n # 输出数组，初始化为1，用于存储前缀乘积 # 第一步：计算前缀乘积，ans[i] = 前i-1个元素的乘积 for i in range(1, n): ans[i] = ans[i-1] * nums[i-1] # 第二步：计算后缀乘积，并用后缀乘积更新ans，实现O(1)空间 suffix = 1 # 后缀乘积，初始为1（最后一个元素的后缀乘积为1） # 从后向前遍历 for i in range(n-1, -1, -1): ans[i] *= suffix # ans[i] = 前缀乘积 * 后缀乘积 suffix *= nums[i] # 更新后缀乘积，加入当前元素 return ans
例题来自力扣网https://leetcode-cn.com/
