​LeetCode解法汇总2477. 到达首都的最少油耗

news/2024/7/17 21:31:03

 目录链接:

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目:

https://github.com/September26/java-algorithms

原题链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台


描述:

给你一棵 n 个节点的树(一个无向、连通、无环图),每个节点表示一个城市,编号从 0 到 n - 1 ,且恰好有 n - 1 条路。0 是首都。给你一个二维整数数组 roads ,其中 roads[i] = [ai, bi] ,表示城市 ai 和 bi 之间有一条 双向路 。

每个城市里有一个代表,他们都要去首都参加一个会议。

每座城市里有一辆车。给你一个整数 seats 表示每辆车里面座位的数目。

城市里的代表可以选择乘坐所在城市的车,或者乘坐其他城市的车。相邻城市之间一辆车的油耗是一升汽油。

请你返回到达首都最少需要多少升汽油。

示例 1:

输入:roads = [[0,1],[0,2],[0,3]], seats = 5
输出:3
解释:
- 代表 1 直接到达首都,消耗 1 升汽油。
- 代表 2 直接到达首都,消耗 1 升汽油。
- 代表 3 直接到达首都,消耗 1 升汽油。
最少消耗 3 升汽油。

示例 2:

输入:roads = [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]], seats = 2
输出:7
解释:
- 代表 2 到达城市 3 ,消耗 1 升汽油。
- 代表 2 和代表 3 一起到达城市 1 ,消耗 1 升汽油。
- 代表 2 和代表 3 一起到达首都,消耗 1 升汽油。
- 代表 1 直接到达首都,消耗 1 升汽油。
- 代表 5 直接到达首都,消耗 1 升汽油。
- 代表 6 到达城市 4 ,消耗 1 升汽油。
- 代表 4 和代表 6 一起到达首都,消耗 1 升汽油。
最少消耗 7 升汽油。

示例 3:

输入:roads = [], seats = 1
输出:0
解释:没有代表需要从别的城市到达首都。

