牛客网面试TOP101 - Python算法学习指南

在这里插入图片描述

题单链接: 牛客top101
题目总数: 101道
题单定位: 基于牛客面经汇总分析整理出的面试常考算法题，完成本题单可解决面试中约70%的代码题
题单模式: 核心代码模式

目录

  1. 题单概览
  2. 链表专题 (BM1-BM16)
  3. 二分查找/排序专题 (BM17-BM22)
  4. 二叉树专题 (BM23-BM41)
  5. 堆/栈/队列专题 (BM42-BM49)
  6. 哈希专题 (BM50-BM54)
  7. 递归/回溯专题 (BM55-BM61)
  8. 动态规划专题 (BM62-BM82)
  9. 字符串专题 (BM83-BM86)
  10. 双指针专题 (BM87-BM94)
  11. 贪心专题 (BM95-BM96)
  12. 模拟/设计专题 (BM97-BM101)

一、题单概览

1.1 分类结构统计

分类/专题题目数量占比难度分布题号范围
链表1615.8%简单-中等BM1 - BM16
二叉树1918.8%简单-困难BM23 - BM41
动态规划2120.8%中等-困难BM62 - BM82
递归/回溯109.9%中等-困难BM55 - BM61
排序/二分查找65.9%简单-中等BM17 - BM22
双指针87.9%简单-中等BM87 - BM94
哈希55.0%简单-中等BM50 - BM54
堆/栈/队列87.9%中等BM42 - BM49
字符串44.0%简单-中等BM83 - BM86
贪心22.0%中等BM95 - BM96
模拟/设计55.0%中等-困难BM97 - BM101

1.2 难度分布

难度级别题目数量占比
入门/简单约35题34.7%
中等约50题49.5%
较难/困难约16题15.8%

二、链表专题 (BM1-BM16)

2.1 核心知识点

  • 快慢指针: Floyd判环、找中点、找倒数第K个节点
  • 虚拟头节点: 简化边界处理
  • 链表反转: 头插法/尾插法
  • 链表合并: 归并思想
  • 链表拆分与重排

2.2 Python代码模板

# 链表节点定义
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 1. 反转链表 - 迭代法
class Solution:
    def ReverseList(self, head):
        pre = None
        cur = head
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

# 2. 快慢指针判环
class Solution:
    def hasCycle(self, head):
        fast = slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False

# 3. 找环入口
class Solution:
    def EntryNodeOfLoop(self, pHead):
        fast = slow = pHead
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                break
        if not fast or not fast.next:
            return None
        fast = pHead
        while fast != slow:
            fast = fast.next
            slow = slow.next
        return fast

# 4. 找倒数第K个节点
class Solution:
    def FindKthToTail(self, pHead, k):
        fast = pHead
        while k > 0 and fast:
            fast = fast.next
            k -= 1
        if k > 0:
            return None
        while fast:
            fast = fast.next
            pHead = pHead.next
        return pHead

# 5. 合并两个有序链表
class Solution:
    def Merge(self, pHead1, pHead2):
        dummy = ListNode(-1)
        cur = dummy
        while pHead1 and pHead2:
            if pHead1.val <= pHead2.val:
                cur.next = pHead1
                pHead1 = pHead1.next
            else:
                cur.next = pHead2
                pHead2 = pHead2.next
            cur = cur.next
        cur.next = pHead1 if pHead1 else pHead2
        return dummy.next

2.3 题目列表

题号题目名称难度核心考察知识点
BM1反转链表简单链表遍历、指针操作
BM2链表内指定区间反转中等链表反转、虚拟头节点
BM3链表中的节点每k个一组翻转中等分组反转、链表遍历
BM4合并两个排序的链表简单归并思想、链表操作
BM5合并k个已排序的链表较难优先队列/分治、链表归并
BM6判断链表中是否有环简单快慢指针、Floyd判圈算法
BM7链表中环的入口结点中等快慢指针、数学推导
BM8链表中倒数最后k个结点简单快慢指针、链表遍历
BM9删除链表的倒数第n个节点中等快慢指针、虚拟头节点
BM10两个链表的第一个公共结点简单双指针、链表长度差
BM11链表相加(二)中等链表遍历、进位处理
BM12单链表的排序中等归并排序、链表操作
BM13判断一个链表是否为回文结构简单快慢指针、链表反转
BM14链表的奇偶重排中等链表拆分、合并
BM15删除有序链表中重复的元素-I简单链表遍历、去重
BM16删除有序链表中重复的元素-II中等虚拟头节点、重复节点删除

