算法笔试高频题型解析：栈、滑动窗口与BFS实战

1. 笔试强训Week1题目解析

作为一名经历过无数次笔试面试的老程序员，我深知算法题在技术面试中的重要性。今天我要分享的这套"笔试强训Week1"题目，包含了字符串处理、数组操作、模拟题和大数运算等经典题型，都是各大厂笔试中的高频考点。

这套题目由浅入深，覆盖了以下五个经典问题：

1. 点击消除（字符串栈应用）
2. 数组中两个字符串的最小距离（数组遍历技巧）
3. dd爱框框（滑动窗口/前缀和）
4. 腐烂的苹果（BFS应用）
5. 大数乘法（字符串模拟运算）

接下来我将逐个拆解每道题的核心思路和解题技巧，分享我在实际编码和面试中积累的经验。

2. 点击消除：字符串与栈的完美结合

2.1 题目理解与示例分析

点击消除的规则是：当出现相邻相同字符时，它们会被消除。这个过程会持续进行，直到没有可以消除的字符为止。例如：

• 输入 "abbaca" → 消除 "bb" → "aaca" → 消除 "aa" → "ca"

这道题本质上考察的是字符串处理和栈的应用。很多同学第一反应是用循环不断扫描字符串进行消除，但这种做法在最坏情况下（如"aaaaaa"）时间复杂度会达到O(n²)。

2.2 最优解：栈的应用

更高效的解法是使用栈结构：

def remove_duplicates(s: str) -> str: stack = [] for char in s: if stack and stack[-1] == char: stack.pop() else: stack.append(char) return ''.join(stack)

时间复杂度：O(n) 空间复杂度：O(n)

关键点：当遇到相同字符时弹出栈顶元素，否则压入栈。最后栈中剩余字符就是结果。

2.3 边界条件与测试用例

需要特别注意的边界情况：

1. 空字符串输入
2. 全部字符都可消除的情况（如"aaaa"）
3. 无任何消除的情况（如"abcde"）
4. 交替消除的情况（如"abba"→""）

3. 数组中两个字符串的最小距离

3.1 问题描述

给定一个字符串数组strs和两个字符串str1、str2，找出它们在数组中最近的距离。例如： strs = ["1","3","3","3","2","3","1"], str1 = "1", str2 = "2" → 输出2

3.2 双指针解法

最直观的解法是记录两个字符串所有出现位置，然后计算最小差值，但这样需要O(n²)时间复杂度。

更优解法是在一次遍历中记录最近出现的str1和str2位置：

def min_distance(strs, str1, str2): index1 = -1 # str1最近出现位置 index2 = -1 # str2最近出现位置 min_dist = float('inf') for i, s in enumerate(strs): if s == str1: index1 = i if index2 != -1: min_dist = min(min_dist, index1 - index2) elif s == str2: index2 = i if index1 != -1: min_dist = min(min_dist, index2 - index1) return min_dist if min_dist != float('inf') else -1

3.3 优化与变种

1. 如果数组中有大量重复查询，可以预处理建立哈希表记录每个字符串的所有位置
2. 变种题：求多个字符串的最小距离（需要扩展记录多个索引）
3. 如果str1和str2相同的情况需要特殊处理

4. dd爱框框：滑动窗口的经典应用

4.1 题目理解

给定一个数组和一个目标值x，找到和≥x的最短连续子数组。例如： nums = [1,2,3,4,5], x = 9 → 输出[4,5]

4.2 滑动窗口解法

这类求连续子数组的问题通常可以用滑动窗口解决：

def min_subarray(nums, x): left = 0 current_sum = 0 min_len = float('inf') result = [] for right in range(len(nums)): current_sum += nums[right] while current_sum >= x: if right - left + 1 < min_len: min_len = right - left + 1 result = nums[left:right+1] current_sum -= nums[left] left += 1 return result if min_len != float('inf') else []

4.3 复杂度分析与优化

时间复杂度：O(n) —— 每个元素最多被访问两次 空间复杂度：O(1)

实际编码时要注意窗口滑动条件和结果更新的时机，这是最容易出错的地方。

5. 腐烂的苹果：多源BFS应用

5.1 问题描述

给定一个m×n的网格，每个格子可能有：

• 0表示空单元格
• 1表示新鲜苹果
• 2表示腐烂苹果

每分钟，腐烂苹果会使相邻（上下左右）的新鲜苹果腐烂。求所有苹果腐烂所需时间，或返回-1表示不可能。

5.2 多源BFS解法

典型的多源广度优先搜索问题：

def orangesRotting(grid): from collections import deque m, n = len(grid), len(grid[0]) queue = deque() fresh = 0 time = 0 # 初始化：记录所有腐烂苹果位置和新鲜苹果数量 for i in range(m): for j in range(n): if grid[i][j] == 2: queue.append((i, j)) elif grid[i][j] == 1: fresh += 1 # 如果没有新鲜苹果 if fresh == 0: return 0 # BFS过程 directions = [(-1,0),(1,0),(0,-1),(0,1)] while queue and fresh > 0: time += 1 for _ in range(len(queue)): x, y = queue.popleft() for dx, dy in directions: nx, ny = x + dx, y + dy if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1: grid[nx][ny] = 2 fresh -= 1 queue.append((nx, ny)) return time if fresh == 0 else -1

5.3 复杂度与注意事项

时间复杂度：O(mn) 空间复杂度：O(mn)

关键点：

1. 需要先统计初始状态的新鲜苹果数量
2. 使用队列层级遍历保证时间计算准确
3. 最后要检查是否还有剩余新鲜苹果

6. 大数乘法：字符串模拟运算

6.1 问题背景

当数字超过语言基本类型的表示范围时（如1000位的整数），需要用字符串表示并模拟手工乘法过程。

6.2 算法思路

模拟竖式乘法：

1. 从右到左逐位相乘
2. 处理进位
3. 累加中间结果

def multiply(num1: str, num2: str) -> str: if num1 == "0" or num2 == "0": return "0" m, n = len(num1), len(num2) result = [0] * (m + n) # 从低位到高位逐位相乘 for i in range(m-1, -1, -1): for j in range(n-1, -1, -1): mul = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0')) p1, p2 = i + j, i + j + 1 total = mul + result[p2] result[p2] = total % 10 result[p1] += total // 10 # 去除前导零 start = 0 while start < len(result) and result[start] == 0: start += 1 return ''.join(map(str, result[start:]))

6.3 优化与边界处理

1. 处理输入为"0"的情况直接返回
2. 结果数组大小设为m+n足够存放乘积
3. 注意去除前导零
4. 可以优化Karatsuba算法达到O(n^1.585)复杂度

7. 综合训练建议

通过这五道题的训练，可以掌握以下核心技能：

1. 栈在字符串处理中的应用
2. 数组遍历与双指针技巧
3. 滑动窗口解决连续子数组问题
4. 多源BFS在网格问题中的应用
5. 字符串模拟大数运算

在实际笔试中，建议：

• 先理解清楚题目要求，多举几个例子
• 分析时间空间复杂度，选择合适算法
• 注意边界条件和特殊输入
• 写代码时保持清晰的变量命名和注释
• 完成后用测试用例验证

我在面试候选人时发现，能够清晰解释解题思路并处理边界条件的候选人，往往在实际工作中也表现出色。算法题不仅是考察编码能力，更是考察问题分析和解决能力的窗口。