机试算法解析
字数
2299 字
阅读时间
10 分钟
算法一
python
from typing import List
"""
设计思路：
本题模拟解析 TLV（Tag-Length-Value）格式的字节流，数据按组排列：
每组第一个字节为 Tag（类型），第二个字节为 Length（后续 Value 的字节数），
后面紧跟 Length 个字节的 Value。难点在于每组之后需要按 4 字节对齐，
即每组的总长度（Tag + Length + Value）需要向上补齐到 4 的倍数。
我们需要从下标 0 开始顺序解析，若解析过程中出现越界、非法数据（值不在 0~99 之间）
或递归过深，则返回 0；否则返回所有遇到的 Tag 的种类数（去重后数量）。
采用递归顺序遍历，用集合存储已出现的 Tag。
"""
class Solution:
def calTagCount(self, tlv: List[int]) -> int:
# 缓存列表总长度，用于边界判断
border = len(tlv)
# 合法性校验：所有元素必须是 int 且取值范围 0~99，否则直接返回 0
if any(type(cell) is not int or cell < 0 or cell > 99 for cell in tlv):
return 0
# 定义递归函数，从 anchor 位置开始解析，bucket 存储已遇见的 Tag，quota 记录递归深度
def collect(anchor: int, bucket: set, quota: int) -> int:
# 终止条件1：如果 anchor 正好到达列表末尾，说明所有组解析完毕，返回不同 Tag 的数量
if anchor == border:
return len(bucket)
# 终止条件2（非法）：
# - 如果 anchor+1 超出边界，说明连“Tag + Length”两个字节都不足，结构不完整
# - 如果递归深度达到 1000，为防止栈溢出或死循环，强制返回 0
if anchor + 1 >= border or quota == 1000:
return 0
# 取出当前组的 Tag 和 Length
kind = tlv[anchor]
amount = tlv[anchor + 1]
# Length 必须 >= 1（题意隐含，若为0则无法推进解析）
if amount < 1:
return 0
# 计算当前组实际占用的字节数：Tag(1) + Length(1) + Value(amount)
unit = amount + 2
# 计算补齐到 4 的倍数后的总步长：
# 如果 unit 本身是 4 的倍数，则 jump = unit；否则补足差值
jump = unit if unit % 4 == 0 else unit + 4 - unit % 4
# 下一组的起始下标
target = anchor + jump
# 如果 target 超出了列表长度，说明无法完整解析下一组，返回 0
if target > border:
return 0
# 将当前 Tag 加入集合（自动去重）
bucket.add(kind)
# 递归解析下一组，递归深度加 1
return collect(target, bucket, quota + 1)
# 从下标 0 开始，传入空集合，初始深度为 0，返回最终结果
return collect(0, set(), 0)
"""
该算法解决的问题：
给定一个 TLV 格式的整数列表，需要按顺序解析每组数据，且每组后需 4 字节对齐。
统计所有成功解析的组中，Tag 字段一共有多少种不同的取值。
若数据格式非法（越界、数值范围不对、递归过深）则返回 0。
"""算法二
python
from typing import List
"""
设计思路：
本题是“最长连续子数组，子数组中最多包含两种不同元素”的经典问题（类似 LeetCode 904）。
要求给定一个整数数组，返回满足上述条件的最长子数组的长度。
采用一次遍历，使用几个变量维护当前窗口的状态：
- recent：当前窗口中最右边（最新出现）的元素值
- second：当前窗口中另一个较旧出现的元素值
- tail：recent 元素连续出现的次数（从当前位置往前数）
- span：以当前遍历元素结尾的、满足条件的子数组长度
当遇到第三种新元素时，新的子数组只能由“前一个元素的连续尾巴”加上当前元素组成，
因此 span = tail + 1，并更新 recent/second/tail。
时间复杂度 O(n)，空间复杂度 O(1)。
"""
class Solution:
def solution(self, energy_types: List[int]) -> int:
# recent 和 second 初始为 None（表示尚未确定）
recent = None
second = None
# tail：recent 连续出现的次数
tail = 0
# span：当前以当前元素结尾的满足条件的最长子数组长度
span = 0
# answer：全局最大长度
answer = 0
# 遍历数组中的每个元素
for item in energy_types:
# 情况1：当前元素属于窗口中的两种元素之一，则窗口可以继续向右扩展
if item == recent or item == second:
span += 1
else:
# 情况2：当前元素是第三种新元素，则新的有效子数组只能从“上一个元素的连续尾巴”开始
# 因为之前连续出现的 recent 元素加上当前新元素，构成了新的“两种元素”窗口
span = tail + 1
# 更新 recent、second 和 tail 的状态
if item == recent:
# 如果当前元素等于 recent，则 recent 的连续计数增加
tail += 1
else:
# 否则（item 不等于 recent），不管 item 是 second 还是新元素，
# 最新的 recent 必须是 item，原来的 recent 变为 second
second = recent
recent = item
# 新 recent 的连续出现次数重置为 1
tail = 1
# 更新全局最大长度
answer = max(answer, span)
return answer
"""
该算法解决的问题：
给定一个整数数组，求最长的连续子数组，使得该子数组中最多只包含两种不同的整数。
返回该最大长度。
例如 [1,2,1,2,3] 返回 4（子数组 [1,2,1,2]）。
"""算法三
python
from typing import List
"""
设计思路：
本题是集合覆盖问题的变体（Set Cover），已知 n 个页面和 m 个员工，
每个页面可由若干员工处理，每个员工有聘用成本。要求选择若干员工，
使得所有页面至少被一个选中员工覆盖，并使得总成本最小。
由于 n 较小（通常 <= 20），可采用状态压缩动态规划（DP）。
将 n 个页面用二进制位掩码表示，dp[mask] 表示达到覆盖状态 mask 的最小开销。
常规做法是 dp[mask] 存储真实成本，但本题要求输出结果对 (sum(cost)+1) 取模，
且需要最小化真实成本，但若直接取模会丢失大小比较信息。
因此采用“加权双关键字”技巧：每个员工的开销设为 quota + cost[i]，
其中 quota = sum(cost) + 1，这个数大于所有真实成本之和。
这样在 DP 比较时，首先比较选人数量（因为每个人都多加一个 quota），
在选人数量相同的情况下再比较真实成本，最终得到“人数最少且成本最小”的解。
最后对 quota 取模即可得到最小真实成本。
"""
class Solution:
def GetMinCost(self, n: int, m: int,
files: List[List[int]], cost: List[int]) -> int:
# staff_bits[i] 表示员工 i 能覆盖的页面的位掩码
staff_bits = [0] * m
# 遍历每个页面及其可处理的员工列表，设置对应的位
for page, choices in enumerate(files):
for employee in choices:
# 将第 page 位设为 1
staff_bits[employee] |= 1 << page
# quota 为大于所有成本总和的数，用作选人权重
quota = sum(cost) + 1
# bound 为所有可能的覆盖状态数（2^n）
bound = 1 << n
# 设置一个极大值表示不可达，确保它大于任何可能出现的合法加权值
unreachable = (m + 1) * quota + sum(cost) + 1
# dp 表，dp[mask] 表示达到掩码 mask 的最小加权开销
table = [unreachable] * bound
table[0] = 0 # 初始状态：未覆盖任何页面，开销为 0
# 遍历每个员工（类似于 0/1 背包的外层循环）
for member in range(m):
# next_table 复制上一轮结果，表示“不选当前员工”的情况
next_table = table[:]
# 如果选中当前员工，需要增加的加权成本 = quota（选人权重）+ 真实成本
addition = quota + cost[member]
# 当前员工能覆盖的页面掩码
mark = staff_bits[member]
# 遍历所有状态（使用上一轮的 table，保证每个员工只选一次）
for pattern in range(bound):
current = table[pattern]
# 如果当前状态不可达，跳过
if current == unreachable:
continue
# 合并状态，得到新覆盖掩码
merged = pattern | mark
# 候选加权开销
candidate = current + addition
# 如果候选值更小，则更新 next_table
if candidate < next_table[merged]:
next_table[merged] = candidate
# 更新 dp 表，进入下一个员工的决策
table = next_table
# 最终 table[bound - 1] 存储覆盖所有页面的最小加权开销，
# 由于加权开销 = (选人数量 * quota) + 真实总成本，
# 而 quota 大于所有真实成本之和，因此对 quota 取模即可得到最小真实总成本
return table[bound - 1] % quota
"""
该算法解决的问题：
有 n 个页面和 m 个员工，每个员工擅长处理某些页面，且聘用成本不同。
要求选择若干员工，使得所有页面都能被覆盖，求最小的总聘用成本。
返回结果需要模 (sum(cost) + 1)。
"""贡献者
freeway348