关注我们，每天更新大厂最新笔试题解析
前言
- 第 1 题 — 简易的二进制包依赖关系检查和处理（中等，DFS）
先把依赖关系看成有向图并用 DFS 或拓扑排序判断是否存在循环依赖；若无环则统计每 个被依赖包所需的最高版本号，并按原依赖关系顺序统一输出该最大版本。 - 第 2 题 — 硬件布线（困难，BFS） 把每个位置按"从上走来"或"从左走来"分成两种状态，用 0-1 BFS
在只允许向下和向右的前提下搜索，直走代价为 0、转弯代价为
1，最终求到右下角的最少转弯次数。 - 第 3 题 — 星球大战（困难，动态规划）
按顺序遍历怪兽，用动态规划维护"击败 个怪兽时能剩下的最大能量"，每次对当前 怪兽选择打或跳过，最终取最多能达到的击败数量。
第 1 题 — 简易的二进制包依赖关系检查和处理
题目内容
一个项目中，除了自研的代码外，还会依赖很多二进制包（后续简称为"包"），这些包也会依赖其他的包，每个被依赖的包还有版本号的要求。本题借鉴了包管理的思想，需要完成一个简易的包依赖关系分析和处理的模型：对输入的一组依赖关系进行分析，判断是否存在循环依赖；如果存在循环依赖则输出不合理；否则进一步对依赖包的版本号进行规整，并输出规整后的依赖关系串。
依赖关系的数据结构由三个属性组成：
- 依赖包序号：任意正整数，表示该包所依赖的另一个包的序号。
例如依赖关系 表示包 依赖包 的 版本。
基于该依赖关系数据进行如下判断与处理：
- 判断包依赖关系中是否存在循环依赖：包之间的依赖关系不能形成循环。例如，包 依赖包 ，包 依赖包 ，包 又依赖包 ，这种情况属于循环依赖，不合理。注：版本号不纳入循环依赖与否的判断。
- 对包依赖关系的版本号进行规整处理：若依赖关系合理，对于多个包依赖同一个包的情况，取其中被依赖包版本号的最大值，然后输出新的依赖关系。
输入描述
每次输入两组依赖关系的信息，分别解析和输出两组结果。每组格式：
- 第一行为一个正整数 ，表示待输入的包依赖关系的个数。
- 接下来 行，每行一个依赖关系，格式为：
序号,依赖包序号,依赖包版本号。
注：两组依赖关系完全独立。
输出描述
依次输出两组结果。每组的输出要求：
- 否则对版本号进行规整处理后，按原顺序输出新的依赖关系。
样例
样例 1
输入：
3
1,2,23
2,3,34
4,2,25
3
1,2,23
2,3,34
3,1,12
输出：
1,2,25
2,3,34
4,2,25
false
说明：
- 第一组：包 依赖包 版本 ，包 依赖包 版本 ，包 依赖包 版本 。无循环依赖；包 和包 共同依赖包 ，版本号规整后取最大值 。
提示
思路与代码
这是一道考察有向图环检测（拓扑排序或深度优先搜索）以及哈希表应用的经典题目。
我们可以把包之间的依赖关系看作是一张有向图，其中：
节点代表二进制包的序号。
有向边代表依赖关系（例如包 1 依赖包 2，可以看作有一条从节点 1 指向节点 2 的边）。
解题思路：
输入解析：题目要求仅使用 sys.stdin.readline()。我们需要编写一个辅助函数来过滤掉空行，准确地读取每一行数据。
环检测：采用深度优先搜索（DFS）检测图中有无环。使用两个集合：visited 记录已访问的节点，rec_stack 记录当前递归栈中的节点。如果在遍历某个节点的邻居时，发现该邻居已经在当前的递归栈中，则说明存在循环依赖（包括自己依赖自己）。
版本规整：使用一个字典 max_version 来记录每个被依赖包的最大版本号。在读取依赖关系时不断更新该字典，如果没有循环依赖，则遍历原始输入的边信息，并将依赖版本号替换为该字典中记录的最大值。
import sys
defget_next_line():
whileTrue:
line = sys.stdin.readline()
ifnot line:
returnNone
line = line.strip()
if line:
return line
defsolve():
# 题目明确输入为两组依赖关系
for _ in range(2):
line = get_next_line()
ifnot line:
break
n = int(line)
edges = []
adj = {}
max_version = {}
nodes = set()
# 读取并解析 n 个依赖关系
for _ in range(n):
edge_str = get_next_line()
ifnot edge_str:
continue
u, v, w = map(int, edge_str.split(','))
edges.append((u, v, w))
# 记录图中所有的节点
nodes.add(u)
nodes.add(v)
# 构建邻接表
if u notin adj:
adj[u] = []
adj[u].append(v)
# 记录被依赖包的最大版本号
if v notin max_version:
max_version[v] = w
else:
max_version[v] = max(max_version[v], w)
visited = set()
rec_stack = set()
# 深度优先搜索判断是否有环
defhas_cycle(curr):
visited.add(curr)
rec_stack.add(curr)
if curr in adj:
for neighbor in adj[curr]:
if neighbor notin visited:
if has_cycle(neighbor):
returnTrue
elif neighbor in rec_stack: # 邻居已在当前递归栈中，存在环路
returnTrue
rec_stack.remove(curr)
returnFalse
cycle_found = False
for node in nodes:
if node notin visited:
if has_cycle(node):
cycle_found = True
break
# 按题目要求输出结果
if cycle_found:
print("false")
else:
for u, v, _ in edges:
# 规整并输出：替换为被依赖包的最大版本号
print(f"{u},{v},{max_version[v]}")
solve()
第 2 题 — 硬件布线
题目内容
硬件 PCB 板上两个芯片之间需要布一条 I2C 链路，两个芯片分别位于左上角和右下角，PCB 走线仅能向下和向右移动。但是当前 PCB 上已经有一些器件或者干扰源，器件和干扰源都要绕开。
给定一个二维数组：
避开干扰信号衰减越小，而且转弯次数越少越好。需要找到从芯片 A 到芯片 B 之间通路的最少转弯次数，实现布线方案预估。如果没有通路，直接返回 。
输入描述
- 第一行两个整数 ，分别表示行数和列数。超出边界值直接返回 。
- 后面 行 列整型矩阵，表示 PCB 板上已有器件分布情况。
约束：
输出描述
返回芯片 A 到芯片 B 之间通路的最少转弯次数。
样例
样例 1
输入：
4 4
0 2 0 4
0 1 3 0
0 1 0 0
1 0 0 0
输出：
-1
说明：从芯片 A 到芯片 B 无通路可到达，返回 。
样例 2
输入：
3 3
0 1 0
0 0 0
2 0 0
输出：
2
说明： 的二维数组中， 代表通路，非 不可通过。从 A 到 B 存在多条路径，例如 转弯 次， 转弯 次，最少转弯次数为 。
样例 3
输入：
-2 2
0 0
0 0
输出：
-1
说明：输入参数不满足要求，直接返回 。
思路与代码
这是一道典型的动态规划（Dynamic Programming, DP）问题。由于题目明确限制走线仅能向下和向右移动，这意味着从芯片 A 到芯片 B 的路径是一个有向无环图（DAG），非常适合使用 DP 来求解最少转弯次数。💡 解题思路1. 状态定义：每次移动的方向决定了下一步是否产生转弯。我们需要记录到达每一个格子时，是从上方（向下移动）还是从左方（向右移动）过来的。因此，定义一个三维 DP 数组 dp[i][j][k]：dp[i][j][0]：表示来到坐标 (i, j) 时，且最后一步是向下走的最少转弯次数。dp[i][j][1]：表示来到坐标 (i, j) 时，且最后一步是向右走的最少转弯次数。2. 状态转移方程：假设当前处理的格子 (i, j) 是可通过的（即 grid[i][j] == 0）：计算 dp[i][j][0]（从上方下来）：如果上一步也是从上方下来：转弯次数不增加，为 dp[i-1][j][0]。如果上一步是从左边过来：方向发生变化，转弯次数 ，为 dp[i-1][j][1] + 1。取两者最小值：dp[i][j][0] = min(dp[i-1][j][0], dp[i-1][j][1] + 1)计算 dp[i][j][1]（从左方过来）：如果上一步也是从左边过来：转弯次数不增加，为 dp[i][j-1][1]。如果上一步是从上方下来：方向发生变化，转弯次数 ，为 dp[i][j-1][0] + 1。取两者最小值：dp[i][j][1] = min(dp[i][j-1][1], dp[i][j-1][0] + 1)3. 边界处理与初始化：起点 dp[0][0][0] = 0，dp[0][0][1] = 0。矩阵的第一列只能由上方走下来，第一行只能由左侧走过来。一旦遇到障碍物，后续对应直线方向上的格子皆不可达（设为无穷大）。若输入的 或 不在 范围内，或者起点/终点被占用了，直接返回 。
import sys
defsolve():
m, n = map(int, sys.stdin.readline().split())
grid = []
for _ in range(m):
row = list(map(int, sys.stdin.readline().split()))
grid.append(row)
if m < 0or n < 0:
print("-1")
return
# 如果起点或终点是障碍物，必然无路可走
if grid[0][0] != 0or grid[m - 1][n - 1] != 0:
print("-1")
return
# 3. 动态规划初始化
INF = float('inf')
# dp[i][j] = [向下走的最少转弯数, 向右走的最少转弯数]
dp = [[[INF, INF] for _ in range(n)] for _ in range(m)]
dp[0][0] = [0, 0]
# 初始化第一列 (只能由上方下来)
for i in range(1, m):
if grid[i][0] == 0:
dp[i][0][0] = dp[i - 1][0][0]
else:
break
# 初始化第一行 (只能由左侧过来)
for j in range(1, n):
if grid[0][j] == 0:
dp[0][j][1] = dp[0][j - 1][1]
else:
break
# 4. 状态转移
for i in range(1, m):
for j in range(1, n):
if grid[i][j] == 0:
# 从上面往下走：取上一步依然向下，或者上一步向右 + 1 次转弯的最小值
dp[i][j][0] = min(dp[i - 1][j][0], dp[i - 1][j][1] + 1)
# 从左边往右走：取上一步依然向右，或者上一步向下 + 1 次转弯的最小值
dp[i][j][1] = min(dp[i][j - 1][1], dp[i][j - 1][0] + 1)
# 5. 输出结果
ans = min(dp[m - 1][n - 1][0], dp[m - 1][n - 1][1])
print("-1"if ans == INF else ans)
solve()
第 3 题 — 星球大战
题目内容
在潘多拉星球上，有一群怪兽组成一道阵线，奥特曼必须按顺序与这些怪兽战斗。奥特曼有一个初始能量值 ，每个怪兽都有一个攻击力 和击败奖励 （击败后奥特曼可以恢复相应的能量值）。
当奥特曼面对第 个怪兽时，有以下选择：
- 如果当前能量值大于怪兽攻击力 ，可以选择战斗：先消耗 点能量，然后增加 点能量；
- 如果当前能量值小于或等于，不能与该怪兽战斗（剩余能量不能 ），此时只能跳过；
- 无论能否打过，都可以选择跳过该怪兽，此时不消耗也不增加能量。
目标：尽可能多地击败怪兽（即最大化击败数量），计算最多能击败多少个怪兽。
注意：奥特曼与怪兽战斗的顺序不能改变。
约束条件：
输入描述
输出描述
整数，最多击败的怪兽数量。
样例
样例 1
输入：
18
15 17 4 18
1 15 4 17
输出：
2
说明：初始能量 。跳过第 个怪兽；打第 个：；打第 个：；剩余能量 ，无法打第 个。最多击败 个。
样例 2
输入：
5
10 20 30
1 1 1
输出：
0
说明：每个怪兽都打不过，输出 。
样例 3
输入：
9
5 4 5
0 3 4
输出：
2
说明：初始能量 。跳过第 个；打第 个：；打第 个：。最多击败 个。
思路与代码
这是一道非常经典的动态规划（0-1 背包的变种）问题。由于初始能量 和怪兽的各项数值非常大（高达 ），我们不能把能量作为动态规划的数组下标（状态）。但是，怪兽的数量 非常小（最多 100 只），所以我们可以转换思路：把“击败的怪兽数量”作为状态，而将“剩余的最大能量”作为动态规划数组中存储的值。算法思路定义状态：维护一个数组 dp，其中 dp[j] 表示击败 个怪兽后，奥特曼所能保留的最大能量。如果无法击败 个怪兽，则 dp[j] = -1。初始化：初始时没有打怪兽，所以 dp[0] = E，其他的 dp[j] = -1。状态转移：按顺序遍历每一个怪兽，对于第 个怪兽（攻击力为 ，奖励为 ），我们从后向前遍历击败的怪兽数量 。如果我们要在当前这步达到“击败 个怪兽”的状态，说明在打这只怪兽之前，我们必须已经击败了 个怪兽，且剩余能量要严格大于当前怪兽的攻击力 。转移方程为：如果 dp[j-1] > d，则可以战斗，战斗后的能量为 dp[j-1] - d + r。我们取所有策略中的最大值：dp[j] = max(dp[j], dp[j-1] - d + r)。得出结果：遍历完成后，从最大的 开始向后查找，找到第一个 dp[j] != -1 的 ，即为最多可以击败的怪兽数量。
import sys
defsolve():
E = int(sys.stdin.readline().strip())
damage = list(map(int, sys.stdin.readline().strip().split()))
reward = list(map(int, sys.stdin.readline().strip().split()))
n = len(damage)
# dp[j] 表示击败 j 个怪兽后剩下的最大能量
# 初始化为 -1，表示该状态不可达
dp = [-1] * (n + 1)
dp[0] = E # 击败 0 个怪兽时，剩余能量为初始能量
for i in range(n):
d = damage[i]
r = reward[i]
# 必须从大到小逆向遍历 j，类似于 0-1 背包的一维空间优化
# 这样可以防止当前阶段刚更新的 dp[j] 被后续的计算重复使用
for j in range(i + 1, 0, -1):
# 只有在之前击败 j-1 个怪兽后的能量严格大于当前怪兽的攻击力时，才能战斗
if dp[j - 1] > d:
# 状态转移：保留当前状态的最大能量值
dp[j] = max(dp[j], dp[j - 1] - d + r)
# 找到最大的可达击败数量
max_defeated = 0
for j in range(n, -1, -1):
if dp[j] != -1:
max_defeated = j
break
print(max_defeated)
solve()
10个月宝宝每天需要喝多少奶粉？
