【2024最新华为OD-C卷试题汇总】传递悄悄话的最长时间(100分) - 三语言AC题解(Python/Java/Cpp)

🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-C卷的三语言AC题解

💻 ACM银牌🥈| 多次AK大厂笔试 | 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

文章目录

  • 前言
    • 🧭 机试备考指南
    • 💊 传递悄悄话的最长时间
      • 题目描述
      • 输入格式
      • 输出格式
      • 样例输入
      • 样例输出
      • 数据范围
      • 题解
      • 参考代码
    • 🍓 AC代码截图 ✅

前言

🧭 机试备考指南

  • 华为OD的题库大半年跟新一次,也就是说,一旦跟新,那么本年用的题目就是从该题库种选题,大概有100~200道左右

  • 最近考试换为C/D卷,C/D卷题库是一样的,D卷为双机位监控,某些外包公司应聘的为D卷。

  • 为此清隆帮大家搜集并整理了C卷的题库,后续会由清隆的ACM银牌团队将题目整理后搬上OJ,支持在线评测

💊 传递悄悄话的最长时间

题目描述

在一个大家庭的聚会上,家庭成员站在由二叉树形式组织的位置上。每个位置上有一人,每个人之间的连接代表一条传递悄悄话的路径,且这条路径上有一个时间消耗。现在,根位置的K小姐想将一个悄悄话传递给所有人。每个连接的数字表示K小姐传递悄悄话给该节点的人所需额外时间。请计算使得所有家庭成员都听到这个悄悄话所需的最长时间。

输入格式

输入包含一行,由空格隔开的整数序列。这个序列以层序遍历的方式描述了一个二叉树,其中 -1 表示空节点。序列的第一个数字是根节点,表示从K小姐开始的时间为0。

输出格式

输出一个整数,表示所有节点都接收到悄悄话的最长时间。

样例输入

0 9 20 -1 -1 15 7 -1 -1 -1 -1 3 2

样例输出

38

数据范围

输入的二叉树节点个数不超过 1000 1000 1000,时间都是非负整数,不超过 100 100 100

题解

这个题目的核心是对二叉树进行遍历,并计算从根节点到每一个节点的路径时间。由于使用的是层序遍历的输入方式,我们可以使用队列来帮助我们构造这个二叉树,并同时计算从根节点到其他节点的时间。我们需要追踪的是从根节点到每个节点的累计时间,最终输出最大的那个时间,即为所有人都接收到悄悄话的最长时间。

参考代码

  • Cpp
#include <iostream>
#include <queue>
#include <vector>
using namespace std;int main() {vector<int> input;int tmp;while (cin >> tmp) {input.push_back(tmp);}if (input.empty() || input[0] == -1) {cout << "0" << endl;return 0;}queue<pair<int, int>> q; // pair<index, time>q.push({0, input[0]});int maxTime = 0;while (!q.empty()) {auto [index, currTime] = q.front();q.pop();maxTime = max(maxTime, currTime);int leftChildIndex = 2 * index + 1;int rightChildIndex = 2 * index + 2;if (leftChildIndex < input.size() && input[leftChildIndex] != -1) {q.push({leftChildIndex, currTime + input[leftChildIndex]});}if (rightChildIndex < input.size() && input[rightChildIndex] != -1) {q.push({rightChildIndex, currTime + input[rightChildIndex]});}}cout << maxTime << endl;return 0;
}
  • Python
from queue import Queueinput_str = input().split()
input = [int(x) if x != '-1' else -1 for x in input_str]if not input or input[0] == -1:print("0")exit()q = Queue()
q.put((0, input[0]))
max_time = 0while not q.empty():index, curr_time = q.get()max_time = max(max_time, curr_time)left_child_index = 2 * index + 1right_child_index = 2 * index + 2if left_child_index < len(input) and input[left_child_index] != -1:q.put((left_child_index, curr_time + input[left_child_index]))if right_child_index < len(input) and input[right_child_index] != -1:q.put((right_child_index, curr_time + input[right_child_index]))print(max_time)
  • Java
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class MaxSumPath {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String[] inputStr = scanner.nextLine().split(" ");int[] input = new int[inputStr.length];for (int i = 0; i < inputStr.length; i++) {input[i] = Integer.parseInt(inputStr[i]);}if (input.length == 0 || input[0] == -1) {System.out.println("0");return;}Queue<Pair> queue = new LinkedList<>();queue.add(new Pair(0, input[0]));int maxTime = 0;while (!queue.isEmpty()) {Pair pair = queue.poll();int index = pair.index;int currTime = pair.time;maxTime = Math.max(maxTime, currTime);int leftChildIndex = 2 * index + 1;int rightChildIndex = 2 * index + 2;if (leftChildIndex < input.length && input[leftChildIndex] != -1) {queue.add(new Pair(leftChildIndex, currTime + input[leftChildIndex]));}if (rightChildIndex < input.length && input[rightChildIndex] != -1) {queue.add(new Pair(rightChildIndex, currTime + input[rightChildIndex]));}}System.out.println(maxTime);}static class Pair {int index;int time;Pair(int index, int time) {this.index = index;this.time = time;}}
}