提示:

  • 1 <= n <= 105
  • roads.length == n - 1
  • roads[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • roads 表示一棵合法的树。
  • 1 <= seats <= 105

解题思路:

首先广度搜索,找到分别走1步,2步,N步可以达到的城市。

然后从走N步可到达的城市开始,N步计算出需要多少油耗。

然后这个城市要达到的城市对应的人数+1,计算N-1步可以到达的。

 

代码:

class Solution {
    //达到key的节点集合
    Map<Integer, List<Integer>> map = new HashMap<>();
    Node[] nodes = new Node[100000];
    List<List<Node>> stepList = new ArrayList<>();

    public long minimumFuelCost(int[][] roads, int seats) {
        //广度遍历
        breadthSearch(roads);
        long sum = 0L;
        for (int i = stepList.size() - 1; i >= 0; i--) {
            System.out.println("sum:" + sum);
            for (Node itemNode : stepList.get(i)) {
                int to = itemNode.to;
                Node toNode = nodes[to];
                toNode.num += itemNode.num;
                sum += itemNode.num / seats;
                if (itemNode.num % seats != 0) {
                    sum++;
                }
            }
            System.out.println("sum:" + sum);
        }
        return sum;
    }

    private void breadthSearch(int[][] roads) {
        for (int[] road : roads) {
            int i1 = road[0];
            int i2 = road[1];
            addList(i1, i2);
            addList(i2, i1);
        }
        Node rootNode = new Node(0);
        nodes[0] = rootNode;
        List<Node> list = new ArrayList<>();
        list.add(rootNode);
        buildStepMap(list, 0);
    }

    private void addList(int to, int from) {
        List<Integer> integers = map.get(to);
        if (integers == null) {
            integers = new ArrayList<>();
            map.put(to, integers);
        }
        integers.add(from);
    }


    private void buildStepMap(List<Node> nodeList, int step) {
        List<Node> newNodeList = new ArrayList<>();
        step++;
        for (Node node : nodeList) {
            List<Integer> integers = map.get(node.pos);
            if (integers == null) {
                continue;
            }
            for (int i : integers) {
                if (nodes[i] != null) {
                    continue;
                }
                Node newNode = new Node(i);
                newNode.to = node.pos;
                newNode.step = step;
                nodes[i] = newNode;
                newNodeList.add(newNode);
            }
        }
        if (newNodeList.size() == 0) {
            return;
        }
        stepList.add(newNodeList);
        buildStepMap(newNodeList, step);
    }


    static class Node {
        int pos = 0;
        int to = 0;
        long num = 1;
        int step = 0;

        Node(int pos) {
            this.pos = pos;
        }
    }
}


http://lihuaxi.xjx100.cn/news/1870792.html

相关文章

go - 计算CIDR的主机数量

在网络中&#xff0c;CIDR /32 表示该地址只能用作网络地址本身&#xff0c;不能分配给任何主机。因此&#xff0c;在计算主机数量时&#xff0c;应将 CIDR 地址按照其位掩码长度进行区分。对于 /32 子网掩码&#xff0c;主机数量总是为 1&#xff0c;而不是 -1。 以下是修正后…

【虚拟机磁盘扩容】 centos7把/dev/sda的磁盘空间分给根目录

一、修改硬盘大小 关闭虚拟机→设置→硬盘→修改到自己需要的磁盘大小 二、查看根目录当前磁盘使用情况统计 df -h 注&#xff1a;虽然在第1步已经设置过新的磁盘大小为50G&#xff0c;但是这里明显可以看出总磁盘大小依旧是之前的20G&#xff0c;这就涉及到分区问题。 三、…

ARM64安全特性之MTE

ARM64架构引入了MTE&#xff08;Memory Tagging Extension&#xff09;作为安全特性&#xff0c;用于增强内存访问的安全性。MTE使用内存标签来追踪和保护内存操作&#xff0c;以帮助检测和防御缓冲区溢出、使用-after-free等内存相关的安全漏洞。 MTE的核心思想是给每个内存地…

Linux服务器配置指南:网络、用户管理、共享服务及DNS配置详解

&#x1f482; 个人网站:【 海拥】【神级代码资源网站】【办公神器】&#x1f91f; 基于Web端打造的&#xff1a;&#x1f449;轻量化工具创作平台&#x1f485; 想寻找共同学习交流的小伙伴&#xff0c;请点击【全栈技术交流群】 1&#xff0e;Linux操作系统网络配置&#xff…

Spring Boot 容器如何根据注解加载发现与管理组件

这里写目录标题 0.一定先理解Java元注解&#xff0c;理解java反射 。1.是否可以把这些功能不同的注解理解为标识标记2.Java类被不同的注解标记后&#xff0c;当http请求时&#xff0c;Spring容器首先会寻找注释为Controller 不会去找注释为Component 后续可能需要再去查询 Comp…

java面试题汇总-目录

坚持记录和总结一些面试过程中遇到的面试题&#xff0c;以及总结出自己的回答技巧。不用死记硬背也能完整的回答出来。会持续更新&#xff0c;欢迎提出问题和疑问&#xff0c;大家一起总结经验。 1.Hashmap、Hashtable、ConcurrentHashMap原理 2.谈谈sql优化-mysql 3.ArrayList…

regex 简单使用

目录 基本用法 匹配结果 迭代器 替换 regex小试牛刀 &#xff0c;提取文件中所有https链接 std::regex 是 C11 引入的正则表达式库&#xff0c;它允许在字符串中进行模式匹配。正则表达式是一种强大的字符串匹配工具&#xff0c;允许你使用模式来描述你感兴趣的字符串集。…

隧道施工废水工艺设备需要哪些

隧道施工废水工艺设备是保障隧道施工过程中废水处理的关键装备。它们能够有效处理施工废水中的悬浮物、悬浮油、重金属等污染物&#xff0c;确保废水排放符合相关环保标准。以下是隧道施工废水工艺设备常见的几种类型&#xff1a; 1. 隧道施工废水沉淀池&#xff1a;沉淀池是废…