三、二分查找/排序专题 (BM17-BM22)

3.1 核心知识点

  • 标准二分查找
  • 查找左/右边界
  • 旋转数组查找
  • 归并排序求逆序对

3.2 Python代码模板

# 1. 标准二分查找
class Solution:
    def search(self, nums, target):
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1

# 2. 旋转数组查找
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        left, right = 0, len(rotateArray) - 1
        while left < right:
            mid = left + (right - left) // 2
            if rotateArray[mid] > rotateArray[right]:
                left = mid + 1
            elif rotateArray[mid] < rotateArray[right]:
                right = mid
            else:
                right -= 1
        return rotateArray[left]

# 3. 归并排序求逆序对
class Solution:
    def InversePairs(self, data):
        self.count = 0
        self.merge_sort(data, 0, len(data) - 1)
        return self.count % 1000000007
    
    def merge_sort(self, data, left, right):
        if left >= right:
            return
        mid = (left + right) // 2
        self.merge_sort(data, left, mid)
        self.merge_sort(data, mid + 1, right)
        self.merge(data, left, mid, right)
    
    def merge(self, data, left, mid, right):
        temp = []
        i, j = left, mid + 1
        while i <= mid and j <= right:
            if data[i] <= data[j]:
                temp.append(data[i])
                i += 1
            else:
                temp.append(data[j])
                self.count += mid - i + 1
                j += 1
        temp.extend(data[i:mid+1])
        temp.extend(data[j:right+1])
        data[left:right+1] = temp

3.3 题目列表

题号题目名称难度核心考察知识点
BM17二分查找-I简单二分查找基础
BM18二维数组中的查找中等矩阵查找、二分思想
BM19寻找峰值中等二分查找变种
BM20数组中的逆序对中等归并排序、逆序对统计
BM21旋转数组的最小数字简单二分查找、旋转数组
BM22比较版本号中等字符串处理、比较逻辑

四、二叉树专题 (BM23-BM41)

4.1 核心知识点

  • 前序、中序、后序遍历（递归与非递归）
  • 层次遍历（BFS）
  • 二叉搜索树性质（中序遍历有序）
  • 树的高度、路径、对称性判断
  • 重建二叉树

4.2 Python代码模板

# 二叉树节点定义
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 1. 前序遍历 - 递归
class Solution:
    def preorderTraversal(self, root):
        if not root:
            return []
        return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)

# 2. 中序遍历 - 迭代
class Solution:
    def inorderTraversal(self, root):
        result = []
        stack = []
        current = root
        while current or stack:
            while current:
                stack.append(current)
                current = current.left
            current = stack.pop()
            result.append(current.val)
            current = current.right
        return result

# 3. 层次遍历
from collections import deque
class Solution:
    def levelOrder(self, root):
        if not root:
            return []
        result = []
        queue = deque([root])
        while queue:
            level_size = len(queue)
            level = []
            for _ in range(level_size):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level)
        return result

# 4. 判断对称二叉树
class Solution:
    def isSymmetric(self, root):
        def check(left, right):
            if not left and not right:
                return True
            if not left or not right:
                return False
            return (left.val == right.val and 
                    check(left.left, right.right) and 
                    check(left.right, right.left))
        if not root:
            return True
        return check(root.left, root.right)

# 5. 求最大深度
class Solution:
    def maxDepth(self, root):
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

# 6. 重建二叉树
class Solution:
    def reConstructBinaryTree(self, pre, tin):
        if not pre or not tin:
            return None
        root_val = pre[0]
        root = TreeNode(root_val)
        root_index = tin.index(root_val)
        root.left = self.reConstructBinaryTree(pre[1:1+root_index], tin[:root_index])
        root.right = self.reConstructBinaryTree(pre[1+root_index:], tin[root_index+1:])
        return root

4.3 题目列表

