虾皮 11 月 15 日机考笔试:恰好 t 种数字的子数组与迷宫不可达格数
- 轮次
- 笔试
- 时间
- 2026-11
- 来源
- 牛客网
《面试题目》
第 1 题:兵种混编子数组统计
候选人列表为 a,每个数字对应不同的兵种,求有多少个连续子数组恰好包含 t 种不同数字。
输入只有一行:开头是整数 t,后面紧跟整数数组 a,两段之间用一个英文逗号隔开。数组长度为 m,1 ≤ t ≤ m ≤ 2×10^4,1 ≤ a_i ≤ m。输出一个整数,表示满足条件的连续子数组个数。
样例输入:
2,[4,4,4,4,1,2]
样例输出:5。满足条件的子数组是 [4,4,4,4,1]、[4,4,4,1]、[4,4,1]、[4,1]、[1,2]。
第 2 题:迷宫不可达格数
迷宫用 m × m 的矩阵表示,0 表示可以到达的区域,1 表示不可到达的区域。从起点 a[0][0] 出发,只能上下左右移动,统计走不到的格子数,包括墙格与被墙隔开的空格。1 ≤ m ≤ 10^3,保证 a[0][0] = 0。
样例输入:
[[0,0,1,0,0],[0,0,1,0,0],[0,0,1,1,1],[0,0,0,0,0],[1,1,0,0,0]]
样例输出:11。墙格 7 个,加上被隔开的空格 a[0][3]、a[0][4]、a[1][3]、a[1][4] 共 4 个。
《参考解析》
第 1 题的关键是「恰好 k 种」不单调,「至多 k 种」单调。固定右端点 r,随着左端点向右移动,窗口内不同元素的个数只减不增,所以合法的左端点是一段后缀。用滑动窗口可以在 O(n) 内算出「不同元素个数不超过 k」的子数组数,记作 atMost(k);再做容斥,恰好 k 种就是 atMost(k) - atMost(k-1)。左指针最多右移 n 次、右指针扫一遍,哈希表操作均摊 O(1),总时间 O(n),空间 O(k)。
import re
import sys
def at_most(nums, limit):
if limit <= 0:
return 0
freq = {}
left = 0
distinct = 0
total = 0
for right, value in enumerate(nums):
freq[value] = freq.get(value, 0) + 1
if freq[value] == 1:
distinct += 1
while distinct > limit:
old = nums[left]
freq[old] -= 1
if freq[old] == 0:
distinct -= 1
left += 1
total += right - left + 1
return total
data = list(map(int, re.findall(r"\d+", sys.stdin.read())))
t, nums = data[0], data[1:]
print(at_most(nums, t) - at_most(nums, t - 1))
实现细节:输入是 t,[...] 这种带方括号与逗号的格式,最省事的是用正则抽出全部整数,第一个是 t,其余是数组;t = 1 时 atMost(0) 返回 0,容斥仍然成立;计数用 64 位整数(Python 无需关心)。不要枚举左右端点,O(n²) 在 2×10^4 下大约 4×10^8 次操作,会超时。
第 2 题是一次连通性遍历。把每个格子看成图上的点,上下左右相邻的格子连边,值为 1 的格子不能站上去,相当于从图中删掉;从 (0,0) 做一次 BFS,能访问到的就是所有可达格。答案等于总格数 m*m 减去可达格数——墙格从未入队,被墙围住的空地也进不来,两类都自然被计入不可达。
from collections import deque
def unreachable(grid):
m = len(grid)
seen = [[False] * m for _ in range(m)]
seen[0][0] = True
q = deque([(0, 0)])
reached = 1
while q:
x, y = q.popleft()
for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < m and not seen[nx][ny] and grid[nx][ny] == 0:
seen[nx][ny] = True
reached += 1
q.append((nx, ny))
return m * m - reached
m 最大 1000,格子数 10^6,BFS 的 O(m²) 时间与空间都可以接受。两个容易踩的坑:① 用递归 DFS 在 10^6 个格子的链状路径上会爆栈,改成显式栈或 BFS;② 输入是二维数组字面量,按行读进来后要正确解析,别把方括号与逗号当成数据。