ARTICLE · 1370499
虾皮11月15日机考笔试题与解析
写在前面
本次给大家带来2026年11月15日虾皮笔试题的3道题,本场机考题目可在咱们平台上在线刷题。
第1题-兵种混编子数组统计
题目内容
你正在为一场战斗挑队员,按评分从高到低排了一批人。排完发现,这些人全是骑兵,兵种太同质化;必须搭配不同兵种,才能把队伍调整到最好的作战状态。
候选人列表为 ,每个数字对应不同的兵种。求有多少个连续子数组恰好包含 种不同数字。
输入描述
输入只有一行:开头是整数 ,后面紧跟整数数组 ,两段之间用一个英文逗号隔开。数组里的每个数表示一种兵种编号。
数组长度为 ,,。
输出描述
输出一个整数,表示满足前面条件的连续子数组个数。
样例1
输入
2,[4,4,4,4,1,2]输出
5说明
满足条件的连续子数组共 个:
[4,4,4,4,1][4,4,4,1][4,4,1][4,1][1,2]
题解
解题思路
题目要统计的是「不同元素个数恰好为 」的连续子数组个数。直接枚举左右端点、边扩展边维护不同元素个数,复杂度是 ,在 达到 时无法接受。
关键观察在于:「恰好 种」本身不单调,但「至多 种」是单调的。固定右端点 后,随着左端点向右移动,窗口内不同元素个数只减不增,合法的左端点因此是一段从某个下界开始的后缀。用滑动窗口就能在 内统计出「不同元素个数不超过 」的子数组数,记作 。
再做一次容斥:恰好 种的子数组数等于 。因为「至多 种」的集合去掉「至多 种」的集合,剩下的正是「不同元素个数恰为 」的子数组。
复杂度分析
时间复杂度:。每次 中右指针只从左到右扫一遍,左指针最多右移 次,两者都单调不回退;哈希表的插入、查询与删除均摊 ,两次 只差常数倍,故总时间为 。 空间复杂度:(最坏 ),其中 是数组中不同元素的个数,也就是哈希表需要保存的键值对数;除此之外只用若干整型变量。
代码实现
python代码(C++和JAVA代码见平台)
classSolution:defsubarraysWithKDistinct(self, nums, k):# 统计「至多 limit 种不同值」的子数组个数:右端点右移,窗口非法时左端点收缩defat_most(limit):if limit <= 0:return0 freq = {} left = 0 distinct = 0 total = 0for right in range(len(nums)): value = nums[right] freq[value] = freq.get(value, 0) + 1if freq[value] == 1: distinct += 1while distinct > limit: old = nums[left] freq[old] -= 1if freq[old] == 0: distinct -= 1 left += 1# 以 right 结尾、左端点在 [left, right] 内的子数组都合法 total += right - left + 1return total# 恰好 k 种 = 至多 k 种 - 至多 (k-1) 种return at_most(k) - at_most(k - 1)第2题-迷宫不可达格数
题目内容
你正在开发一款迷宫游戏。为了方便,迷宫用 的矩阵表示,其中 表示可以到达的区域, 表示不可到达的区域。
例如这样一个迷宫:
[ [0, 1, 0], [0, 1, 0], [0, 1, 1]]在这个例子里, 和 都是墙,所以从起点 看,、 的位置走不到(只能上下左右走)。
为了方便判断迷宫设计的难易程度,要统计每个迷宫中走不到的格子有多少个。以上面的迷宫为例,不可达区域为 个原生墙格,加上 个被隔开的空格,总数为 。
输入描述
输入数据是一个 的二维整数数组 ,数组元素只会是 或 ,其中 。起点固定为 ,并且保证 。
输出描述
输出一个整数,表示从 出发走不到的格子数,包括墙格和被墙隔开的空格。
样例1
输入
[[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说明
墙格共 个:、、、、、、。 这 格是空格,但被边界和墙围住,从起点到不了:、、、。 两类合计 个。
题解
解题思路
题目要的是「从 出发走不到多少格」,本质上是网格图上的一次连通性遍历。
把方阵的每一格看成图上的一个点,上下左右相邻的两格之间连一条边;值为 的格子不能站上去,也不能穿过,相当于从图中删掉。于是从 出发做一次广度优先搜索,能搜到的点集就是从起点真正走得到的全部格子。
搜索结束后,用总格数减去可达格数,就是走不到的格子数。墙格从未被访问,被墙圈住的空地也进不了搜索队列,两类不可达格子都被这个减法自然算进去了,不需要另外区分。
复杂度分析
时间复杂度为 :每个格子最多入队一次、出队一次,出队时固定检查 个相邻方向,最后再线性扫一遍访问数组统计可达格数,全部工作都与格子总数成正比。
空间复杂度为 :访问数组 需要 个字节,BFS 队列最多同时容纳 个下标,两者都不随方阵内容变化。
代码实现
python代码(C++和JAVA代码见平台)
classSolution:defcountUnreachable(self, grid): n = len(grid)# 用一维编号 cur = r * n + c 做 BFS,省掉坐标对拆装的开销 seen = bytearray(n * n) seen[0] = 1 queue = [0] head = 0while head < len(queue): cur = queue[head] head += 1 r, c = divmod(cur, n)# 逐个方向检查:越界、已访问、是墙的邻居都直接跳过if r > 0: nxt = cur - nifnot seen[nxt] and grid[r - 1][c] == 0: seen[nxt] = 1 queue.append(nxt)if r + 1 < n: nxt = cur + nifnot seen[nxt] and grid[r + 1][c] == 0: seen[nxt] = 1 queue.append(nxt)if c > 0: nxt = cur - 1ifnot seen[nxt] and grid[r][c - 1] == 0: seen[nxt] = 1 queue.append(nxt)if c + 1 < n: nxt = cur + 1ifnot seen[nxt] and grid[r][c + 1] == 0: seen[nxt] = 1 queue.append(nxt)# seen 里只标记了从出发点可达的空地,总数减掉它们即可return n * n - sum(seen)第3题-词典切分判定
题目内容
给定字符串 和字符串字典 。如果 能拆成字典里的若干个单词,单词之间用空格分隔,返回 true;否则返回 false。
字典中的单词可以重复使用。
输入描述
输入只有一行:先给出一个字符串 ,再给出一个字符串数组 。样例按这个顺序排列。
数据范围:,,; 与字典里的单词都由小写字母组成,字典里的单词互不相同。
输出描述
如果 能拆成字典里的若干个单词,输出 true,否则输出 false。
样例1
输入
"sunflowermoonlight",["sun","flower","moon","light","night"]输出
true说明
sun、flower、moon、light 都在字典中,依次拼接就是整个字符串,答案为 true。
题解
解题思路
把目标串记为 、单词表记为 ,长度记为 。题目要求判断 能否被完整切成表中的单词,同一个单词可以重复使用,这是典型的动态规划。
定义状态 : 的前 个字符能否被完整切分。空串天然合法,所以 。考虑最后一段单词 :如果前 个字符已经可以切分,且剩下的 正好是 ,那么前 个字符也可切分。把所有单词都考虑一遍,就能得到 。
最终 就是整个字符串能否被切分的答案。
复杂度分析
时间复杂度为 ,其中 为字符串长度、 为单词表大小、 为单词的最大长度;每个右端点都要与至多 个单词比较,单次比较至多 个字符。空间复杂度为 ,只需要长度为 的 数组。
代码实现
python代码(C++和JAVA代码见平台)
from typing import ListclassSolution:defwordBreak(self, s: str, wordDict: List[str]) -> bool: n = len(s)# dp[i] 表示 s 的前 i 个字符能否被完整切分 dp = [False] * (n + 1) dp[0] = True# 空串视为可切分for i in range(1, n + 1):# 枚举最后一段单词,判断它能否接在某个可切分前缀之后for w in wordDict: l = len(w)if l <= i and dp[i - l] and s[i - l:i] == w: dp[i] = Truebreakreturn dp[n]手机端刷题:塔子哥刷题宝
















































