题号题目名称难度核心考察知识点
BM23二叉树的前序遍历简单递归/迭代遍历
BM24二叉树的中序遍历简单递归/迭代遍历
BM25二叉树的后序遍历简单递归/迭代遍历
BM26求二叉树的层序遍历简单BFS、队列
BM27按之字形顺序打印二叉树中等BFS、双端队列
BM28二叉树的最大深度简单递归、DFS
BM29二叉树中和为某一值的路径(一)中等DFS、回溯
BM30二叉搜索树与双向链表中等中序遍历、树转换
BM31对称的二叉树简单递归、树对称判断
BM32合并二叉树简单递归、树合并
BM33二叉树的镜像简单递归、树翻转
BM34判断是不是二叉搜索树中等中序遍历、BST性质
BM35判断是不是完全二叉树中等BFS、完全二叉树性质
BM36判断是不是平衡二叉树中等递归、高度计算
BM37二叉搜索树的最近公共祖先简单BST性质、递归
BM38在二叉树中找到两个节点的最近公共祖先中等DFS、递归
BM39序列化二叉树较难前序遍历、字符串处理
BM40重建二叉树中等前序+中序、递归构建
BM41输出二叉树的右视图中等BFS、层序遍历

五、堆/栈/队列专题 (BM42-BM49)

5.1 核心知识点

  • 栈与队列相互实现
  • 单调栈/单调队列
  • TopK问题
  • 中缀表达式求值

5.2 Python代码模板

# 1. 用两个栈实现队列
class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    
    def push(self, node):
        self.stack1.append(node)
    
    def pop(self):
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

# 2. 包含min函数的栈
class Solution:
    def __init__(self):
        self.stack = []
        self.min_stack = []
    
    def push(self, node):
        self.stack.append(node)
        if not self.min_stack or node <= self.min_stack[-1]:
            self.min_stack.append(node)
    
    def pop(self):
        if self.stack.pop() == self.min_stack[-1]:
            self.min_stack.pop()
    
    def top(self):
        return self.stack[-1]
    
    def min(self):
        return self.min_stack[-1]

# 3. 有效括号
class Solution:
    def isValid(self, s):
        stack = []
        mapping = {')': '(', '}': '{', ']': '['}
        for char in s:
            if char in mapping:
                top = stack.pop() if stack else '#'
                if mapping[char] != top:
                    return False
            else:
                stack.append(char)
        return not stack

# 4. 滑动窗口最大值（单调队列）
from collections import deque
class Solution:
    def maxInWindows(self, num, size):
        if not num or size <= 0:
            return []
        result = []
        dq = deque()  # 存储索引
        for i, val in enumerate(num):
            # 移除窗口外的元素
            while dq and dq[0] <= i - size:
                dq.popleft()
            # 保持单调递减
            while dq and num[dq[-1]] < val:
                dq.pop()
            dq.append(i)
            if i >= size - 1:
                result.append(num[dq[0]])
        return result

5.3 题目列表

题号题目名称难度核心考察知识点
BM42用两个栈实现队列简单栈、队列、数据流转换
BM43包含min函数的栈中等辅助栈、最小值维护
BM44有效括号序列简单栈、括号匹配
BM45滑动窗口的最大值中等单调队列、滑动窗口
BM46最小的K个数中等堆、TopK问题
BM47寻找第K大中等快排思想/堆、TopK
BM48数据流中的中位数较难双堆、中位数维护
BM49表达式求值较难栈、中缀表达式求值

六、哈希专题 (BM50-BM54)

6.1 核心知识点

  • 两数之和
  • 频次统计
  • 摩尔投票法
  • 位运算

6.2 Python代码模板

