悄悄话 - 华为OD统一考试

OD统一考试(C卷)

分值: 100分

题解: Java / Python / C++

alt

题目描述

给定一个二叉树,每个节点上站一个人,节点数字表示父节点到该节点传递悄悄话需要花费的时间。

初始时,根节点所在位置的人有一个悄悄话想要传递给其他人,求二叉树所有节点上的人都接收到悄悄话花费的时间。

输入描述

给定二叉树

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

注: -1 表示空节点

image-20240131101708298

输出描述

返回所有节点都接收到悄悄话花费的时间

38

示例1

输入:
0 9 20 -1 -1 15 15 7 -1 -1 -1 -1 3 2

输出:
38

题解

这个题目是一个树的遍历问题,采用**深度优先搜索(DFS)**的方式解决。

遍历时叶子节点最晚到达时间即为答案。

Java

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author code5bug
 */
public class Main {

    static int[] arr;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        arr = Arrays.stream(scanner.nextLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();

        System.out.println(dfs(0));
    }

    // 从 idx 节点到叶子节点最大耗时
    static int dfs(int idx) {
        int maxCostTime = 0;

        // 左右节点
        int leftIdx = 2 * idx + 1, rightIdx = 2 * idx + 2;
        if (leftIdx < arr.length && arr[leftIdx] != -1) {
            maxCostTime = Math.max(maxCostTime, dfs(leftIdx));
        }

        if (rightIdx < arr.length && arr[rightIdx] != -1) {
            maxCostTime = Math.max(maxCostTime, dfs(rightIdx));
        }

        return arr[idx] + maxCostTime;
    }
}

Python

arr = list(map(int, input().split()))
n = len(arr)

def dfs(idx):
    global n
    max_cost_time = 0
	
    # 左右节点
    left_idx, right_idx = 2 * idx + 1, 2 * idx + 2
    if left_idx < n and arr[left_idx] != -1:
        max_cost_time = max(max_cost_time, dfs(left_idx))
    if right_idx < n and arr[right_idx] != -1:
        max_cost_time = max(max_cost_time, dfs(right_idx))

    return arr[idx] + max_cost_time


print(dfs(0))

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> arr;

// 从 idx 节点到叶子节点最大耗时
int dfs(int idx) {
    int maxCostTime = 0;

    // 左右节点
    int leftIdx = 2 * idx + 1, rightIdx = 2 * idx + 2;
    if (leftIdx < arr.size() && arr[leftIdx] != -1) {
        maxCostTime = max(maxCostTime, dfs(leftIdx));
    }

    if (rightIdx < arr.size() && arr[rightIdx] != -1) {
        maxCostTime = max(maxCostTime, dfs(rightIdx));
    }

    return arr[idx] + maxCostTime;
}

int main() {

    int num;
    while (cin >> num) {
        arr.push_back(num);
    }

    cout << dfs(0) << endl;

    return 0;
}

‍❤️‍华为OD机试面试交流群每日真题分享): 加V时备注“华为od加群”

🙏整理题解不易, 如果有帮助到您,请给点个赞 ‍❤️‍ 和收藏 ⭐,让更多的人看到。🙏🙏🙏

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

vue3.0 + 动态加载组件 + 全局注册组件

首先 vue 动态加载组件使用的是 component 标签&#xff0c;并通过设置组件的is 属性来指定要渲染的组件。例如&#xff1a; <component :is"currentComponent"></component>其中&#xff0c;currentComponent 是一个变量&#xff0c;它的值可以是以下几…

【图论】【状态压缩】【树】【深度优先搜索】1617. 统计子树中城市之间最大距离

作者推荐 【动态规划】【字符串】【行程码】1531. 压缩字符串 本文涉及的知识点 图论 深度优先搜索 状态压缩 树 LeetCode1617. 统计子树中城市之间最大距离 给你 n 个城市&#xff0c;编号为从 1 到 n 。同时给你一个大小为 n-1 的数组 edges &#xff0c;其中 edges[i] …

FPGA工程师的重要技能

写代码是最难的嘛&#xff1f; 不是 会调试代码才是你的闪光点&#xff01;&#xff01; 很多人觉得写代码是最重要的但这不是一个优秀的FPGA工程师的核心竞争力 企业工作也更加注重你调试代码的能力 因此我们的课程老师对课程设计也是很有要求的 写代码是最难的嘛&#…

HT71663 13V,12A全集成同步升压转换器 中文资料 规格书

HT71663是一款高功率、全集成升压转换器&#xff0c;集成16mΩ功率开关管和23mΩ同步整流管&#xff0c;为便携式系统提供G效的小尺寸处理方案。 HT71663具有2.7V至13V宽输入电压范围&#xff0c;可为采用单节或两节锂电池的应用提供支持。该器件具备10A开关电流能力&#xff…

CHS_05.2.3.4_1+信号量机制

CHS_05.2.3.4_1信号量机制 知识总览信号量机制信号量机制——整型信号量信号量机制——记录型信号量知识回顾 在这个小节中 我们会学习信号量 机制这个极其重要的知识点 知识总览 在考研当中 我们需要掌握两种类型的信号量 一种是整形信号量 另一种是记录型信号量 我们会在后面…

数字孪生模型优化平台

老子云模型优化服务平台 一、模型优化 使用单模型轻量化、格式转换、倾斜摄影轻量化服务。 1、格式转换 只需上传原始单模型文件&#xff0c;就能在云端自动发起转换。 服务介绍&#xff1a; 支持格式输出为FBX、OBJ、STL、STP格式&#xff08;其他输出格式陆续上线中&…

