大厂真题 / 美团
美团研发岗 2026-09-15
本场考试概述
考试时间：2026-09-15
考试岗位：研发岗
难度评级：简单
考点分析：
- 第一题 合格空位数量：01 串、最近位置与相邻段计数（难度简单）。
建议策略：
- 不要对每个
0分别向左右扫描；最坏会退化到 $O(n^2)$。 - 同一对相邻
1之间，每个0到两端的距离之和都等于两端下标差。 - 第一个
1之前和最后一个1之后的空位缺少一侧已占位置，不能计入。
第 1 题：合格空位数量
题目描述
给定一个长度为 $n$ 的二进制串，其中 1 表示已占位置，0 表示空位。
对某个空位，如果它左右两侧都存在已占位置，分别取左右最近的一个。若空位到这两个已占位置的距离之和恰好为 $k$，则称该空位合格。求合格空位的数量。
输入描述
第一行是 $n,k$，满足 $1\le n\le2\times10^5$、$1\le k\le n$。
第二行是长度为 $n$ 的二进制串 $s$。
输出描述
输出合格空位数量。
样例 1
输入
7 3
1001001
输出
4
样例 2
输入
10 4
0100010010
输出
3
思路分析
第一步：观察相邻的两个 1。 设它们下标为 $L<R$，中间没有其他 1。任取中间空位 $i$，其左右最近已占位置必然就是 $L$ 和 $R$。
第二步：消去空位下标。 两段距离之和为：
\[(i-L)+(R-i)=R-L\]它只与两端 1 的间距有关，与 $i$ 无关。因此，当 $R-L=k$ 时，中间的 $R-L-1$ 个空位全部合格；否则全部不合格。
第三步：单趟扫描。 记录上一个 1 的位置。遇到新的 1 时检查两者间距，满足条件就把中间空位数加入答案。串两端没有被一对 1 包围的 0 不会进入任何一段，自然不会误计。
正确性说明
每个左右两侧都有已占位置的空位，唯一属于其左右最近两个 1 形成的相邻段。算法逐一处理所有相邻 1 的区间；由距离恒等式，该区间中的空位要么全部合格，要么全部不合格。各区间内部空位互不重叠，因此算法准确统计全部合格空位。
题解代码
import sys
def solve():
input = sys.stdin.readline
n, target_distance = map(int, input().split())
seats = input().strip()
answer = 0
previous = -1
for index, value in enumerate(seats):
if value != "1":
continue
if previous != -1 and index - previous == target_distance:
answer += index - previous - 1
previous = index
print(answer)
solve()
复杂度分析
时间复杂度：$O(n)$，只扫描一次字符串。
空间复杂度：$O(1)$，除输入字符串外只保存上一个已占位置和答案。
易错点
- 必须使用相邻的
1；跨过中间1选择更远端点不符合“最近”要求。 - 当 $k=1$ 时两个
1相邻，中间没有空位，贡献为 0。 - 全
0、只有一个1或空位仅位于串两端时，答案都是 0。
小结
看似需要为每个空位查询左右最近位置，实际在相邻 1 的区间内距离和恒定。按区间计数后，只需一次线性扫描和常数额外空间。