# 1. 两数之和
class Solution:
    def twoSum(self, 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 []

# 2. 摩尔投票法 - 找多数元素
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        candidate = None
        count = 0
        for num in numbers:
            if count == 0:
                candidate = num
            count += 1 if num == candidate else -1
        # 验证
        return candidate if numbers.count(candidate) > len(numbers) // 2 else 0

# 3. 只出现一次的数字（两个）
class Solution:
    def singleNumber(self, nums):
        xor = 0
        for num in nums:
            xor ^= num
        # 找到最低位的1
        lowbit = xor & (-xor)
        num1 = num2 = 0
        for num in nums:
            if num & lowbit:
                num1 ^= num
            else:
                num2 ^= num
        return [num1, num2]

6.3 题目列表

题号题目名称难度核心考察知识点
BM50两数之和简单哈希表、两数配对
BM51数组中出现次数超过一半的数字简单摩尔投票法/哈希
BM52数组中只出现一次的两个数字中等位运算、哈希
BM53缺失的第一个正整数中等原地哈希、索引映射
BM54三数之和中等排序+双指针/哈希

七、递归/回溯专题 (BM55-BM61)

7.1 核心知识点

  • 全排列
  • 子集
  • N皇后
  • 岛屿数量
  • 括号生成

7.2 Python代码模板

# 回溯算法模板
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

# 1. 全排列
class Solution:
    def permute(self, nums):
        result = []
        n = len(nums)
        
        def backtrack(path, used):
            if len(path) == n:
                result.append(path[:])
                return
            for i in range(n):
                if not used[i]:
                    used[i] = True
                    path.append(nums[i])
                    backtrack(path, used)
                    path.pop()
                    used[i] = False
        
        backtrack([], [False] * n)
        return result

# 2. 子集
class Solution:
    def subsets(self, nums):
        result = []
        n = len(nums)
        
        def backtrack(start, path):
            result.append(path[:])
            for i in range(start, n):
                path.append(nums[i])
                backtrack(i + 1, path)
                path.pop()
        
        backtrack(0, [])
        return result

# 3. N皇后
class Solution:
    def solveNQueens(self, n):
        result = []
        board = [['.' for _ in range(n)] for _ in range(n)]
        
        def isValid(row, col):
            for i in range(row):
                if board[i][col] == 'Q':
                    return False
            i, j = row - 1, col - 1
            while i >= 0 and j >= 0:
                if board[i][j] == 'Q':
                    return False
                i -= 1
                j -= 1
            i, j = row - 1, col + 1
            while i >= 0 and j < n:
                if board[i][j] == 'Q':
                    return False
                i -= 1
                j += 1
            return True
        
        def backtrack(row):
            if row == n:
                result.append([''.join(row) for row in board])
                return
            for col in range(n):
                if isValid(row, col):
                    board[row][col] = 'Q'
                    backtrack(row + 1)
                    board[row][col] = '.'
        
        backtrack(0)
        return result

# 4. 岛屿数量
class Solution:
    def numIslands(self, grid):
        if not grid:
            return 0
        m, n = len(grid), len(grid[0])
        count = 0
        
        def dfs(i, j):
            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1':
                return
            grid[i][j] = '0'  # 标记已访问
            dfs(i+1, j)
            dfs(i-1, j)
            dfs(i, j+1)
            dfs(i, j-1)
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    count += 1
                    dfs(i, j)
        return count

7.3 题目列表

题号题目名称难度核心考察知识点
BM55没有重复项数字的全排列中等回溯、全排列
BM56有重复项数字的全排列中等回溯、去重
BM57岛屿数量中等DFS/BFS、连通块
BM58字符串的排列中等回溯、字符串排列
BM59N皇后问题困难回溯、剪枝
BM60括号生成中等回溯、括号组合
BM61矩阵最长递增路径中等记忆化搜索、DFS

八、动态规划专题 (BM62-BM82)

8.1 核心知识点

  • 状态定义: dp[i]或dp[i][j]的含义
  • 状态转移方程: 如何从子问题推导出当前问题
  • 初始化: base case
  • 遍历顺序: 确保计算当前状态时，依赖的状态已计算

8.2 Python代码模板

# 1. 斐波那契数列 - 状态压缩
class Solution:
    def Fibonacci(self, n):
        if n <= 1:
            return n
        prev2, prev1 = 0, 1
        for i in range(2, n + 1):
            current = prev1 + prev2
            prev2, prev1 = prev1, current
        return prev1

# 2. 连续子数组最大和
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        dp = [0] * len(array)
        dp[0] = array[0]
        max_sum = array[0]
        for i in range(1, len(array)):
            dp[i] = max(array[i], dp[i-1] + array[i])
            max_sum = max(max_sum, dp[i])
        return max_sum

# 3. 最长公共子序列 (LCS)
class Solution:
    def longestCommonSubsequence(self, text1, text2):
        m, n = len(text1), len(text2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return dp[m][n]

# 4. 最长上升子序列
class Solution:
    def lengthOfLIS(self, nums):
        if not nums:
            return 0
        dp = [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)

# 5. 0-1背包问题
class Solution:
    def knapsack(self, weights, values, capacity):
        n = len(weights)
        dp = [0] * (capacity + 1)
        for i in range(n):
            for j in range(capacity, weights[i] - 1, -1):
                dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
        return dp[capacity]

# 6. 完全背包（正序遍历）
class Solution:
    def complete_knapsack(self, weights, values, capacity):
        n = len(weights)
        dp = [0] * (capacity + 1)
        for i in range(n):
            for j in range(weights[i], capacity + 1):
                dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
        return dp[capacity]

# 7. 股票问题 - 买卖股票的最佳时机
class Solution:
    def maxProfit(self, prices):
        if not prices:
            return 0
        min_price = prices[0]
        max_profit = 0
        for price in prices:
            min_price = min(min_price, price)
            max_profit = max(max_profit, price - min_price)
        return max_profit

# 8. 编辑距离
class Solution:
    def minDistance(self, 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] = i
        for j in range(n + 1):
            dp[0][j] = j
        for 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] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
        return dp[m][n]

8.3 题目列表

题号题目名称难度核心考察知识点
BM62斐波那契数列入门DP基础、递推
BM63跳台阶简单DP、递推
BM64最小花费爬楼梯简单DP、状态转移
BM65最长公共子序列(二)中等二维DP、LCS
BM66最长公共子串中等二维DP、子串
BM67不同路径的数目(一)简单二维DP、路径计数
BM68矩阵的最小路径和中等二维DP、路径DP
BM69把数字翻译成字符串中等DP、字符串解码
BM70兑换零钱(一)中等完全背包、DP
BM71最长上升子序列(一)中等一维DP、LIS
BM72连续子数组的最大和简单一维DP、最大子数组
BM73最长回文子串中等中心扩展/DP
BM74数字字符串转化成IP地址中等回溯/DP、字符串分割
BM75编辑距离(一)较难二维DP、经典问题
BM76正则表达式匹配困难二维DP、复杂状态
BM77最长的括号子串中等栈/DP、括号匹配
BM78打家劫舍(一)中等一维DP、状态转移
BM79打家劫舍(二)中等一维DP、环形数组
BM80买卖股票的最好时机(一)简单一维DP、股票问题
BM81买卖股票的最好时机(二)中等一维DP、无限交易
BM82买卖股票的最好时机(三)中等二维DP、有限交易

九、字符串专题 (BM83-BM86)

9.1 核心知识点

  • 字符串操作
  • 最长公共前缀
  • IP地址验证
  • 大数运算

9.2 Python代码模板

# 1. 最长公共前缀
class Solution:
    def longestCommonPrefix(self, strs):
        if not strs:
            return ""
        prefix = strs[0]
        for s in strs[1:]:
            while not s.startswith(prefix):
                prefix = prefix[:-1]
                if not prefix:
                    return ""
        return prefix

# 2. 大数加法
class Solution:
    def solve(self, s, t):
        result = []
        i, j = len(s) - 1, len(t) - 1
        carry = 0
        while i >= 0 or j >= 0 or carry:
            num1 = int(s[i]) if i >= 0 else 0
            num2 = int(t[j]) if j >= 0 else 0
            total = num1 + num2 + carry
            result.append(str(total % 10))
            carry = total // 10
            i -= 1
            j -= 1
        return ''.join(reversed(result))

9.3 题目列表

题号题目名称难度核心考察知识点
BM83字符串变形简单字符串操作、空格处理
BM84最长公共前缀简单字符串比较、纵向扫描
BM85验证IP地址中等字符串处理、IP验证
BM86大数加法简单字符串模拟、大数运算

十、双指针专题 (BM87-BM94)

10.1 核心知识点

  • 对撞指针
  • 快慢指针
  • 滑动窗口

10.2 Python代码模板

# 1. 对撞指针 - 两数之和
class Solution:
    def twoSum(self, nums, target):
        left, right = 0, len(nums) - 1
        while left < right:
            current = nums[left] + nums[right]
            if current == target:
                return [left + 1, right + 1]
            elif current < target:
                left += 1
            else:
                right -= 1
        return []

# 2. 滑动窗口 - 最长无重复子串
class Solution:
    def lengthOfLongestSubstring(self, s):
        char_index = {}
        left = 0
        max_len = 0
        for right, char in enumerate(s):
            if char in char_index and char_index[char] >= left:
                left = char_index[char] + 1
            char_index[char] = right
            max_len = max(max_len, right - left + 1)
        return max_len

# 3. 接雨水
class Solution:
    def trap(self, height):
        if not height:
            return 0
        left, right = 0, len(height) - 1
        left_max = right_max = 0
        water = 0
        while left < right:
            if height[left] < height[right]:
                if height[left] >= left_max:
                    left_max = height[left]
                else:
                    water += left_max - height[left]
                left += 1
            else:
                if height[right] >= right_max:
                    right_max = height[right]
                else:
                    water += right_max - height[right]
                right -= 1
        return water

10.3 题目列表

题号题目名称难度核心考察知识点
BM87合并两个有序的数组简单双指针、从后向前
BM88判断是否为回文字符串简单双指针、回文判断
BM89合并区间中等排序、双指针、区间合并
BM90最小覆盖子串困难滑动窗口、双指针
BM91反转字符串简单双指针、原地交换
BM92最长无重复子数组中等滑动窗口、哈希
BM93盛水最多的容器中等双指针、面积计算
BM94接雨水问题中等双指针/单调栈、接雨水

十一、贪心专题 (BM95-BM96)

11.1 核心知识点

  • 区间调度
  • 贪心策略

11.2 题目列表

题号题目名称难度核心考察知识点
BM95分糖果问题中等贪心、两次遍历
BM96主持人调度（二）中等贪心、区间调度

十二、模拟/设计专题 (BM97-BM101)

12.1 核心知识点

  • 数组旋转
  • 螺旋矩阵
  • LRU/LFU缓存设计

12.2 Python代码模板

# 1. 旋转数组
class Solution:
    def rotate(self, nums, k):
        k %= len(nums)
        nums[:] = nums[-k:] + nums[:-k]

# 2. 螺旋矩阵
class Solution:
    def spiralOrder(self, matrix):
        if not matrix:
            return []
        result = []
        top, bottom = 0, len(matrix) - 1
        left, right = 0, len(matrix[0]) - 1
        while top <= bottom and left <= right:
            for i in range(left, right + 1):
                result.append(matrix[top][i])
            top += 1
            for i in range(top, bottom + 1):
                result.append(matrix[i][right])
            right -= 1
            if top <= bottom:
                for i in range(right, left - 1, -1):
                    result.append(matrix[bottom][i])
                bottom -= 1
            if left <= right:
                for i in range(bottom, top - 1, -1):
                    result.append(matrix[i][left])
                left += 1
        return result

# 3. LRU缓存
from collections import OrderedDict
class Solution:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()
    
    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]
    
    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