企业级大数据安全架构(七)服务安全

作者&#xff1a;楼高 在企业级大数据安全方案中&#xff0c;本节主要介绍服务安全问题&#xff0c;引入kerberos认证机制&#xff0c;目前直接对接kerberos使用较多&#xff0c;这里我们使用FreeIPA来集成kerberos FreeIPA官网下载地址&#xff1a;https://www.freeipa.org/p…

Android systemui 编译

目录 简介&#xff1a; 一、步骤 二、下载源码 三、环境配置 四、确定好需要编译版本 五、编译SystemUI 步骤1&#xff1a;进入源代码目录 步骤2&#xff1a;初始化编译环境 步骤3&#xff1a;选择目标设备 步骤4&#xff1a;编译SystemUI 步骤5&#xff1a;查找生成…

指针的深入了解6

1.回调函数 回调函数就是一个通过函数指针调用的函数。 如果你把函数的指针&#xff08;地址&#xff09;作为参数传递给另一个函数&#xff0c;当这个指针被用来调用其所指向的函数 时&#xff0c;被调用的函数就是回调函数。回调函数不是由该函数的实现方直接调用&#xff0…

【Tomcat与网络5】再论Tomcat的工作过程与两种经典的设计模式

前面两篇&#xff0c;我们重点分析了Tomcat的容器和连接器的基本设计&#xff0c;今天我们来看一下两个机构如何在service的调度下进行协同工作的。 目录 1.模板模式与Tomcat的重用性设计 2.观察者模式与Tomcat可扩展性设计 1.模板模式与Tomcat的重用性设计 首先&#xff0…

车规级高压LDO正式上线

随着汽车电子行业向着智能化、物联网化的趋势发展&#xff0c;LDO的性能在车载电源设计中变得越来越重要。由于车载应用使用电池供电&#xff0c;所以对系统待机功耗有较高要求。例如感应雨刷、感应后备箱、自动大灯等功能&#xff0c;在触发前都需要保持低功耗工作&#xff0c…

Pandas.DataFrame.quantile() 分位数 详解 含代码 含测试数据集 随Pandas版本持续更新

关于Pandas版本&#xff1a; 本文基于 pandas2.2.0 编写。 关于本文内容更新&#xff1a; 随着pandas的stable版本更迭&#xff0c;本文持续更新&#xff0c;不断完善补充。 传送门&#xff1a; Pandas API参考目录 传送门&#xff1a; Pandas 版本更新及新特性 传送门&…

Flask 入门2:路由

1. 前言 在上一节中&#xff0c;我们使用到了静态路由&#xff0c;即一个路由规则对应一个 URL。而在实际应用中&#xff0c;更多使用的则是动态路由&#xff0c;它的 URL是可变的。 2. 定义一个很常见的路由地址 app.route(/user/<username>) def user(username):ret…

java servlet勤工助学家教管系统Myeclipse开发mysql数据库web结构java编程计算机网页项目

一、源码特点 java servlet 勤工助学家教管系统是一套完善的java web信息管理系统 serlvetdaobean mvc 模式开发 &#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为TOMCAT7.0,Myecli…

streampark+flink一键整库或多表同步mysql到doris实战

streamparkflink一键整库或多表同步mysql到doris实战&#xff0c;此应用一旦推广起来&#xff0c;那么数据实时异构时&#xff0c;不仅可以减少对数据库的查询压力&#xff0c;还可以减少数据同步时的至少50%的成本&#xff0c;还可以减少30%的存储成本&#xff1b; streampar…

2024年【天津市安全员C证】新版试题及天津市安全员C证模拟考试题

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 天津市安全员C证新版试题是安全生产模拟考试一点通总题库中生成的一套天津市安全员C证模拟考试题&#xff0c;安全生产模拟考试一点通上天津市安全员C证作业手机同步练习。2024年【天津市安全员C证】新版试题及天津市…

java基础(面试用)

一、基本语法 1. 注释有哪几种形式&#xff1f; //单行注释&#xff1a;通常用于解释方法内某单行代码的作用。 //int i 0;//多行注释&#xff1a;通常用于解释一段代码的作用。 //int i 0; //int i 0;//文档注释&#xff1a;通常用于生成 Java 开发文档。 /* *int i 0; …

实现自己的小功能(方案二)

第一套方案废弃的原因是数据不准确&#xff0c;大家可以使用Tushare试试&#xff0c;多测试一些。 方案二的整体流程&#xff1a; 先随机检测数据&#xff08;50条&#xff09;处理后数据的精度问题&#xff08;第一套方案也遇到了这个问题&#xff09; 1、下载数据 使用通达…

马哈鱼SQLFlow Lite的python版本

Gudu SQLFlow 是一款用来分析各种数据库的 SQL 语句和存储过程来获取复杂的数据血缘关系并进行可视化的工具。 Gudu SQLFlow Lite version for python 可以让 python 开发者把数据血缘分析和可视化能力快速集成到他们自己的 python 应用中。 Gudu SQLFlow Lite version for p…

【JAVA】Semaphore 有什么作用

&#x1f34e;个人博客&#xff1a;个人主页 &#x1f3c6;个人专栏&#xff1a;JAVA ⛳️ 功不唐捐&#xff0c;玉汝于成 目录 前言 正文 1. 二进制信号量&#xff1a; 2. 计数信号量&#xff1a; 结语 我的其他博客 前言 Semaphore&#xff08;信号量&#xff09;作为…