【2024年华为OD机试】(C卷,100分)- 悄悄话 (Java JS PythonC/C++)
一、问题描述
题目描述
给定一个二叉树,每个节点上站一个人,节点数字表示父节点到该节点传递悄悄话需要花费的时间。
初始时,根节点所在位置的人有一个悄悄话想要传递给其他人,求二叉树所有节点上的人都接收到悄悄话花费的时间。
输入描述
给定二叉树的层序遍历序列:
0 9 20 -1 -1 15 7 -1 -1 -1 -1 3 2
注:-1
表示空节点。
输出描述
返回所有节点都接收到悄悄话花费的时间。
38
用例
输入
0 9 20 -1 -1 15 7 -1 -1 -1 -1 3 2
输出
38
说明
无
题目解析
层序遍历序列与二叉树结构
题目给出的输入信息是二叉树的层序遍历序列。层序遍历序列中,父子节点存在如下关系:
- 如果父节点在序列中的索引是
k
,则其左子节点在序列中的索引为2k+1
,右子节点在序列中的索引为2k+2
。
通过这种关系,我们可以直接从层序遍历序列中推导出二叉树的结构,而无需显式地构建二叉树。
悄悄话传递的时延计算
初始时,根节点所在位置的人有一个悄悄话想要传递给其他人。传递过程中,父节点将自身得到消息的时延累加到其各个子节点上。具体来说:
- 根节点的时延为
0
。 - 对于每个非空节点,其左子节点的时延为父节点的时延加上左子节点的传递时间。
- 对于每个非空节点,其右子节点的时延为父节点的时延加上右子节点的传递时间。
最终,所有节点都接收到悄悄话花费的时间就是所有叶子节点中最大的时延值。
示例解析
以输入序列0 9 20 -1 -1 15 7 -1 -1 -1 -1 3 2
为例:
- 根节点的时延为
0
。 - 左子节点的时延为
0 + 9 = 9
。 - 右子节点的时延为
0 + 20 = 20
。 - 左子节点的左子节点为空,右子节点的左子节点的时延为
20 + 15 = 35
。 - 右子节点的右子节点的时延为
20 + 7 = 27
。 - 左子节点的右子节点的左子节点的时延为
35 + 3 = 38
。 - 左子节点的右子节点的右子节点的时延为
35 + 2 = 37
。
最终,所有叶子节点中最大的时延值为38
,因此所有节点都接收到悄悄话花费的时间为38
。
通过这种方式,我们可以直接从层序遍历序列中计算出所有节点接收到悄悄话的总时间。
二、JavaScript算法源码
以下是对您提供的 JavaScript 代码的详细注释和讲解:
// 引入 readline 模块,并创建接口实例
const rl = require("readline").createInterface({ input: process.stdin });
// 获取异步迭代器,用于逐行读取输入
var iter = rl[Symbol.asyncIterator]();
// 定义异步函数 readline,用于读取一行输入
const readline = async () => (await iter.next()).value;
// 立即执行异步函数
void (async function () {
// 读取第一行输入,并将其按空格分割成数组,转换为数字数组 times
const times = (await readline()).split(" ").map(Number);
// 初始化变量 ans,用于记录最终结果(最大时延)
let ans = 0;
// 使用队列进行广度优先搜索(BFS),初始时将根节点(索引为 0)加入队列
const queue = [0];
// 当队列不为空时,继续处理
while (queue.length > 0) {
// 取出队列中的第一个节点(父节点)
const fa = queue.shift();
// 计算左子节点和右子节点的索引
const ch1 = 2 * fa + 1; // 左子节点索引
const ch2 = 2 * fa + 2; // 右子节点索引
// 判断左子节点是否存在
const ch1_exist = ch1 < times.length && times[ch1] != -1;
// 判断右子节点是否存在
const ch2_exist = ch2 < times.length && times[ch2] != -1;
// 如果左子节点存在
if (ch1_exist) {
// 将父节点的时延累加到左子节点
times[ch1] += times[fa];
// 将左子节点加入队列,继续处理
queue.push(ch1);
}
// 如果右子节点存在
if (ch2_exist) {
// 将父节点的时延累加到右子节点
times[ch2] += times[fa];
// 将右子节点加入队列,继续处理
queue.push(ch2);
}
// 如果当前节点是叶子节点(没有左子节点和右子节点)
if (!ch1_exist && !ch2_exist) {
// 更新最大时延 ans
ans = Math.max(ans, times[fa]);
}
}
// 输出最终结果(最大时延)
console.log(ans);
})();
代码功能讲解:
-
输入部分:
- 使用
readline
模块从控制台读取输入。 - 第一行输入是一个数组
times
,表示每个节点的时延值,-1
表示节点不存在。
- 使用
-
广度优先搜索(BFS):
- 使用队列实现 BFS,从根节点(索引为 0)开始遍历二叉树。
- 对于每个节点,计算其左子节点和右子节点的索引。
- 如果子节点存在,则将父节点的时延累加到子节点,并将子节点加入队列。
-
叶子节点处理:
- 如果当前节点是叶子节点(没有左子节点和右子节点),则更新最大时延
ans
。
- 如果当前节点是叶子节点(没有左子节点和右子节点),则更新最大时延
-
输出结果:
- 输出所有叶子节点中的最大时延。
示例运行:
假设输入如下:
1 2 3 -1 -1 4 5
程序会构建二叉树并计算每个叶子节点的时延:
9
总结:
该代码的主要功能是通过广度优先搜索(BFS)遍历二叉树,计算每个叶子节点的时延,并输出最大时延。通过队列和累加时延的方式,代码实现了对输入数据的处理和结果计算。
三、Java算法源码
以下是对您提供的 Java 代码的详细注释和讲解:
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// 创建 Scanner 对象,用于读取控制台输入
Scanner sc = new Scanner(System.in);
// 读取一行输入,按空格分割成字符串数组,并将其转换为整数数组 times
int[] times = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
// 初始化变量 ans,用于记录最终结果(最大时延)
int ans = 0;
// 使用 LinkedList 实现队列,用于广度优先搜索(BFS)
LinkedList<Integer> queue = new LinkedList<>();
// 将根节点(索引为 0)加入队列
queue.addLast(0);
// 当队列不为空时,继续处理
while (queue.size() > 0) {
// 取出队列中的第一个节点(父节点)
int fa = queue.removeFirst();
// 计算左子节点和右子节点的索引
int ch1 = 2 * fa + 1; // 左子节点索引
int ch2 = 2 * fa + 2; // 右子节点索引
// 判断左子节点是否存在
boolean ch1_exist = ch1 < times.length && times[ch1] != -1;
// 判断右子节点是否存在
boolean ch2_exist = ch2 < times.length && times[ch2] != -1;
// 如果左子节点存在
if (ch1_exist) {
// 将父节点的时延累加到左子节点
times[ch1] += times[fa];
// 将左子节点加入队列,继续处理
queue.addLast(ch1);
}
// 如果右子节点存在
if (ch2_exist) {
// 将父节点的时延累加到右子节点
times[ch2] += times[fa];
// 将右子节点加入队列,继续处理
queue.addLast(ch2);
}
// 如果当前节点是叶子节点(没有左子节点和右子节点)
if (!ch1_exist && !ch2_exist) {
// 更新最大时延 ans
ans = Math.max(ans, times[fa]);
}
}
// 输出最终结果(最大时延)
System.out.println(ans);
}
}
代码功能讲解:
-
输入部分:
- 使用
Scanner
从控制台读取一行输入。 - 将输入按空格分割成字符串数组,并转换为整数数组
times
,表示每个节点的时延值,-1
表示节点不存在。
- 使用
-
广度优先搜索(BFS):
- 使用
LinkedList
实现队列,从根节点(索引为 0)开始遍历二叉树。 - 对于每个节点,计算其左子节点和右子节点的索引。
- 如果子节点存在,则将父节点的时延累加到子节点,并将子节点加入队列。
- 使用
-
叶子节点处理:
- 如果当前节点是叶子节点(没有左子节点和右子节点),则更新最大时延
ans
。
- 如果当前节点是叶子节点(没有左子节点和右子节点),则更新最大时延
-
输出结果:
- 输出所有叶子节点中的最大时延。
示例运行:
假设输入如下:
1 2 3 -1 -1 4 5
程序会构建二叉树并计算每个叶子节点的时延:
9
总结:
该代码的主要功能是通过广度优先搜索(BFS)遍历二叉树,计算每个叶子节点的时延,并输出最大时延。通过队列和累加时延的方式,代码实现了对输入数据的处理和结果计算。
四、Python算法源码
以下是对您提供的 Python 代码的详细注释和讲解:
# 输入获取
# 从控制台读取一行输入,按空格分割成字符串列表,并将其转换为整数列表 times
times = list(map(int, input().split()))
# 算法入口
def getResult():
# 初始化变量 ans,用于记录最终结果(最大时延)
ans = 0
# 使用列表实现队列,用于广度优先搜索(BFS)
# 将根节点(索引为 0)加入队列
queue = [0]
# 当队列不为空时,继续处理
while len(queue) > 0:
# 取出队列中的第一个节点(父节点)
fa = queue.pop(0)
# 计算左子节点和右子节点的索引
ch1 = 2 * fa + 1 # 左子节点索引
ch2 = 2 * fa + 2 # 右子节点索引
# 判断左子节点是否存在
ch1_exist = ch1 < len(times) and times[ch1] != -1
# 判断右子节点是否存在
ch2_exist = ch2 < len(times) and times[ch2] != -1
# 如果左子节点存在
if ch1_exist:
# 将父节点的时延累加到左子节点
times[ch1] += times[fa]
# 将左子节点加入队列,继续处理
queue.append(ch1)
# 如果右子节点存在
if ch2_exist:
# 将父节点的时延累加到右子节点
times[ch2] += times[fa]
# 将右子节点加入队列,继续处理
queue.append(ch2)
# 如果当前节点是叶子节点(没有左子节点和右子节点)
if not ch1_exist and not ch2_exist:
# 更新最大时延 ans
ans = max(ans, times[fa])
# 返回最终结果(最大时延)
return ans
# 算法调用
print(getResult())
代码功能讲解:
-
输入部分:
- 使用
input()
从控制台读取一行输入。 - 将输入按空格分割成字符串列表,并转换为整数列表
times
,表示每个节点的时延值,-1
表示节点不存在。
- 使用
-
广度优先搜索(BFS):
- 使用列表实现队列,从根节点(索引为 0)开始遍历二叉树。
- 对于每个节点,计算其左子节点和右子节点的索引。
- 如果子节点存在,则将父节点的时延累加到子节点,并将子节点加入队列。
-
叶子节点处理:
- 如果当前节点是叶子节点(没有左子节点和右子节点),则更新最大时延
ans
。
- 如果当前节点是叶子节点(没有左子节点和右子节点),则更新最大时延
-
输出结果:
- 输出所有叶子节点中的最大时延。
示例运行:
假设输入如下:
1 2 3 -1 -1 4 5
程序会构建二叉树并计算每个叶子节点的时延:
9
总结:
该代码的主要功能是通过广度优先搜索(BFS)遍历二叉树,计算每个叶子节点的时延,并输出最大时延。通过队列和累加时延的方式,代码实现了对输入数据的处理和结果计算。
五、C/C++算法源码:
C 语言代码注释和讲解
#include <stdio.h>
#include <stdlib.h>
// 定义宏 MAX,用于比较两个数的大小
#define MAX(a,b) ((a) > (b) ? (a) : (b))
// 定义数组的最大大小
#define MAX_SIZE 10000
// 定义链表节点结构体
typedef struct ListNode {
int ele; // 节点存储的值
struct ListNode *next; // 指向下一个节点的指针
} ListNode;
// 定义链表结构体
typedef struct LinkedList {
int size; // 链表的长度
ListNode *head; // 指向链表头节点的指针
ListNode *tail; // 指向链表尾节点的指针
} LinkedList;
// 创建一个新的链表
LinkedList *new_LinkedList() {
LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList));
link->size = 0;
link->head = NULL;
link->tail = NULL;
return link;
}
// 向链表尾部添加一个节点
void addLast_LinkedList(LinkedList *link, int ele) {
ListNode *listNode = (ListNode *) malloc(sizeof(ListNode));
listNode->ele = ele;
listNode->next = NULL;
if (link->size == 0) {
// 如果链表为空,新节点既是头节点也是尾节点
link->head = listNode;
link->tail = listNode;
} else {
// 否则将新节点添加到链表尾部
link->tail->next = listNode;
link->tail = listNode;
}
link->size++; // 链表长度加 1
}
// 移除链表的第一个节点并返回其值
int removeFirst_LinkedList(LinkedList* link) {
if (link->size == 0) exit(-1); // 如果链表为空,退出程序
ListNode* removed = link->head;
if (link->size == 1) {
// 如果链表只有一个节点,移除后链表为空
link->head = NULL;
link->tail = NULL;
} else {
// 否则将头节点指向下一个节点
link->head = link->head->next;
}
link->size--; // 链表长度减 1
int res = removed->ele; // 获取移除节点的值
free(removed); // 释放移除节点的内存
return res;
}
int main() {
int times[MAX_SIZE]; // 存储输入的时延数组
int times_size = 0; // 时延数组的大小
// 从控制台读取输入,直到遇到换行符
while (scanf("%d", ×[times_size++])) {
if (getchar() != ' ') break;
}
// 记录最终结果(最大时延)
int ans = 0;
// 创建一个链表作为队列,用于广度优先搜索(BFS)
LinkedList* queue = new_LinkedList();
addLast_LinkedList(queue, 0); // 将根节点(索引为 0)加入队列
// 当队列不为空时,继续处理
while (queue->size > 0) {
int fa = removeFirst_LinkedList(queue); // 取出队列中的第一个节点(父节点)
int ch1 = 2 * fa + 1; // 左子节点索引
int ch2 = 2 * fa + 2; // 右子节点索引
// 判断左子节点是否存在
int ch1_exist = ch1 < times_size && times[ch1] != -1;
// 判断右子节点是否存在
int ch2_exist = ch2 < times_size && times[ch2] != -1;
// 如果左子节点存在
if (ch1_exist) {
times[ch1] += times[fa]; // 将父节点的时延累加到左子节点
addLast_LinkedList(queue, ch1); // 将左子节点加入队列
}
// 如果右子节点存在
if (ch2_exist) {
times[ch2] += times[fa]; // 将父节点的时延累加到右子节点
addLast_LinkedList(queue, ch2); // 将右子节点加入队列
}
// 如果当前节点是叶子节点(没有左子节点和右子节点)
if (!ch1_exist && !ch2_exist) {
ans = MAX(ans, times[fa]); // 更新最大时延
}
}
// 输出最终结果(最大时延)
printf("%d\n", ans);
return 0;
}
C++ 代码版本
C++ 提供了标准库中的 queue
,可以简化队列的实现。以下是 C++ 版本的代码:
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
int times[10000]; // 存储输入的时延数组
int times_size = 0; // 时延数组的大小
// 从控制台读取输入,直到遇到换行符
while (cin >> times[times_size++]) {
if (cin.get() != ' ') break;
}
// 记录最终结果(最大时延)
int ans = 0;
// 使用 STL 的 queue 作为队列,用于广度优先搜索(BFS)
queue<int> q;
q.push(0); // 将根节点(索引为 0)加入队列
// 当队列不为空时,继续处理
while (!q.empty()) {
int fa = q.front(); // 取出队列中的第一个节点(父节点)
q.pop();
int ch1 = 2 * fa + 1; // 左子节点索引
int ch2 = 2 * fa + 2; // 右子节点索引
// 判断左子节点是否存在
bool ch1_exist = ch1 < times_size && times[ch1] != -1;
// 判断右子节点是否存在
bool ch2_exist = ch2 < times_size && times[ch2] != -1;
// 如果左子节点存在
if (ch1_exist) {
times[ch1] += times[fa]; // 将父节点的时延累加到左子节点
q.push(ch1); // 将左子节点加入队列
}
// 如果右子节点存在
if (ch2_exist) {
times[ch2] += times[fa]; // 将父节点的时延累加到右子节点
q.push(ch2); // 将右子节点加入队列
}
// 如果当前节点是叶子节点(没有左子节点和右子节点)
if (!ch1_exist && !ch2_exist) {
ans = max(ans, times[fa]); // 更新最大时延
}
}
// 输出最终结果(最大时延)
cout << ans << endl;
return 0;
}
代码功能总结
-
输入部分:
- 从控制台读取一行输入,按空格分割成整数数组
times
,表示每个节点的时延值,-1
表示节点不存在。
- 从控制台读取一行输入,按空格分割成整数数组
-
广度优先搜索(BFS):
- 使用队列从根节点(索引为 0)开始遍历二叉树。
- 对于每个节点,计算其左子节点和右子节点的索引。
- 如果子节点存在,则将父节点的时延累加到子节点,并将子节点加入队列。
-
叶子节点处理:
- 如果当前节点是叶子节点(没有左子节点和右子节点),则更新最大时延
ans
。
- 如果当前节点是叶子节点(没有左子节点和右子节点),则更新最大时延
-
输出结果:
- 输出所有叶子节点中的最大时延。
示例运行
假设输入如下:
1 2 3 -1 -1 4 5
程序会构建二叉树并计算每个叶子节点的时延:
9
总结
- C 语言版本通过手动实现链表和队列来完成 BFS。
- C++ 版本利用 STL 的
queue
简化了队列的实现。 - 两种版本的核心逻辑相同,都是通过 BFS 遍历二叉树,计算叶子节点的最大时延。
六、尾言
什么是华为OD?
华为OD(Outsourcing Developer,外包开发工程师)是华为针对软件开发工程师岗位的一种招聘形式,主要包括笔试、技术面试以及综合面试等环节。尤其在笔试部分,算法题的机试至关重要。
为什么刷题很重要?
-
机试是进入技术面的第一关:
华为OD机试(常被称为机考)主要考察算法和编程能力。只有通过机试,才能进入后续的技术面试环节。 -
技术面试需要手撕代码:
技术一面和二面通常会涉及现场编写代码或算法题。面试官会注重考察候选人的思路清晰度、代码规范性以及解决问题的能力。因此提前刷题、多练习是通过面试的重要保障。 -
入职后的可信考试:
入职华为后,还需要通过“可信考试”。可信考试分为三个等级:- 入门级:主要考察基础算法与编程能力。
- 工作级:更贴近实际业务需求,可能涉及复杂的算法或与工作内容相关的场景题目。
- 专业级:最高等级,考察深层次的算法以及优化能力,与薪资直接挂钩。
刷题策略与说明:
2024年8月14日之后,华为OD机试的题库转为 E卷,由往年题库(D卷、A卷、B卷、C卷)和全新题目组成。刷题时可以参考以下策略:
-
关注历年真题:
- 题库中的旧题占比较大,建议优先刷历年的A卷、B卷、C卷、D卷题目。
- 对于每道题目,建议深度理解其解题思路、代码实现,以及相关算法的适用场景。
-
适应新题目:
- E卷中包含全新题目,需要掌握全面的算法知识和一定的灵活应对能力。
- 建议关注新的刷题平台或交流群,获取最新题目的解析和动态。
-
掌握常见算法:
华为OD考试通常涉及以下算法和数据结构:- 排序算法(快速排序、归并排序等)
- 动态规划(背包问题、最长公共子序列等)
- 贪心算法
- 栈、队列、链表的操作
- 图论(最短路径、最小生成树等)
- 滑动窗口、双指针算法
-
保持编程规范:
- 注重代码的可读性和注释的清晰度。
- 熟练使用常见编程语言,如C++、Java、Python等。
如何获取资源?
-
官方参考:
- 华为招聘官网或相关的招聘平台会有一些参考信息。
- 华为OD的相关公众号可能也会发布相关的刷题资料或学习资源。
-
加入刷题社区:
- 找到可信的刷题交流群,与其他备考的小伙伴交流经验。
- 关注知名的刷题网站,如LeetCode、牛客网等,这些平台上有许多华为OD的历年真题和解析。
-
寻找系统性的教程:
- 学习一本经典的算法书籍,例如《算法导论》《剑指Offer》《编程之美》等。
- 完成系统的学习课程,例如数据结构与算法的在线课程。
积极心态与持续努力:
刷题的过程可能会比较枯燥,但它能够显著提升编程能力和算法思维。无论是为了通过华为OD的招聘考试,还是为了未来的职业发展,这些积累都会成为重要的财富。
考试注意细节
-
本地编写代码
- 在本地 IDE(如 VS Code、PyCharm 等)上编写、保存和调试代码,确保逻辑正确后再复制粘贴到考试页面。这样可以减少语法错误,提高代码准确性。
-
调整心态,保持冷静
- 遇到提示不足或实现不确定的问题时,不必慌张,可以采用更简单或更有把握的方法替代,确保思路清晰。
-
输入输出完整性
- 注意训练和考试时都需要编写完整的输入输出代码,尤其是和题目示例保持一致。完成代码后务必及时调试,确保功能符合要求。
-
快捷键使用
- 删除行可用
Ctrl+D
,复制、粘贴和撤销分别为Ctrl+C
,Ctrl+V
,Ctrl+Z
,这些可以正常使用。 - 避免使用
Ctrl+S
,以免触发浏览器的保存功能。
- 删除行可用
-
浏览器要求
- 使用最新版的 Google Chrome 浏览器完成考试,确保摄像头开启并正常工作。考试期间不要切换到其他网站,以免影响考试成绩。
-
交卷相关
- 答题前,务必仔细查看题目示例,避免遗漏要求。
- 每完成一道题后,点击【保存并调试】按钮,多次保存和调试是允许的,系统会记录得分最高的一次结果。完成所有题目后,点击【提交本题型】按钮。
- 确保在考试结束前提交试卷,避免因未保存或调试失误而丢分。
-
时间和分数安排
- 总时间:150 分钟;总分:400 分。
- 试卷结构:2 道一星难度题(每题 100 分),1 道二星难度题(200 分)。及格分为 150 分。合理分配时间,优先完成自己擅长的题目。
-
考试环境准备
- 考试前请备好草稿纸和笔。考试中尽量避免离开座位,确保监控画面正常。
- 如需上厕所,请提前规划好时间以减少中途离开监控的可能性。
-
技术问题处理
- 如果考试中遇到断电、断网、死机等技术问题,可以关闭浏览器并重新打开试卷链接继续作答。
- 出现其他问题,请第一时间联系 HR 或监考人员进行反馈。
祝你考试顺利,取得理想成绩!