12.3 题目列表

题号题目名称难度核心考察知识点
BM97旋转数组简单三次反转、数组操作
BM98螺旋矩阵中等模拟、边界控制
BM99顺时针旋转矩阵中等矩阵转置、翻转
BM100设计LRU缓存结构中等哈希+双向链表
BM101设计LFU缓存结构困难哈希+多链表

附录：时间/空间复杂度速查表

算法类型典型时间复杂度空间复杂度
数组遍历O(n)O(1)
双指针O(n)O(1)
二分查找O(log n)O(1)
哈希查找O(1)O(n)
快速排序O(n log n)平均O(log n)
归并排序O(n log n)O(n)
堆排序O(n log n)O(1)
二叉树遍历O(n)O(h)
图的BFS/DFSO(V+E)O(V)
动态规划O(n)或O(n²)O(n)或O(n²)
回溯算法O(2ⁿ)或O(n!)O(n)

参考资源

# 面试 # python # 算法
Logo
亚马逊云科技技术品牌专区

更多推荐

open-code-review Codex 插件教程：对话式调用评审技能指南

本文是一份面向新手的 **open-code-review Codex 插件教程**，教你在 Codex 中通过对话式方式调用 open-code-review 的 AI 代码评审技能。open-code-review 是阿里巴巴开源的 AI 代码评审工具，采用"确定性流水线 + LLM Agent"混合架构，内置多语言评审规则（NPE、线程安全、XSS、SQL 注入等），可在 Codex 里用一

