Leetcode每日一题学习训练——Python3版(到达首都的最少油耗)

2023-12-05 21:28

本文主要是介绍Leetcode每日一题学习训练——Python3版(到达首都的最少油耗),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

版本说明

当前版本号[20231205]。

版本修改说明
20231205初版

目录

文章目录

  • 版本说明
  • 目录
  • 到达首都的最少油耗
    • 理解题目
    • 代码思路
    • 参考代码

原题可以点击此 2477. 到达首都的最少油耗 前去练习。

到达首都的最少油耗

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

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

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

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

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

示例 1:

img

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

示例 2:

img

输入: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:

img

输入: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. 这个问题可以使用图的广度优先搜索(BFS)算法来解决。
  2. 广度优先搜索(BFS)算法是一种用于遍历或搜索树或图的算法。它从根节点开始,然后访问所有相邻的节点,然后再访问这些相邻节点的相邻节点,依此类推。
  3. 首先,我们需要创建一个邻接表来表示城市之间的道路关系。
  4. 然后,从首都开始进行BFS搜索,每次搜索时,将当前城市的汽油消耗累加到总油耗中,并更新每个城市的汽油消耗。
  5. 最后,返回到达首都的总油耗。

代码思路

  1. 它包含一个名为minimumFuelCost的方法,该方法接受两个参数:roads和seats。**roads是一个二维列表,表示城市之间的道路关系;seats是一个整数,表示每辆车的座位数。**方法的目的是计算到达首都所需的最少汽油量。

    ​ (该函数:minimumFuelCost是函数名;

    self是类实例的引用,表示这个函数是一个类的方法;

    (self, roads: List[List[int]], seats: int)是函数的参数列表,包括两个参数:

    ​ 一个是roads,类型为List[List[int]],表示一个二维整数列表

    ​ 另一个是seats,类型为int,表示一个整数。

    -> int表示这个函数的返回值类型是整数。)

     def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
    
  2. 首先,代码创建了一个名为g的空列表,用于存储道路关系。然后,遍历roads列表,将每个城市的邻居添加到g中。

    [[] for i in range(len(roads) + 1)]表示创建一个长度为len(roads) + 1的列表;

    ​ 其中每个元素都是一个空列表。

    ​ 这样做的目的是为了让每个节点都有一个与之对应的邻接表,

    ​ 方便后续进行图的遍历和操作。)

       # 创建一个空的邻接表g,用于存储道路关系g = [[] for i in range(len(roads) + 1)]for e in roads:# 将道路的两个端点添加到对方的邻接表中g[e[0]].append(e[1])g[e[1]].append(e[0])res = 0  # 初始化结果变量为0
    
  3. 接下来,定义了一个名为dfs的内部函数,用于深度优先搜索。这个函数接受两个参数:**cur表示当前城市,fa表示当前城市的父节点。**在dfs函数中,首先初始化一个名为peopleSum的变量,表示当前城市及其代表的人数之和。

            def dfs(cur, fa):nonlocal res  # 声明res为非局部变量,以便在dfs函数中修改它peopleSum = 1  # 初始化当前节点的人数为1
    
  4. 然后,遍历当前城市的代表,如果代表不是父节点,则递归调用dfs函数,并将返回的人数累加到peopleSum中。同时,更新res变量,将其加上(peopleCnt + seats - 1) // seats的结果。最后,返回peopleSum。

     for ne in g[cur]:  # 遍历当前节点的所有代表if ne != fa:  # 如果代表不是父节点peopleCnt = dfs(ne, cur)  # 递归调用dfs函数,计算代表的人数peopleSum += peopleCnt  # 累加代表的人数到当前节点的人数res += (peopleCnt + seats - 1) // seats  # 更新结果变量,计算所需的汽油量return peopleSum  # 返回当前节点的人数
    
  5. 在主函数中,调用dfs函数,传入初始值0和-1。最后,返回res作为结果。

         dfs(0, -1)  # 从根节点开始调用dfs函数return res  # 返回结果变量

参考代码

class Solution:def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:g = [[] for i in range(len(roads) + 1)]for e in roads:g[e[0]].append(e[1])g[e[1]].append(e[0])res = 0def dfs(cur, fa):nonlocal respeopleSum = 1 for ne in g[cur]:if ne != fa:peopleCnt = dfs(ne, cur)peopleSum += peopleCntres += (peopleCnt + seats - 1) // seatsreturn peopleSumdfs(0, -1)return res

这篇关于Leetcode每日一题学习训练——Python3版(到达首都的最少油耗)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/459206

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

引言 高斯过程(Gaussian Process,简称GP)是一种概率模型,用于描述一组随机变量的联合概率分布,其中任何一个有限维度的子集都具有高斯分布 文章目录 引言一、高斯过程1.1 基本定义1.1.1 随机过程1.1.2 高斯分布 1.2 高斯过程的特性1.2.1 联合高斯性1.2.2 均值函数1.2.3 协方差函数(或核函数) 1.3 核函数1.4 高斯过程回归(Gauss

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络(1)sklearn

系列文章目录 监督学习:参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归(SAheart.csv) 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

线性代数|机器学习-P36在图中找聚类

文章目录 1. 常见图结构2. 谱聚类 感觉后面几节课的内容跨越太大,需要补充太多的知识点,教授讲得内容跨越较大,一般一节课的内容是书本上的一章节内容,所以看视频比较吃力,需要先预习课本内容后才能够很好的理解教授讲解的知识点。 1. 常见图结构 假设我们有如下图结构: Adjacency Matrix:行和列表示的是节点的位置,A[i,j]表示的第 i 个节点和第 j 个