🍓 AC代码截图 ✅

  • Python
    在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/331147.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

42-2 应急响应之计划任务排查

一、进程排查 进程排查是指通过分析系统中正在运行的进程,以识别和处理恶意程序或异常行为。在Windows和Linux系统中,进程是操作系统的基本单位,因此对于发现和处理恶意软件或异常活动至关重要。恶意程序通常会以进程的形式在系统中运行,执行各种恶意操作,比如窃取信息、破…

自定义RedisTemplate序列化器

大纲 RedisSerializerFastJsonRedisSerializer自定义二进制序列化器总结代码 在《RedisTemplate保存二进制数据的方法》一文中&#xff0c;我们将Java对象通过《使用java.io库序列化Java对象》中介绍的方法转换为二进制数组&#xff0c;然后保存到Redis中。实际可以通过定制Red…

Leetcode刷题笔记2

283. 移动零 283. 移动零 - 力扣&#xff08;LeetCode&#xff09; 数据划分、数据分块 利用数组下标充当指针cur&#xff1a;从左往右扫描数组&#xff0c;遍历数组dest&#xff1a;已处理的区间内&#xff0c;非零元素的最后一个位置 一共被分为三个区间 [0,dest] [dest1,cu…

42-3 应急响应之服务排查

一、服务排查 服务是后台运行的进程,可在计算机启动时自动启动,也可暂停和重新启动,且不显示用户界面。它们特别适用于长时间运行的功能,以避免影响其他用户在同一台计算机上的工作。在应急响应中,服务常被恶意软件用作驻留方法。 二、Windows服务排查 打开【运行】对话框…

【C++项目】实时聊天的在线匹配五子棋对战游戏

目录 项目介绍 开发环境 核心技术 项目前置知识点介绍 Websocketpp 1. WebSocket基本认识 2. WebSocket协议切换原理解析 3. WebSocket报文格式 4. Websocketpp介绍 5. 搭建一个简单WebSocket服务器 JsonCpp 1. Json格式的基本认识 2. JsonCpp介绍 3. 序列化与反序…

iPhone实况照片从Windows资源管理器复制的JPG+MOV无法正常还原到iPhone

背景&#xff1a; 之前使用的iPhone 15 Pro&#xff0c;使用的Windows资源管理器当中复制导出的实况照片&#xff0c;复制出来的格式例如IMG_0001.JPG, IMG_0001.MOV。之后手机就卖掉了。现在使用的iPhone 14 Pro Max&#xff0c;想要导回之前备份的实况照片。尝试使用爱思助手…

VBA即用型代码手册:删除Excel中空白行Delete Blank Rows in Excel

我给VBA下的定义&#xff1a;VBA是个人小型自动化处理的有效工具。可以大大提高自己的劳动效率&#xff0c;而且可以提高数据的准确性。我这里专注VBA,将我多年的经验汇集在VBA系列九套教程中。 作为我的学员要利用我的积木编程思想&#xff0c;积木编程最重要的是积木如何搭建…

一篇文章讲透排序算法之希尔排序

希尔排序是对插入排序的优化&#xff0c;如果你不了解插入排序的话&#xff0c;可以先阅读这篇文章&#xff1a;插入排序 目录 1.插入排序的问题 2.希尔排序的思路 3.希尔排序的实现 4.希尔排序的优化 5.希尔排序的时间复杂度 1.插入排序的问题 如果用插入排序对一个逆序…

单片机设计注意事项

1.电源线可以30mil走线&#xff0c;信号线可以6mil走线 2.LDO推荐 SGM2019-3.3,RT9013,RT9193,1117-3.3V。 3.单片机VCC要充分滤波后再供电&#xff0c;可以接0.1uf的电容 4.晶振附件不要走其他元件&#xff0c;且放置完单片机后就放置晶振&#xff0c;晶振靠近X1,X2。