avatar 亚马逊云科技技术品牌专区

OBS Studio 完整指南：免费开源录屏与直播软件从零上手

想做一场像模像样的直播，或者把屏幕内容录成教程视频，但一想到商用软件的订阅费就有些犹豫？其实你不需要花一分钱。OBS Studio 是一款免费开源的直播与录屏软件，支持 Windows、macOS 和 Linux，采集、混音、编码、推流、录制，一条流水线全包了。## 先搞清楚 OBS Studio 是什么OBS Studio 是一个"场景化"的采集合成工具：你把摄像头、窗口、浏览器、图片、

avatar 亚马逊云科技技术品牌专区

如何用MediaCrawler爬取小红书抖音数据？7大平台爬虫从安装到实战完整指南

MediaCrawler 是一个支持小红书、抖音、快手、B站、微博、百度贴吧、知乎的开源自媒体数据采集工具。它能按关键词、按帖子、按创作者主页三种方式抓取笔记/视频内容、评论甚至二级评论，并把结果存成 JSON、CSV、Excel 或数据库。适合做市场调研、竞品监控、内容选题的运营人员，以及想要现成爬虫框架而不想从零写 JS 逆向的开发者。## 从一次"手动抄数据"说起想象这个场景：你负责

avatar 亚马逊云科技技术品牌专区