大家好，我是吴师兄。
继续每天陪大家练习一场大厂算法题，拿下秋招！
今天练习的是
华为秋招笔试题
。
2024 年的大厂真题可以在我的网站上进行练习。
网站地址：
https://oj.algomooc.com/
关注吴师兄，算法学习好轻松
1、小C的二叉树消消乐
题目介绍
小C有两棵满二叉树：一棵是原始二叉树，另一棵是参照二叉树。你需要比对它们的每一层，找出同一层级中值相同的节点并将它们从原始二叉树中消除。消除规则是：如果同一层的节点值相同，则可以成对消除。消除后，原始二叉树中有效的节点值按出现的频率从高到低排序，若频率相同，则按节点值从大到小排列。若所有节点被消除，则输出0。
题目解析
这道题目考察了
满二叉树
的结构，以及
哈希表
的使用来统计节点的频率。由于是满二叉树，可以利用层序遍历的方法，每一层的节点数量是
，因此我们可以逐层处理，比较每层原始二叉树和参照二叉树的节点，将相同的节点在原始二叉树中消除。
解题思路
-
层序遍历
：首先根据满二叉树的性质，将每层的节点取出。每一层的节点数量是
，即第k层有
个节点。
-
节点频率统计
：利用哈希表统计每层原始二叉树和参照二叉树节点的出现频率。
-
消除相同节点
：遍历每层原始二叉树中的节点，对于那些在参照二叉树中相同值的节点，消除相应数量的节点。
-
统计剩余节点
：对消除后的原始二叉树节点进行统计，将剩余节点的频率按要求进行排序：频率从高到低，频率相同则按节点值从大到小排列。
参考代码
# 关注吴师兄，算法好轻松
from collections import Counter
# 读取输入
n = int(input()) # 原始二叉树的节点个数
a = list(map(int, input().split())) # 原始二叉树的节点值
m = int(input()) # 参照二叉树的节点个数
b = list(map(int, input().split())) # 参照二叉树的节点值
# 初始化计数器
c = Counter()
# p表示当前层级的起始位置，k表示当前层级的层数
p = k = 0
# 遍历原始二叉树和参照二叉树的节点，按层级进行处理
while p la = a[p:p + (1 <# 取出原始二叉树当前层的节点
lb = b[p:p + (1 <# 取出参照二叉树当前层的节点
# 统计当前层原始二叉树和参照二叉树中各个节点的频率
ca = Counter(la)
cb = Counter(lb)
# 对原始二叉树的节点进行消除
for key, val in ca.items():
rest = val - cb.get(key, 0) # 减去参照二叉树中相同值的节点数
if rest > 0:
c[key] += rest # 记录剩余有效节点
p += 1 <# 更新p指针，移动到下一层
k += 1 # 进入下一层
# 对剩余有效节点进行排序，按频率降序排列，频率相同时按值降序排列
ans = sorted(c.keys(), key=lambda x: (c[x], x), reverse=True)
# 输出结果
if len(ans) == 0:
print(0)
else:
print("".join(map(str, ans)))
知识点及相关 LeetCode 题目
这道题目涉及到的主要知识点包括
二叉树层序遍历
、
哈希表
以及
排序算法
。与之相关的LeetCode题目如下：
-
LeetCode 第 102 号问题：二叉树的层次遍历
，考察层次遍历算法。
-
LeetCode 第 347 号问题：前 K 个高频元素
，涉及哈希表统计频率并排序的操作。
遇到这类问题时，首先需要明确树的层级关系，其次是通过哈希表高效统计频率并排序。
2、小C的好友推荐系统
题目介绍
小C开发了一个社交网络平台，在其中你需要为用户推荐好友。推荐依据是“共同好友数量”。当两个用户非好友时，他们的相似度为两人拥有的共同好友数，系统会为给定用户推荐相似度最高的前L个用户，要求输出推荐的用户编号，若相似度相同则按用户编号从小到大排序。
题目解析
这道题目属于
图论中的邻接表
和
哈希表
处理问题。我们可以使用邻接表来存储好友关系，然后对于每个用户，遍历所有其他用户，计算他们之间的共同好友数。
解题思路
-
-
非好友用户的处理
：对于给定的用户，找出其非好友用户，计算这些非好友用户和给定用户之间的共同好友数量。
-
相似度计算与排序
：根据共同好友数量进行排序，若共同好友数量相同，则按用户编号从小到大排列，最终输出前L个用户。
-
参考代码
# 关注吴师兄，算法好轻松
from collections import defaultdict
# 读取输入
n, m, k, l = map(int, input().split())
# 构建好友关系的邻接表
g = defaultdict(set)
for _ in range(m):
x, y = map(int, input().split())
g[x].add(y)
g[y].add(x)
# 用于存储符合条件的用户及其与用户k的共同好友数量
ls = []
# 枚举所有用户i，排除掉用户k本身以及与用户k已经是好友的用户
for i in range(1, n + 1):
if i != k and i not in g[k]:
# 计算用户i与用户k的共同好友数量
ls.append((len(g[i] & g[k]), i))
# 按共同好友数量降序、用户编号升序进行排序
ls.sort(key=lambda x: (-x[0], x[1]))
# 提取排序后的用户编号，并补齐不足l个的情况
ans = [x[1] for x in ls[:l]] + [0] * (l - len(ls))
# 输出推荐的好友编号
print(*ans)
知识点及相关 LeetCode 题目
这道题目涉及到的主要知识点包括
图的邻接表表示法
、
哈希表
和
排序算法
。与此题相关的LeetCode题目有：
-
LeetCode 第 133 号问题：克隆图
，考察图的邻接表处理。
-
LeetCode 第 347 号问题：前 K 个高频元素
，同样涉及哈希表和排序。
当处理好友推荐等问题时，构建高效的邻接表并快速统计相似度是关键。
3、小C的设备更换任务
题目介绍
小C需要为客户更换设备，并且随身携带的背包容量有限。你需要根据客户的优先级顺序为客户更换设备，并计算完成所有任务所需的最短距离。小C可以走直线或斜线，目标是最小化总距离。
题目解析
这道题目涉及到
动态规划
和
欧几里得距离的计算
。我们可以将问题转化为一个路径规划问题，背包容量有限，因此需要合理安排何时回公司补充设备，以最小化总距离。
解题思路
