大厂真题 / 字节跳动
字节跳动 4.19 笔试真题
本场考试概述
考试时间：2026年4月19日 考试岗位：通用技术岗 难度评级：中等
考点分析：
- 第一题：二分答案 + 贪心（难度中等）
- 第二题：贪心标记 + 相邻性验证（难度中等）
- 第三题：贪心 + 因子分解（难度中等）
- 第四题：矩阵模拟（难度简单）
建议策略：
- 第四题纯模拟，代码量小且不易出错，建议优先完成
- 第一题二分答案是经典套路，check 函数中贪心模拟即可，注意特判全开的情况
- 第二题贪心扫描 + 邻接块验证，分两步走思路清晰
- 第三题需要理解”尾随零 = min(因子2个数, 因子5个数)”，操作只转移因子2，贪心从左往右移除即可
第一题：走廊通行与按钮策略
题目描述
有一条走廊上依次排列着 n 扇门，每扇门的状态为开启（0）或关闭（1）。你有一个按钮，最多可以按 K 次。每次按下按钮时，从当前位置开始，接下来的 x 扇门会全部打开（x 是按钮的”效力”，对所有按压统一生效）。你需要从走廊起点走到终点，经过的每扇门都必须处于开启状态。
求：使得你能顺利通过走廊的最小效力值 x。
多组测试数据，第一行输入 T。每组输入两行：第一行 n 和 K，第二行 n 个整数表示门的状态。所有测试数据的 n 之和不超过 200000。
样例
输入
3
4 1
0 1 1 0
8 2
1 1 0 1 1 1 0 1
5 3
0 0 0 0 0
输出
2
4
0
思路分析
第一步：特判——没有关闭的门
如果数组中不存在值为 1 的元素，意味着所有门都已打开，不需要按按钮，答案为 0。
第二步：发现单调性——为什么能二分
关键观察：当效力值 x 增大时，每次按钮能打开更多的门，所需的按压次数只会减少（或不变），不会增加。具体来说：
- x 越大，一次按压就能覆盖更多连续的关闭门
- 需要的总按压次数随 x 的增大而单调不增
这种单调性意味着：存在一个最小的 x_0，使得 K 次按压恰好足够。对于所有 x >= x_0 都满足条件，x < x_0 都不满足。这正是二分答案的经典形态。
第三步：设计 check 函数——贪心模拟
给定效力值 x，如何计算最少需要多少次按压？采用贪心策略：
从左到右遍历数组。遇到开启的门（a[i] == 0）直接通过，索引加 1。遇到关闭的门（a[i] == 1）必须按下按钮，按压次数加 1，然后跳过接下来的 x 扇门（因为它们都被打开了），索引加 x。
这个贪心是最优的：在第一个关闭门的位置按按钮，能最大化覆盖范围。提前按没有意义（前面的门已经开着），延后按则走不过去。
第四步：二分框架
- 搜索范围：lo = 1, hi = n
- 对每个 mid，调用 check 函数计算所需按压次数
- 若按压次数 <= K，说明 mid 足够大，尝试缩小：hi = mid
- 否则 mid 太小，需增大：lo = mid + 1
- 最终 lo 即为答案
以样例 2 为例：a = [1,1,0,1,1,1,0,1], K = 2
- x = 3: 位置0关闭，按一次跳到位置3；位置3关闭，按一次跳到位置6；位置6开放走到位置7；位置7关闭，需第三次按压。共需 3 次 > K=2，不可行。
- x = 4: 位置0关闭，按一次跳到位置4；位置4关闭，按一次跳到位置8，已越过终点。共需 2 次 = K=2，可行。
所以答案为 4。
题解代码
import sys
input = sys.stdin.readline
def count_buttons(a, x):
n = len(a)
cnt = 0
i = 0
while i < n:
if a[i] == 1:
cnt += 1
i += x
else:
i += 1
return cnt
def solve():
n, K = map(int, input().split())
a = list(map(int, input().split()))
if 1 not in a:
print(0)
return
lo, hi = 1, n
while lo < hi:
mid = (lo + hi) // 2
if count_buttons(a, mid) <= K:
hi = mid
else:
lo = mid + 1
print(lo)
T = int(input())
for _ in range(T):
solve()
复杂度分析
时间复杂度：O(n log n)，二分 O(log n) 轮，每轮 check 函数遍历数组 O(n)。 空间复杂度：O(n)，存储数组。
第二题：矩阵印章染色
题目描述
给定一个 n x m 的网格，每个格子为 ‘*’ 或 ‘.’。你有一枚 2x2 的印章，每次使用会将一个 2x2 区域全部染为 ‘*‘。要求判断：给定的网格图案能否由若干枚印章印出，且任意两枚印章之间不相邻（不共享边，也不共享角，即 8 方向都不接触）。
多组测试数据，第一行输入 T。
样例
输入
3
4 4
**..
**..
..**
..**
4 5
**...
**...
...**
...**
2 2
*.
..
输出
No
Yes
No
思路分析
第一步：贪心扫描确定印章位置
从左上角逐行扫描。每遇到第一个未被标记的 ‘*’ 格子，它只能作为某个 2x2 印章的左上角（因为我们从上到下、从左到右扫描，该 ‘*’ 不可能是其他位置印章覆盖的结果）。
此时检查以该位置为左上角的 2x2 区域是否全部为 ‘*’ 且全部未被标记。如果不满足，直接判定为 No（无法合法放置印章）。若满足，将这 4 格标记为”已覆盖”，并记录该印章的左上角坐标。
扫描结束后，如果还有未被标记的 ‘*’ 存在，说明有孤立的星号无法被 2x2 印章覆盖，判定 No。
第二步：为什么贪心扫描顺序是正确的
当我们从上到下、从左到右扫描时，遇到一个未标记的 ‘*‘，它不可能被”更靠右下”的印章覆盖（因为 2x2 印章覆盖的是左上角及其右、下、右下三个邻居）。所以它必须作为某个印章的左上角。这保证了贪心选择的唯一性。
第三步：验证印章间的非相邻性
两个 2x2 印章”不相邻”意味着它们覆盖的区域在 8 方向上没有接触。设两个印章左上角坐标分别为 (r1, c1) 和 (r2, c2)，则两块 2x2 区域占据的行范围分别是 [r1, r1+1] 和 [r2, r2+1]，列范围分别是 [c1, c1+1] 和 [c2, c2+1]。
两块区域不相邻（包括对角）的充要条件是：行距离 >= 3 或 列距离 >= 3。
| 这里”行距离”定义为两个左上角行坐标之差的绝对值 | r1 - r2 | ，列距离类似。因为每块印章占 2 行 2 列，两块印章如果行距 < 3 且列距 < 3，则存在某对格子 8 连通相邻。 |
第四步：综合判定
枚举所有印章对，检查是否满足行距 >= 3 或列距 >= 3。如果所有对都满足，输出 Yes，否则 No。
| 以样例 1 为例：4x4 网格，贪心扫描得到两个印章在 (0,0) 和 (2,2)。行距 = | 0-2 | = 2 < 3，列距 = | 0-2 | = 2 < 3，两个条件都不满足，印章对角相邻，输出 No。 |
以样例 2 为例：4x5 网格，两个印章在 (0,0) 和 (2,3)。行距 = 2 < 3，但列距 = 3 >= 3，满足条件，输出 Yes。
题解代码
import sys
input = sys.stdin.readline
def solve():
n, m = map(int, input().split())
grid = [input().strip() for _ in range(n)]
used = [[False] * m for _ in range(n)]
blocks = []
for i in range(n):
for j in range(m):
if grid[i][j] == '*' and not used[i][j]:
if i + 1 >= n or j + 1 >= m:
return "No"
if grid[i][j+1] != '*' or grid[i+1][j] != '*' or grid[i+1][j+1] != '*':
return "No"
if used[i][j+1] or used[i+1][j] or used[i+1][j+1]:
return "No"
used[i][j] = used[i][j+1] = used[i+1][j] = used[i+1][j+1] = True
blocks.append((i, j))
for a in range(len(blocks)):
for b in range(a + 1, len(blocks)):
dr = abs(blocks[a][0] - blocks[b][0])
dc = abs(blocks[a][1] - blocks[b][1])
if dr < 3 and dc < 3:
return "No"
return "Yes"
T = int(input())
for _ in range(T):
print(solve())
复杂度分析
时间复杂度：O(nm + B^2)，其中 B 为印章数量。扫描网格 O(nm)，验证印章对 O(B^2)。最坏情况 B = nm/4，但由于非相邻约束，实际 B 远小于此。 空间复杂度：O(nm)，存储网格和标记数组。
第三题：数组字典序优化与尾随零
题目描述
给定一个长度为 n 的正整数数组 a，以及操作次数上限 k。每次操作可以选择两个不同下标 i 和 j，要求 a[i] 是偶数，然后将 a[i] 除以 2，同时将 a[j] 乘以 2。
目标：通过至多 k 次操作，使数组的字典序尽可能小。输出操作后数组中每个元素的尾随零（即十进制表示末尾连续 0 的个数）。
样例
输入
5 1
1 2 3 4 5
输出
0 0 0 0 1
输入
3 20
1024 5 125
输出
0 0 3
思路分析
第一步：理解尾随零的本质
一个正整数 x 的尾随零个数 = x 能被 10 整除的次数 = min(x 中因子 2 的个数, x 中因子 5 的个数)。例如：
- 20 = 2^2 x 5，尾随零 = min(2, 1) = 1
- 1000 = 2^3 x 5^3，尾随零 = min(3, 3) = 3
- 125 = 5^3，尾随零 = min(0, 3) = 0
第二步：操作只影响因子 2 的分布
操作”a[i] /= 2, a[j] *= 2”本质上是将一个因子 2 从位置 i 转移到位置 j。操作不改变任何元素中因子 5 的个数，也不改变因子 2 的总量，只改变因子 2 在数组中的分布。
因此，操作后每个元素的尾随零 = min(操作后的因子2个数, 原始因子5个数)。
第三步：字典序最小化的贪心策略
字典序比较从第一个元素开始。要让字典序最小，优先让前面的元素尽可能小。将因子 2 从前面的元素移走会减小该元素的值（除以 2），从而减小字典序。
贪心策略：从左到右，对每个元素（除最后一个），尽可能多地移走其因子 2。每移走一个因子 2 消耗一次操作。具体来说，对位置 i，最多可移走 min(c2[i], k) 个因子 2。
被移走的因子 2 形成一个”池子”。最终把池子里所有因子 2 都给最后一个元素（放在最后对字典序影响最小）。
第四步：计算最终尾随零
操作完成后：
- 前 n-1 个元素：c2[i] 被减去移走的量，尾随零 = min(新c2[i], c5[i])
- 最后一个元素：c2[n-1] 加上池中所有因子 2，尾随零 = min(新c2[n-1], c5[n-1])
以样例 2 为例：a = [1024, 5, 125], k = 20
- c2 = [10, 0, 0], c5 = [0, 1, 3]
- 位置 0：移走 min(10, 20) = 10 个因子 2，k 剩余 10，c2[0] = 0
- 位置 1：移走 min(0, 10) = 0 个因子 2，c2[1] = 0
- 位置 2（最后）：接收 pool = 10 个因子 2，c2[2] = 0 + 10 = 10
- 尾随零：min(0,0)=0, min(0,1)=0, min(10,3)=3
- 输出：0 0 3
题解代码
import sys
input = sys.stdin.readline
def count_factor(x, p):
cnt = 0
while x % p == 0:
cnt += 1
x //= p
return cnt
n, k = map(int, input().split())
a = list(map(int, input().split()))
c2 = [count_factor(x, 2) for x in a]
c5 = [count_factor(x, 5) for x in a]
pool = 0
for i in range(n - 1):
move = min(c2[i], k)
c2[i] -= move
pool += move
k -= move
c2[n - 1] += pool
print(' '.join(str(min(c2[i], c5[i])) for i in range(n)))
复杂度分析
时间复杂度：O(n log V)，其中 V 为数组元素最大值。对每个元素计算因子 2 和因子 5 的个数需要 O(log V)。 空间复杂度：O(n)，存储因子计数数组。
第四题：自定义池化操作
题目描述
给定一个 n x n 的整数矩阵（n 为 2 的幂）。定义一次”池化”操作：将矩阵划分为若干个不重叠的 2x2 小块，对每个小块取其中第 2 大的值（即 4 个元素排序后的第 3 个，从小到大第 3 个即从大到小第 2 个），组成新的 n/2 x n/2 矩阵。
重复执行池化操作，直到矩阵缩小为 1x1，输出最终的唯一元素。
样例
输入
4
-6 -8 7 -4
-5 -5 14 11
11 11 -1 -1
4 9 -2 -4
输出
11
思路分析
第一步：理解池化规则
4 个元素排序后取第 3 个（0-indexed 为 [2]），即第 2 大的值。例如 [-6, -8, -5, -5] 排序得 [-8, -6, -5, -5]，第 2 大值为 sorted[2] = -5。
第二步：模拟过程
以样例为例，初始 4x4 矩阵：
-6 -8 7 -4
-5 -5 14 11
11 11 -1 -1
4 9 -2 -4
第一次池化（4x4 -> 2x2）：
- 左上 2x2: [-6, -8, -5, -5] -> sorted = [-8, -6, -5, -5] -> 取 [2] = -5
- 右上 2x2: [7, -4, 14, 11] -> sorted = [-4, 7, 11, 14] -> 取 [2] = 11
- 左下 2x2: [11, 11, 4, 9] -> sorted = [4, 9, 11, 11] -> 取 [2] = 11
- 右下 2x2: [-1, -1, -2, -4] -> sorted = [-4, -2, -1, -1] -> 取 [2] = -1
得到 2x2 矩阵：
-5 11
11 -1
第二次池化（2x2 -> 1x1）：
- [-5, 11, 11, -1] -> sorted = [-5, -1, 11, 11] -> 取 [2] = 11
最终输出 11。
第三步：实现
直接按定义模拟即可。每轮遍历当前矩阵的所有 2x2 块，计算第 2 大值写入新矩阵。矩阵大小每轮减半，循环直到 n = 1。
由于 n 为 2 的幂，log2(n) 轮后一定缩为 1x1。总工作量为 n^2 + (n/2)^2 + … + 1 = O(n^2)（等比数列求和）。
题解代码
import sys
input = sys.stdin.readline
n = int(input())
mat = []
for _ in range(n):
mat.append(list(map(int, input().split())))
while n > 1:
half = n // 2
new_mat = [[0] * half for _ in range(half)]
for i in range(half):
for j in range(half):
new_mat[i][j] = sorted([
mat[2*i][2*j], mat[2*i][2*j+1],
mat[2*i+1][2*j], mat[2*i+1][2*j+1]
])[2]
mat = new_mat
n = half
print(mat[0][0])
复杂度分析
时间复杂度：O(n^2)，等比数列 n^2 + n^2/4 + n^2/16 + … 收敛至 O(n^2)。每个 2x2 块排序为常数时间 O(4 log 4) = O(1)。 空间复杂度：O(n^2)，存储矩阵。
小结
- 第一题是经典的二分答案模板题，核心在于发现”效力 x 越大所需按压次数越少”的单调性，check 函数采用贪心模拟：遇到关闭门就按按钮并跳过 x 格
- 第二题分两步走：先用贪心扫描唯一确定每个印章的位置（利用从左上到右下的扫描顺序保证正确性），再验证任意两个印章不在 8 连通范围内
- 第三题的关键洞察是”操作只转移因子 2，因子 5 永远不变”，尾随零由两者的最小值决定，因此贪心地将因子 2 从前面元素移走、集中给最后一个元素即可最小化字典序
- 第四题是纯模拟，直接按定义逐轮缩小矩阵即可，注意”第 2 大”对应排序后下标 [2]