## 1. 从“万万没想到”开始：字节跳动春招Python编程题的敲门砖 又到了一年一度的春招季，对于想冲进字节跳动这类大厂的同学们来说，算法笔试是绕不过去的一道坎。我当年也经历过这个阶段，刷了无数道题，但真正到了考场上才发现，大厂的题目往往有自己的“套路”。它们不追求冷僻的算法，反而特别喜欢在字符串处理、数组操作这些基础场景上，结合巧妙的逻辑和边界条件，来考察你的代码基本功和思维严谨性。就拿字节跳动2023年春招（以及往年）的题目来说，很多都披着一层有趣的故事外衣，比如“聪明的编辑”、“抓捕孔连顺”，但内核依然是扎实的编程能力考察。 我们先从最经典的“万万没想到之聪明的编辑”这道题入手。题目背景是编辑王大锤要校对英文稿件，规则就两条：第一，三个同样的字母连在一起（AAA），去掉一个；第二，两对一样的字母以AABB形式连在一起，去掉第二个B。规则还强调了“从左到右”的匹配优先级。这题乍一看很简单，不就是遍历字符串然后删减吗？但如果你真这么想，可能就要踩坑了。我最初实现的时候，就犯了一个错误：直接在原字符串上边遍历边删除。这在Python里是大忌，因为改变序列长度会影响迭代器的行为，很容易导致下标错乱或者漏掉字符。 正确的做法是引入一个“写指针”的概念。我们可以把原字符串想象成一个只读的输入流，再准备一个空列表作为输出流。用一个指针`k`指向输出列表的当前位置，然后遍历输入字符串的每个字符。核心逻辑是：每读入一个字符，就先把它写到输出列表的`k`位置，然后`k`自增。紧接着，我们检查以`k-1`为结尾的这段输出列表，是否构成了AAA或者AABB模式。注意，这里检查的是**输出列表**，而不是原输入字符串。如果发现AAA（即`s[k-3] == s[k-2] == s[k-1]`），那么说明刚写的这个字符是多余的，我们只需要把写指针`k`回退一位，相当于“覆盖”掉它。AABB的模式检查同理。这种方法一次遍历就能搞定，时间复杂度O(n)，空间复杂度O(n)（用于存储输出列表），非常高效。 ```python def smart_editor(s): """ 智能校对函数 :param s: 输入字符串 :return: 校对后的字符串 """ s_list = list(s) # 转换为列表方便操作 k = 0 # 写指针，指向结果列表的当前位置 for i in range(len(s_list)): # 将当前字符写入结果位置 s_list[k] = s_list[i] k += 1 # 检查是否出现 AAA if k >= 3 and s_list[k-3] == s_list[k-2] == s_list[k-1]: k -= 1 # 回退指针，相当于删除最后一个字符 # 检查是否出现 AABB if k >= 4 and s_list[k-4] == s_list[k-3] and s_list[k-2] == s_list[k-1]: k -= 1 # 回退指针，相当于删除最后一个字符（第二个B） return ''.join(s_list[:k]) # 将结果列表前k个字符拼接成字符串 # 测试用例 print(smart_editor("helloo")) # 输出: hello print(smart_editor("woooooow")) # 输出: woow print(smart_editor("aabbcc")) # 输出: aabcc (验证从左到右优先级) ``` 这道题给我的启示是，处理字符串修改问题时，**“双指针”或“读写指针”是避免索引混乱的黄金法则**。同时，一定要仔细审题，理解“从左到右匹配”的含义。比如`"aabbcc"`，AABB和BBCC都是错误，但优先修复前面的AABB，结果应该是`"aabcc"`。这种对细节的把握，正是面试官想要看到的。 ## 2. 组合数学与双指针的巧妙结合：埋伏方案数计算 如果说第一题考的是基本功，那“万万没想到之抓捕孔连顺”这道题，就开始上难度了，它完美结合了**双指针**和**组合数学**。题目大意是，在一条数轴上有N个建筑作为埋伏点，三名特工要选择三个不同的点埋伏，并且最远的两名特工距离不能超过D。我们需要计算有多少种不同的埋伏方案。这里有个关键点：特工是等价的，所以`(A, B, C)`和`(B, A, C)`是同一种方案。 暴力解法当然是三重循环枚举所有组合，检查距离条件。但N最大可以到100万，O(N³)的复杂度想都别想。我们必须找到更优的方法。这里就需要用到**排序数组**和**双指针**来优化。因为建筑坐标已经从小到大排序，这是一个非常重要的提示。我们可以固定第一个特工的位置`i`，那么问题就转化为：在`i`之后的坐标中，找到所有满足`nums[j] - nums[i] <= D`的`j`，然后从`(i+1)`到`j`这个区间里，任意选出两个位置给另外两个特工。 具体怎么找这个`j`呢？用另一个指针`j`去探索。对于每个固定的`i`，我们让`j`从`i+2`开始（因为至少需要三个不同的点），不断向右移动，直到`nums[j] - nums[i] > D` 或者 `j`超出数组范围。此时，`j-1`就是对于当前`i`来说，最远的那个符合条件的下标。那么，在`i+1`到`j-1`这个闭区间内，有多少个点呢？是`(j-1) - i`个。我们需要从中选出2个点给另外两名特工，方案数就是组合数 **C(cnt, 2)**，其中`cnt = (j-1) - i`。 这里有个细节，`cnt`可能小于2，此时组合数为0。计算组合数公式是`C(cnt, 2) = cnt * (cnt - 1) // 2`。最后，我们把所有`i`对应的方案数累加起来，就是总方案数。由于结果可能很大，题目要求对`99997867`取模。 ```python def ambush_scheme(N, D, buildings): """ 计算埋伏方案数 :param N: 建筑数量 :param D: 最大允许距离 :param buildings: 建筑坐标列表 :return: 方案数 % MOD """ MOD = 99997867 res = 0 j = 0 # 快指针，探索最远边界 # 固定第一个特工的位置 i for i in range(N - 2): # i最多取到倒数第三个建筑 # 移动j，找到满足 buildings[j] - buildings[i] <= D 的最远j while j < N and buildings[j] - buildings[i] <= D: j += 1 # 此时，符合条件的右边界是 j-1 # 计算从 i+1 到 j-1 之间有多少个点 cnt = j - i - 1 if cnt >= 2: # 组合数 C(cnt, 2) res = (res + cnt * (cnt - 1) // 2) % MOD return res # 测试用例 print(ambush_scheme(4, 3, [1, 2, 3, 4])) # 输出: 4 print(ambush_scheme(5, 19, [1, 10, 20, 30, 50])) # 输出: 1 ``` 这个算法的核心是，指针`j`随着`i`的增大而单调向右移动，不会回退。因此，`i`和`j`各自遍历了整个数组一次，时间复杂度是O(N)。这比暴力法高效太多了。在实际面试中，如果你能清晰地解释为什么`j`不需要回退（因为数组有序，`i`增大后，`nums[i]`变大，之前满足`nums[j] - old_i <= D`的`j`，现在肯定更满足`nums[j] - new_i <= D`），面试官一定会眼前一亮。 ## 3. 递归与回溯的经典战场：麻将和牌判断 “雀魂启动！”这道题可以说是字节跳动笔试中的“明星题”，它考察的是**递归回溯**和**问题建模**能力。题目背景是简化版的麻将，数字1~9，每种4张，共36张。手牌14张和牌的条件是：有一对雀头（两张相同的牌），剩下的12张牌必须能组成4个顺子（如123）或刻子（如111）。现在给你13张牌，问摸哪张牌可以和牌。 最直接的思路就是暴力枚举。我们遍历所有可能摸到的牌（1-9，但要考虑已有牌数不能超过4张），将这张牌加入手牌，然后判断这14张牌是否能和牌。判断和牌的函数是核心难点。这里就需要用到递归回溯的思想。 和牌的本质是，14张牌可以被**完全划分**为1个雀头（2张）和4个面子（顺子或刻子，各3张）。递归函数的思路是：尝试从当前牌堆中，移除一个可能的雀头或面子，然后对剩下的牌递归调用判断。如果最后牌堆能被清空，说明可以和牌。 具体实现时，为了效率，我们通常将手牌表示为一个长度为10的计数列表`count`，`count[i]`表示数字`i`出现的次数（1-9）。递归函数`is_win(count)`判断当前牌型能否和牌： 1. **找雀头**：遍历1-9，如果某个数字`i`的数量`>=2`，我们假设它是雀头，将`count[i]`减去2，然后递归判断剩下的牌能否组成4个面子。递归返回后记得恢复`count[i]`（回溯）。 2. **找面子**：如果找不到雀头或者雀头尝试失败，就尝试组面子。面子有两种： * **刻子**：遍历1-9，如果`count[i] >= 3`，减去3后递归。 * **顺子**：遍历1-7，如果`count[i] > 0, count[i+1] > 0, count[i+2] > 0`，说明可以组成顺子`i, i+1, i+2`，各减1后递归。 3. **递归基**：如果牌的总张数已经是0（意味着所有牌都被成功分组），返回`True`。如果所有尝试都失败，返回`False`。 这里有一个重要的优化：**确定雀头**。因为雀头是必须的，我们可以在递归外层就先确定雀头候选。对于14张牌，雀头数字`i`必须满足`count[i] >= 2`。确定雀头后，问题就简化为判断剩下的12张牌能否组成4个面子，这时只需要递归尝试组成刻子或顺子即可。 ```python def can_win(count): """ 判断当前牌型（计数列表）能否和牌（已确定雀头） 简化版：此函数假设雀头已移除，判断剩余12张能否组成4个面子 """ # 递归基：所有牌都用完了 if sum(count) == 0: return True # 尝试刻子 for i in range(1, 10): if count[i] >= 3: count[i] -= 3 if can_win(count): count[i] += 3 # 回溯 return True count[i] += 3 # 回溯 # 尝试顺子 (1-7) for i in range(1, 8): if count[i] > 0 and count[i+1] > 0 and count[i+2] > 0: count[i] -= 1 count[i+1] -= 1 count[i+2] -= 1 if can_win(count): # 回溯 count[i] += 1 count[i+1] += 1 count[i+2] += 1 return True # 回溯 count[i] += 1 count[i+1] += 1 count[i+2] += 1 return False def find_win_tile(hand_13): """ 主函数：寻找和牌牌 :param hand_13: 13张手牌的列表 :return: 可能和牌的牌列表 """ from collections import Counter cnt = Counter(hand_13) result = [] # 尝试添加每一张可能的牌 for tile in range(1, 10): # 检查这张牌是否还能加入（不超过4张） if cnt[tile] >= 4: continue # 构造14张牌的计数 test_cnt = [0] * 10 for k, v in cnt.items(): test_cnt[k] = v test_cnt[tile] += 1 # 尝试每一种可能的雀头 win_flag = False for head in range(1, 10): if test_cnt[head] >= 2: test_cnt[head] -= 2 # 移除雀头 if can_win(test_cnt): win_flag = True test_cnt[head] += 2 # 恢复 if win_flag: break if win_flag: result.append(tile) return result if result else [0] # 测试用例 print(find_win_tile([1,1,1,2,2,2,5,5,5,6,6,6,9])) # 输出: [9] print(find_win_tile([1,1,1,1,2,2,3,3,5,6,7,8,9])) # 输出: [4, 7] ``` 这道题代码写起来有点长，但思路是清晰的。它考察的是你将一个复杂规则转化为递归搜索的能力，以及编写回溯代码时“恢复状态”的严谨性。在实际面试中，即使不能完全写对，如果能清晰地阐述递归和回溯的思路，也能拿到不少分数。 ## 4. 哈希映射与状态追踪：最长特征运动 “特征提取”这道题看起来描述很复杂，什么猫咪特征、连续帧，其实核心就是一个**哈希表（字典）** 的灵活运用。题目要求我们找到，在视频的多帧序列中，同一个二维特征向量连续出现的最大长度。 关键点在于“连续”。特征`<1,1>`在第2、3、4帧出现，算连续长度为3；如果在第7、8帧又出现，那就是另一个长度为2的运动。我们需要找出所有特征中，最长的那个连续长度。 最笨的方法是为每个特征维护一个列表，记录它在哪些帧出现，然后扫描列表找最长连续段。但帧数M和特征总数都可能很大（10^4量级），我们需要一种在遍历过程中就能动态计算并更新最长长度的办法。 这里就用到了**两个哈希表**的技巧。我们用一个字典`last_seen`来记录**每个特征在上一个连续运动中的长度**。但注意，这个“上一个连续运动”必须是刚结束的。我们还需要一个`current`字典来记录**在当前帧中，每个特征连续运动到了多长**。 具体算法如下： 1. 遍历每一帧。 2. 对于当前帧中的每一个特征，我们生成一个唯一的key（比如把坐标`(x,y)`映射成一个整数`x*BASE + y`，BASE取一个比最大坐标大的数，比如1000000）。 3. 检查这个key是否存在于`last_seen`字典中： * 如果存在，说明这个特征在上一帧（或更早但连续）出现过。那么它在当前帧的连续长度就是`last_seen[key] + 1`。 * 如果不存在，说明它是当前连续段的开始，长度为1。 4. 将计算出的新长度存入`current[key]`，并更新全局最大长度`max_len`。 5. **关键一步**：处理完当前帧的所有特征后，将`last_seen`更新为`current`。因为下一帧的“上一帧”就是当前帧。而那些在当前帧没有出现的特征，其连续运动在当前帧就中断了，所以在`current`中自然就没有了，`last_seen`被覆盖后，这些特征的信息就被清除了，完美符合“连续”的定义。 ```python def longest_feature_movement(test_cases): """ 计算最长特征运动 :param test_cases: 一个列表，每个元素是一个列表的列表，代表一个测试用例的多帧特征 :return: 每个测试用例的最长特征运动长度列表 """ results = [] for frames in test_cases: max_len = 1 last_seen = {} # 记录特征在上一帧的连续长度 for frame in frames: current = {} for feature in frame: # 将特征(x,y)编码为一个唯一key，简单起见用元组 key = tuple(feature) # 如果上一帧有这个特征，则连续长度+1，否则从1开始 current[key] = last_seen.get(key, 0) + 1 # 更新全局最大值 max_len = max(max_len, current[key]) # 当前帧处理完毕，作为下一帧的“上一帧” last_seen = current results.append(max_len) return results # 模拟输入例子1 # 用例1: 8帧 # 帧1: 2个特征 (1,1), (2,2) # 帧2: 1个特征 (1,1) # 帧3: 1个特征 (1,1) # 帧4: 2个特征 (1,1), (2,2) # 帧5: 2个特征 (2,2), (2,2) # 注意这里有两个相同的(2,2)，但根据题意，同一帧内相同特征只算一个？题目说“特征个数”，通常理解为集合。这里我们按集合处理。 # 帧6: 1个特征 (1,1) # 帧7: 0个特征 # 帧8: 1个特征 (1,1) # 为了简化，我们假设输入已经按帧整理好，且每帧的特征是去重的列表。 test_input = [ [[(1,1), (2,2)], [(1,1)], [(1,1)], [(1,1), (2,2)], [(2,2)], [(1,1)], [], [(1,1)]] ] print(longest_feature_movement(test_input)) # 输出: [3] # 特征(1,1)在帧2,3,4连续出现3次 ``` 这道题的本质是**状态机**。每个特征都有一个状态（当前连续长度），这个状态随着每一帧的输入而转移。我们用哈希表来维护所有特征的状态，并在状态转移过程中更新答案。这种思路在处理流式数据、寻找连续模式的问题中非常常见。 ## 5. 当组合爆炸遇见动态规划：毕业旅行问题 “毕业旅行问题”是经典的**旅行商问题（TSP）** 的简化版（起点固定且需要返回）。城市数n最大为20，这暗示我们，虽然可以用暴力枚举所有排列（`(n-1)!`），但当n=20时，`19!`是一个天文数字，不可行。然而，题目给出的n≤20，实际上是一个强烈的提示：可以用**状态压缩动态规划**来解决。 旅行商问题的DP状态定义通常为：`dp[S][i]` 表示已经访问过的城市集合为`S`（一个二进制掩码），并且最后停留在城市`i`，此时的最小花费。其中`S`包含了起点（假设为0号城市）和城市`i`。 我们的目标是求 `min(dp[ALL][i] + dist[i][0])`，其中`ALL`是所有城市都访问过的状态，最后再加上从城市`i`回到起点0的费用。 状态转移方程是： `dp[S][i] = min(dp[S\{i}][j] + dist[j][i])`，对于所有`j`属于`S`且`j != i`。 意思是，要到达状态`(S, i)`，我们一定是先从某个状态`(S\{i}, j)`过来，即先访问了除`i`外的城市集合`S\{i}`，最后在`j`城市，然后再从`j`走到`i`。 初始化：`dp[1<<0][0] = 0`，表示只访问了起点0，且就在起点，花费为0。 这里的关键是**状态压缩**。我们用整数`mask`的二进制位来表示城市集合。第`i`位为1表示城市`i`在集合中。这样，`S`就可以用一个整数来表示，方便作为DP数组的索引。 ```python def min_travel_cost(dist): """ 使用状态压缩DP解决毕业旅行问题 :param dist: 二维列表，dist[i][j]表示城市i到j的车费 :return: 最小车费花销 """ n = len(dist) ALL = (1 << n) - 1 # 所有城市都访问过的状态，二进制位全为1 INF = float('inf') # dp[mask][i]: 访问过的城市集合为mask，最后在城市i的最小花费 dp = [[INF] * n for _ in range(1 << n)] dp[1][0] = 0 # 从起点0开始，mask只有第0位为1 # 遍历所有状态mask for mask in range(1, 1 << n): # 遍历所有城市i作为当前终点 for i in range(n): # 如果状态mask不包含城市i，跳过 if not (mask & (1 << i)): continue # 如果dp[mask][i]还是无穷大，说明这个状态不可达，跳过 if dp[mask][i] == INF: continue # 尝试从i走到下一个未访问的城市j for j in range(n): # 如果j已经在mask中，跳过 if mask & (1 << j): continue next_mask = mask | (1 << j) dp[next_mask][j] = min(dp[next_mask][j], dp[mask][i] + dist[i][j]) # 最终答案：所有城市都访问过（ALL），且最后在某个城市i，再返回起点0 ans = INF for i in range(1, n): # i不能是0，因为最后一步是从i回0 if dp[ALL][i] != INF: ans = min(ans, dp[ALL][i] + dist[i][0]) return ans # 测试用例 dist = [ [0, 2, 6, 5], [2, 0, 4, 4], [6, 4, 0, 2], [5, 4, 2, 0] ] print(min_travel_cost(dist)) # 输出: 13 ``` 这个算法的时间复杂度是`O(2^n * n^2)`，对于n=20，`2^20 ≈ 1e6`，再乘以`400`，大约是`4e8`，在Python中可能处于超时的边缘，但通常笔试环境会放宽限制，或者n实际更小。它展示了如何用DP来应对组合爆炸问题。理解状态压缩DP，是攻克大厂hard级算法题的重要武器。 ## 6. 贪心算法的直觉：找零与机器人跳跃 最后两题“找零”和“机器人跳跃问题”相对简单，但体现了不同的算法思想。 “找零”是典型的**贪心算法**。硬币面值是1、4、16、64，都是4的幂次。这种特殊的币值体系保证了贪心策略的最优性：为了使得硬币数最少，我们每次都尽可能使用面值最大的硬币。这几乎是一个直觉，代码也非常简洁。 ```python def min_coins(N): """ 计算找零所需的最少硬币数 :param N: 商品价值 :return: 最少硬币数 """ coins = [64, 16, 4, 1] change = 1024 - N count = 0 for coin in coins: count += change // coin change %= coin return count print(min_coins(200)) # 输出: 17 ``` 而“机器人跳跃问题”则需要一点逆向思维和数学推导。题目描述了机器人的能量变化规则：在第k个建筑，能量为E，跳到高度为H(k+1)的建筑后，新能量变为`2E - H(k+1)`。游戏目标是全程能量非负。 正向思考很难，我们不知道初始能量该设多少。但如果我们从终点**倒着推**，就简单了。假设我们要求到达终点（最后一个建筑）后，能量值至少为0（题目要求过程中非负，终点可以为0）。设到达最后一个建筑时的能量为`E_n`（我们不知道，但可以设为目标值，比如0）。 那么，在倒数第二个建筑（高度`H_{n-1}`）时，能量`E_{n-1}`需要满足：`2 * E_{n-1} - H_n >= E_n`。因为从`E_{n-1}`跳到`H_n`后，能量会变成`2E_{n-1} - H_n`，这个值必须至少等于我们要求的`E_n`。由此可以解出`E_{n-1} >= ceil((E_n + H_n) / 2)`，其中`ceil`是向上取整，因为能量必须是整数，且要保证“至少”。 我们从后往前，依次推导出每个位置所需的最小能量。推到起点时，得到的`E_0`就是所需的最小初始能量。 ```python import math def min_initial_energy(heights): """ 计算机器人完成游戏所需的最少初始能量 :param heights: 建筑物高度列表 :return: 最小初始能量 """ E = 0 # 假设到达最后一个建筑后，能量至少为0 # 从后往前逆推 for H in reversed(heights): E = math.ceil((E + H) / 2) return E print(min_initial_energy([3, 4, 3, 2, 4])) # 输出: 4 print(min_initial_energy([4, 4, 4])) # 输出: 4 print(min_initial_energy([1, 6, 4])) # 输出: 3 ``` 这道题的精妙之处在于**逆向思维**和**数学化简**。它考察的是你能否从复杂的描述中抽象出核心的数学关系，并找到高效的求解方向。在实际编程中，遇到类似“满足某种条件的最小值”问题，不妨想想能否从结果反推。 刷题就像打怪升级，每一道真题都是一个知识点的具象化。字节跳动的这些题目覆盖了字符串处理、双指针、组合数学、递归回溯、哈希映射、状态压缩DP、贪心、逆向推导等多个核心考点。我的建议是，不要死记硬背代码，而是吃透每一道题背后的思想，并尝试自己从头实现。遇到卡壳的地方，正是你知识体系的薄弱点，补上它，你就又强了一分。春招在即，祝大家都能写出优雅的代码，收获心仪的offer。