1. 笔试强训Week1题目解析作为一名经历过无数次笔试面试的老程序员我深知算法题在技术面试中的重要性。今天我要分享的这套笔试强训Week1题目包含了字符串处理、数组操作、模拟题和大数运算等经典题型都是各大厂笔试中的高频考点。这套题目由浅入深覆盖了以下五个经典问题点击消除字符串栈应用数组中两个字符串的最小距离数组遍历技巧dd爱框框滑动窗口/前缀和腐烂的苹果BFS应用大数乘法字符串模拟运算接下来我将逐个拆解每道题的核心思路和解题技巧分享我在实际编码和面试中积累的经验。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 边界条件与测试用例需要特别注意的边界情况空字符串输入全部字符都可消除的情况如aaaa无任何消除的情况如abcde交替消除的情况如abba→3. 数组中两个字符串的最小距离3.1 问题描述给定一个字符串数组strs和两个字符串str1、str2找出它们在数组中最近的距离。例如 strs [1,3,3,3,2,3,1], str1 1, str2 2 → 输出23.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 -13.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:right1] 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 -15.3 复杂度与注意事项时间复杂度O(mn) 空间复杂度O(mn)关键点需要先统计初始状态的新鲜苹果数量使用队列层级遍历保证时间计算准确最后要检查是否还有剩余新鲜苹果6. 大数乘法字符串模拟运算6.1 问题背景当数字超过语言基本类型的表示范围时如1000位的整数需要用字符串表示并模拟手工乘法过程。6.2 算法思路模拟竖式乘法从右到左逐位相乘处理进位累加中间结果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 优化与边界处理处理输入为0的情况直接返回结果数组大小设为mn足够存放乘积注意去除前导零可以优化Karatsuba算法达到O(n^1.585)复杂度7. 综合训练建议通过这五道题的训练可以掌握以下核心技能栈在字符串处理中的应用数组遍历与双指针技巧滑动窗口解决连续子数组问题多源BFS在网格问题中的应用字符串模拟大数运算在实际笔试中建议先理解清楚题目要求多举几个例子分析时间空间复杂度选择合适算法注意边界条件和特殊输入写代码时保持清晰的变量命名和注释完成后用测试用例验证我在面试候选人时发现能够清晰解释解题思路并处理边界条件的候选人往往在实际工作中也表现出色。算法题不仅是考察编码能力更是考察问题分析和解决能力的窗口。
算法笔试高频题型解析：栈、滑动窗口与BFS实战
1. 笔试强训Week1题目解析作为一名经历过无数次笔试面试的老程序员我深知算法题在技术面试中的重要性。今天我要分享的这套笔试强训Week1题目包含了字符串处理、数组操作、模拟题和大数运算等经典题型都是各大厂笔试中的高频考点。这套题目由浅入深覆盖了以下五个经典问题点击消除字符串栈应用数组中两个字符串的最小距离数组遍历技巧dd爱框框滑动窗口/前缀和腐烂的苹果BFS应用大数乘法字符串模拟运算接下来我将逐个拆解每道题的核心思路和解题技巧分享我在实际编码和面试中积累的经验。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 边界条件与测试用例需要特别注意的边界情况空字符串输入全部字符都可消除的情况如aaaa无任何消除的情况如abcde交替消除的情况如abba→3. 数组中两个字符串的最小距离3.1 问题描述给定一个字符串数组strs和两个字符串str1、str2找出它们在数组中最近的距离。例如 strs [1,3,3,3,2,3,1], str1 1, str2 2 → 输出23.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 -13.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:right1] 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 -15.3 复杂度与注意事项时间复杂度O(mn) 空间复杂度O(mn)关键点需要先统计初始状态的新鲜苹果数量使用队列层级遍历保证时间计算准确最后要检查是否还有剩余新鲜苹果6. 大数乘法字符串模拟运算6.1 问题背景当数字超过语言基本类型的表示范围时如1000位的整数需要用字符串表示并模拟手工乘法过程。6.2 算法思路模拟竖式乘法从右到左逐位相乘处理进位累加中间结果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 优化与边界处理处理输入为0的情况直接返回结果数组大小设为mn足够存放乘积注意去除前导零可以优化Karatsuba算法达到O(n^1.585)复杂度7. 综合训练建议通过这五道题的训练可以掌握以下核心技能栈在字符串处理中的应用数组遍历与双指针技巧滑动窗口解决连续子数组问题多源BFS在网格问题中的应用字符串模拟大数运算在实际笔试中建议先理解清楚题目要求多举几个例子分析时间空间复杂度选择合适算法注意边界条件和特殊输入写代码时保持清晰的变量命名和注释完成后用测试用例验证我在面试候选人时发现能够清晰解释解题思路并处理边界条件的候选人往往在实际工作中也表现出色。算法题不仅是考察编码能力更是考察问题分析和解决能力的窗口。