今天练习的是华为非AI岗最新机考笔试题3题。
各大厂真题都整理了近两年的机考题，题库里面有详细思路和答案~
肥猫学长也提供机考辅导助攻和面试辅导欢迎咨询。
微信号：jackwwang8
目前已经整理的题库有如下：如果有需要可以加我微信获取哦
华为非AI方向暑期实习5.13春招机考真题
第1题：统计类别合规的浏览片段
题面描述
某电商平台需要分析用户的商品浏览历史，以优化推荐系统。
给定用户在某段时间内的商品浏览记录序列，每个商品属于一个类别（如 手机、电脑、家电 等）。
平台希望统计出：用户在连续浏览过程中，不同商品类别数不超过 K 种的浏览片段数量。
浏览片段：浏览记录中一段连续的记录序列。例如，浏览记录 [手机, 电脑, 手机, 家电] 中，[手机, 电脑] 是一个浏览片段。
不同商品类别数：浏览片段中不重复的商品类别个数。例如，浏览片段 [手机, 电脑, 手机, 家电] 的不同商品类别数为 3（类别为 手机、电脑、家电）。
测试用例
样例 1 输入
3 31001 2002 3003样例 1 输出
6样例 1 说明
所有浏览片段的不同类别数都不超过 3，因此结果为所有子数组的数量，即为 6。
样例 2 输入
5 21 40 1 12 5000样例 2 输出
10样例 2 说明
不同商品类别数不超过 2 种的浏览片段结果为 10。
解题思路
本题要求统计连续浏览片段中，不同商品类别数不超过 K 的片段数量。
使用滑动窗口算法。
维护一个窗口 [left, right]，表示当前连续片段。用哈希表记录窗口内每种类别出现的次数，同时维护不同类别数量。
每次将 nums[right] 加入窗口：
如果窗口内不同类别数超过 K，就不断移动 left，缩小窗口，直到不同类别数不超过 K。
此时，以 right 结尾的合法片段数量为：right - left + 1。
因为这些片段分别是：[left, right], [left+1, right], ..., [right, right]。
把每个位置作为右端点的合法片段数累加，即为答案。
（更加详细解题思路和CPP、Java代码加我微信获取）
# 华为机考题号：1
def calculate_valid_browsing_history(category_list, max_categories):
# 使用字典记录当前窗口内各类别的出现频率
category_frequency = {}
left_pointer = 0
total_valid_segments = 0
for right_pointer in range(len(category_list)):
# 获取当前浏览的商品类别
current_category = category_list[right_pointer]
# 更新该类别在窗口内的出现次数
category_frequency[current_category] = category_frequency.get(current_category, 0) + 1
# 如果当前窗口内的不同类别总数超过了允许的最大值
while len(category_frequency) > max_categories:
# 尝试移除左端点的商品
left_category = category_list[left_pointer]
category_frequency[left_category] -= 1
# 如果该类别在窗口内不再出现，则从字典中删除
if category_frequency[left_category] == 0:
del category_frequency[left_category]
# 左指针向右移动，缩小窗口
left_pointer += 1
# 此时以 right_pointer 为结尾的所有子片段都是合法的
# 数量即为窗口的长度
total_valid_segments += right_pointer - left_pointer + 1
return total_valid_segments
def main():
import sys
# 读取输入数据
input_data = sys.stdin.read().split()
if not input_data:
return
n = int(input_data[0])
k = int(input_data[1])
# 将后续的类别编号存入列表
category_list = [int(x) for x in input_data[2:]]
# 计算并输出结果
result = calculate_valid_browsing_history(category_list, k)
print(result)
if __name__ == "__main__":
main()
第2题：部门服务二叉树合并
题面描述
某公司用二叉树来管理服务，随着部门业务的调整，需要对服务进行合并以节约管理成本。部门主管将服务合并的任务下发给你。
具体要求为：
一、当两棵二叉树部分重叠，且其余节点不冲突，则重叠部分可以合并得到新的树。
树采用层序遍历（按行）+ 空节点表示空缺的方式表示。
二、如果两棵树的节点有冲突（部分子节点无法合并），则不可合并。
三、如果树 1 可以往树 2 合并，树 2 也可往树 1 合并，则采用树 2 往树 1 合并。
提示：
不用考虑两棵树同时为空的场景。
合并前树的节点不重名，合并后可重名；合并方式为整棵合并的逻辑，并去除重合部分。
测试用例
样例 1 输入
a b c d null e f null null null null ffc e f null null it样例 1 输出
0样例 1 说明
a, b, c 三个节点完全重合，但子节点 ffc 和 it 冲突了。
样例 2 输入
a b c d null e f null null null null gc e f null null null q样例 2 输出
a b c d null e f null null null null g q样例 2 说明
a, b, c 三个节点完全重合，且子节点 g 和 q 也不冲突，可以合并。
解题思路
先用 deque 按层序序列建出两棵二叉树，注意只有非空节点才继续读取它的左右孩子。
合并时使用递归判断冲突：
当两个位置都有节点时，节点值必须相同，否则冲突，不能合并。
当某个位置为空时，可以直接接上另一棵树对应位置的子树。
优先尝试把树 2 合并到树 1 中，也就是在树 1 中找到与树 2 根节点值相同的节点，从这里开始整体合并。
如果失败，再尝试把树 1 合并到树 2 中。
如果两种方式都失败，输出 0。
层序输出时保留中间的 null，最后删除末尾多余的 null。
（更加详细解题思路和CPP、Java代码加我微信获取）
# 华为机考题号：2
import sys
from collections import deque
class ServiceTreeNode:
"""定义服务节点结构"""
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def construct_tree_from_sequence(sequence_str):
"""根据层序遍历序列构建二叉树"""
values = sequence_str.strip().split()
if not values or values[0] == "null":
return None
root_node = ServiceTreeNode(values[0])
traversal_queue = deque([root_node])
index = 1
# 按照层序规则，依次填充节点的左右子树
while traversal_queue and index < len(values):
current_node = traversal_queue.popleft()
# 处理左子节点
if index < len(values):
if values[index] != "null":
current_node.left = ServiceTreeNode(values[index])
traversal_queue.append(current_node.left)
index += 1
# 处理右子节点
if index < len(values):
if values[index] != "null":
current_node.right = ServiceTreeNode(values[index])
traversal_queue.append(current_node.right)
index += 1
return root_node
def locate_service_node(current_root, target_value):
"""在树中查找值为 target_value 的节点"""
if current_root is None:
return None
if current_root.value == target_value:
return current_root
# 递归查找左子树
found_node = locate_service_node(current_root.left, target_value)
if found_node:
return found_node
# 递归查找右子树
return locate_service_node(current_root.right, target_value)
def check_merge_compatibility(node_a, node_b):
"""检查两棵子树是否可以合并（即对应位置节点值相同或有一方为空）"""
if node_a is None or node_b is None:
return True
# 两个节点都存在时，名称必须一致
if node_a.value != node_b.value:
return False
# 递归检查左右子树的兼容性
return check_merge_compatibility(node_a.left, node_b.left) and \
check_merge_compatibility(node_a.right, node_b.right)
def execute_tree_merge(node_a, node_b):
"""将树 node_b 合并到树 node_a 中"""
if node_a is None:
return node_b
if node_b is None:
return node_a
# 递归合并子树
node_a.left = execute_tree_merge(node_a.left, node_b.left)
node_a.right = execute_tree_merge(node_a.right, node_b.right)
return node_a
def serialize_tree_to_level_order(tree_root):
"""将二叉树序列化为层序遍历字符串，去除尾部多余的 null"""
if tree_root is None:
return "null"
result_list = []
process_queue = deque([tree_root])
while process_queue:
node = process_queue.popleft()
if node is None:
result_list.append("null")
else:
result_list.append(node.value)
process_queue.append(node.left)
process_queue.append(node.right)
# 移除序列末尾无意义的空节点标识
while result_list and result_list[-1] == "null":
result_list.pop()
return " ".join(result_list)
def solve_service_merging():
# 读取全部输入行
raw_lines = [line.strip() for line in sys.stdin.read().splitlines() if line.strip()]
if len(raw_lines) < 2:
return
# 构建两棵待处理的树
tree_one = construct_tree_from_sequence(raw_lines[0])
tree_two = construct_tree_from_sequence(raw_lines[1])
if tree_one is None:
print(serialize_tree_to_level_order(tree_two))
return
if tree_two is None:
print(serialize_tree_to_level_order(tree_one))
return
# 策略一：尝试将树 2 作为子树合并到树 1 的某个位置
match_in_one = locate_service_node(tree_one, tree_two.value)
if match_in_one and check_merge_compatibility(match_in_one, tree_two):
execute_tree_merge(match_in_one, tree_two)
print(serialize_tree_to_level_order(tree_one))
return
# 策略二：尝试将树 1 作为子树合并到树 2 的某个位置
match_in_two = locate_service_node(tree_two, tree_one.value)
if match_in_two and check_merge_compatibility(match_in_two, tree_one):
execute_tree_merge(match_in_two, tree_one)
print(serialize_tree_to_level_order(tree_two))
return
# 若均不满足合并条件
print(0)
if __name__ == "__main__":
solve_service_merging()
第3题：智能公交最短路径规划
题面描述
你正在参与开发一款智能公交调度系统，该系统需要为自动驾驶的电动公交规划从起点到终点的最短时间路径。
城市道路网络由 N 个交叉路口（编号 0 ~ N-1）构成，道路为单向，每条道路有固定的通行时间，其中有 K 个路口建有充电站。
现在需要规划一辆电动公交车，从起点 S 到终点 T 的路线。存在以下约束：
车辆的电池电量有限，且不同路段的能耗不同，不能在电量不足的情况下通过某条道路（即剩余电量 < 通过该道路需要的电量的情况）。
车辆只能在充电站进行充电，不能在路段中途充电。
在充电站可以选择恢复电池至满电，也可以不充电，无论剩余多少电量每次充满电耗时为 1，不充电不耗时。
请你设计一个算法，找出公交车从起点 S 到终点 T 的总耗时最少的路径，并返回最小耗时。
测试用例
样例 1 输入
5 2 6 0 4 3 301 2 10 25 21 33 12 31 33 41 21 42 32 3样例 1 输出
7样例 1 说明
充电站位于路口 2 和 3。通过路径 0 -> 1 -> 2 -> 4，在 2 号充电站充满电，总耗时为 7。
解题思路
本题需要在满足电量限制的前提下，求从起点 S 到终点 T 的最短总耗时。
可以使用扩展状态图上的 Dijkstra 算法。
将状态定义为：(current_intersection, current_battery)。
状态转移：
对于当前状态 (u, e)：
经过道路：若存在从 u 到 v 的道路，耗时为 t，能耗为 c。当 e >= c 时，可以转移到 (v, e-c)，新增耗时 t。
在充电站充电：如果当前路口 u 是充电站，并且电量不满，则可以花费 1 个单位时间，将电量恢复为满电：(u, battery_capacity)，新增耗时 1。
答案：
终点 T 可以以任意剩余电量到达，因此答案为 min(dist[T][any_energy])。
若所有状态都不可达，则输出 -1。
（更加详细解题思路和CPP、Java代码加我微信获取）
# 华为机考题号：3
import sys
import heapq
def calculate_min_travel_duration(node_count, road_network, charging_station_map, start_node, end_node, initial_battery, battery_capacity):
"""使用 Dijkstra 算法在扩展状态空间（位置，电量）中搜索最短路径"""
# 极大值，表示不可达
INF = 10**18
# dist[u][e] 表示到达路口 u，且剩余电量为 e 时的最少累计耗时
min_time_to_state = [[INF] * (battery_capacity + 1) for _ in range(node_count)]
# 初始化起点状态
min_time_to_state[start_node][initial_battery] = 0
priority_queue = [(0, start_node, initial_battery)]
while priority_queue:
current_duration, u, current_energy = heapq.heappop(priority_queue)
# 排除已找到更优路径的过期状态
if current_duration != min_time_to_state[u][current_energy]:
continue
# 目标达成判定：虽然可以在终点继续操作，但最短路径通常在第一次到达时通过更小电量获得
# 我们继续运行直到队列为空以确保得到全局最优
# 动作一：在充电站充满电
if charging_station_map[u] and current_energy < battery_capacity:
new_duration = current_duration + 1
if new_duration < min_time_to_state[u][battery_capacity]:
min_time_to_state[u][battery_capacity] = new_duration
heapq.heappush(priority_queue, (new_duration, u, battery_capacity))
# 动作二：尝试通过所有可达的单向道路
for v, travel_time, energy_cost in road_network[u]:
if current_energy >= energy_cost:
remaining_energy = current_energy - energy_cost
new_duration = current_duration + travel_time
if new_duration < min_time_to_state[v][remaining_energy]:
min_time_to_state[v][remaining_energy] = new_duration
heapq.heappush(priority_queue, (new_duration, v, remaining_energy))
# 在所有到达终点的不同电量状态中选取耗时最小值
final_result = min(min_time_to_state[end_node])
return -1 if final_result == INF else final_result
def main():
# 读取标准输入并扁平化
input_data = list(map(int, sys.stdin.read().split()))
if not input_data:
return
ptr = 0
N = input_data[ptr]; ptr += 1 # 路口数
K = input_data[ptr]; ptr += 1 # 充电站数
M = input_data[ptr]; ptr += 1 # 道路数
S = input_data[ptr]; ptr += 1 # 起点
T = input_data[ptr]; ptr += 1 # 终点
init_e = input_data[ptr]; ptr += 1 # 初始电量
max_e = input_data[ptr]; ptr += 1 # 满电电量
# 构建邻接表
road_network = [[] for _ in range(N)]
for _ in range(M):
u = input_data[ptr]; ptr += 1
v = input_data[ptr]; ptr += 1
t = input_data[ptr]; ptr += 1
c = input_data[ptr]; ptr += 1
road_network[u].append((v, t, c))
# 标记充电站位置
charging_station_map = [False] * N
for _ in range(K):
station_node = input_data[ptr]; ptr += 1
charging_station_map[station_node] = True
# 执行计算并输出
print(calculate_min_travel_duration(N, road_network, charging_station_map, S, T, init_e, max_e))
if __name__ == "__main__":
main()
扫描它，然后带走我：
微信号｜ jackwwang8
bilibili｜ 养只猫一米哒
小红书｜ 2878931801
