夜雨聆风学习资料网

ARTICLE · 1370499

虾皮11月15日机考笔试题与解析

虾皮11月15日机考笔试题与解析

写在前面

本次给大家带来2026年11月15日虾皮笔试题的3道题,本场机考题目可在咱们平台上在线刷题。

题号
题目
核心做法
1
兵种混编子数组统计
滑动窗口
2
迷宫不可达格数
BFS
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]
刷题练习:CodeFun2000.com

手机端刷题:塔子哥刷题宝

回首页,搜索你想要的文档

在首页搜索框输入关键词,快速定位资料

文库首页搜索指引 立即搜索

相关学习资料