SpringBoot高级原理详解

文章目录 1 SpringBoot自动化配置原理01-SpringBoot2高级-starter依赖管理机制02-SpringBoot2高级-自动化配置初体验03-SpringBoot2高级-底层原理-Configuration配置注解04-SpringBoot2高级-底层原理-Import注解使用105-SpringBoot2高级-底层原理-Import注解使用206-SpringBoot…

微信小程序上线必备:SSL证书申请以及安装

一、认识ssl证书 1、ssl证书是什么&#xff1f; SSL证书&#xff0c;全称Secure Socket Layer Certificate&#xff0c;是一种数字证书&#xff0c;它遵循SSL&#xff08;现在通常指TLS&#xff0c;Transport Layer Security&#xff09;协议标准&#xff0c;用于在客户端&…

打造AI虚拟伴侣 - 优化方案

第一部分:框架优化概述 1、精确定位: 构建一个高度灵活且用户友好的平台,旨在通过无缝集成多种大型语言模型(LLMs)后端,为用户创造沉浸式的角色交互体验。不仅适配电脑端,还特别优化移动端体验,满足二次元AI虚拟伴侣市场的特定需求。 2、核心功能强化: 增强后端兼容…

k8s——Pod详解

一、Pod基础概念 1.1 Pod定义 Pod是kubernetes中最小的资源管理组件&#xff0c;Pod也是最小化运行容器化应用的资源对象。一个Pod代表着集群中运行的一个进程。kubernetes中其他大多数组件都是围绕着Pod来进行支撑和扩展Pod功能的&#xff0c;例如&#xff0c;用于管理Pod运行…

华为云服务培训

一、存储类服务实践 是什么&#xff1a; 云硬盘( Elastic Volume Service )是一种为 ECS&#xff08;弹性云服务器&#xff09;、BMS&#xff08;裸金属服务器&#xff09; 等计算服务提供持久性存储的服务。 作用&#xff1a; 它通过数据冗余和缓存加速等多项技术&#xf…

【C++高阶(一)】继承

目录 一、继承的概念 1.继承的基本概念 2.继承的定义和语法 3.继承基类成员访问方式的变化 ​编辑 4.总结 二、基类和派生类对象赋值转换 三、继承中的作用域 四、派生类的默认成员函数 1.派生类中的默认构造函数 2.派生类中的拷贝构造函数 3.派生类中的移动构造函数…

[国产大模型简单使用介绍] 开源与免费API

个人博客:Sekyoro的博客小屋 个人网站:Proanimer的个人网站 随着大模型技术蓬勃发展和开源社区越来越活跃,国内的大模型也如雨后春笋一般.这时,一些就会问了,有了llama3,Mistral还有Gemma等等,国外大厂接连发力,一些开源社区也会有一些不错的模型,国内怎么比?对一个人使用,oll…

02.爬虫---HTTP基本原理

02.HTTP基本原理 1.URI 和 URL 的区别2.HTTP 和 HTTPS 的区别3.请求过程 1.URI 和 URL 的区别 URL&#xff08;Uniform Resource Locator&#xff09;即-统一资源定位符 URL是用来定位和访问互联网上资源的独特标识&#xff0c;它包括了资源的位置&#xff08;如IP地址或域名&a…

node.js —— 解读http模块

目录 http模块&#xff1a; http模块的引入&#xff1a; 创建web服务器的基本步骤&#xff1a; web服务器的一些基本属性&#xff1a; 上述知识汇总案例&#xff1a; http模块&#xff1a; http模块的引入&#xff1a; const http require (http) 创建web服务器的基本步骤…

记录docker ps查找指定容器的几个命令

1.docker ps | grep registry 查询包含registry的容器 2.docker ps | grep -E "reigistry\s" 开启正则匹配模式&#xff0c;匹配registry后面为空格的容器&#xff0c;若是匹配一整行可以这样写docker ps | grep -E "^([0-9a-f]{12})\sregistry\s.*" 这…

第八节 条件装配案例讲解

一、条件装配的作用是什么 条件装配是 Spring 框架中一个强大的特性&#xff0c;使得开发者能够创建更加灵活和可维护的应用程序。在 Spring Boot 中&#xff0c;这个特性被大量用于自动配置&#xff0c;极大地简化了基于 Spring 的应用开发。 二、条件装配注解 <dependen…