Leetcode每日一题学习训练——Python3版(最小化旅行的价格总和)

版本说明

当前版本号[20231206]。

版本修改说明
20231206初版

目录

文章目录

  • 版本说明
  • 目录
  • 最小化旅行的价格总和
    • 理解题目
    • 代码思路
    • 参考代码

原题可以点击此 2646. 最小化旅行的价格总和 前去练习。

最小化旅行的价格总和

现有一棵无向、无根的树,树中有 n 个节点,按从 0n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ,其中 edges[i] = [ai, bi] 表示树中节点 aibi 之间存在一条边。

每个节点都关联一个价格。给你一个整数数组 price ,其中 price[i] 是第 i 个节点的价格。

给定路径的 价格总和 是该路径上所有节点的价格之和。

另给你一个二维整数数组 trips ,其中 trips[i] = [starti, endi] 表示您从节点 starti 开始第 i 次旅行,并通过任何你喜欢的路径前往节点 endi

在执行第一次旅行之前,你可以选择一些 非相邻节点 并将价格减半。

返回执行所有旅行的最小价格总和。

示例 1:

img

输入:n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]
输出:23
解释:
上图表示将节点 2 视为根之后的树结构。第一个图表示初始树,第二个图表示选择节点 0 、2 和 3 并使其价格减半后的树。
第 1 次旅行,选择路径 [0,1,3] 。路径的价格总和为 1 + 2 + 3 = 6 。
第 2 次旅行,选择路径 [2,1] 。路径的价格总和为 2 + 5 = 7 。
第 3 次旅行,选择路径 [2,1,3] 。路径的价格总和为 5 + 2 + 3 = 10 。
所有旅行的价格总和为 6 + 7 + 10 = 23 。可以证明,23 是可以实现的最小答案。

示例 2:

img

输入:n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]]
输出:1
解释:
上图表示将节点 0 视为根之后的树结构。第一个图表示初始树,第二个图表示选择节点 0 并使其价格减半后的树。 
第 1 次旅行,选择路径 [0] 。路径的价格总和为 1 。 
所有旅行的价格总和为 1 。可以证明,1 是可以实现的最小答案。

提示:

  • 1 <= n <= 50
  • edges.length == n - 1
  • 0 <= ai, bi <= n - 1
  • edges 表示一棵有效的树
  • price.length == n
  • price[i] 是一个偶数
  • 1 <= price[i] <= 1000
  • 1 <= trips.length <= 100
  • 0 <= starti, endi <= n - 1

理解题目

首先需要构建一棵树,然后使用动态规划来计算每个节点作为根节点时的最小价格总和。

在计算过程中,可以选择一些非相邻节点并将价格减半。

简单来说就是:

  1. 构建树结构
  2. 初始化动态规划数组
  3. 遍历所有旅行,计算每个节点作为根节点时的最小价格总和
  4. 返回最小价格总和

代码思路

  1. 首先,根据给定的边信息构建一个邻接表来表示树结构。每个节点都有一个子节点列表,用于存储与该节点相连的其他节点。

    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:
            # 构建邻接表表示树结构
            children = [[] for _ in range(n)]
            for edge in edges:
                children[edge[0]].append(edge[1])
                children[edge[1]].append(edge[0])
    
  2. 然后,初始化一个计数器数组 count,用于记录每个节点在行程中出现的次数。

      # 初始化每个节点的计数器
            count = [0] * n
    
  3. 接下来,使用深度优先搜索(DFS)遍历树结构,计算从起点到终点的路径上的节点数量。在遍历过程中,如果到达终点节点,则将该节点的计数器加一。

     # 深度优先搜索,计算从起点到终点的路径上的节点数量
            def dfs(node: int, parent: int, end: int) -> bool:
                if node == end:
                    count[node] += 1
                    return True
                for child in children[node]:
                    if child == parent:
                        continue
                    if dfs(child, node, end):
                        count[node] += 1
                        return True
                return False
    
  4. 遍历所有行程,对于每个行程的起点和终点,调用 DFS 函数来计算从起点到终点的路径上的节点数量,并将结果累加到对应节点的计数器中。

    # 遍历所有行程,计算每个节点在行程中出现的次数
            for [x, y] in trips:
                dfs(x, -1, y)
    
  5. 最后,使用动态规划(DP)来计算每个节点作为根节点时的最小总价格。在 DP 函数中,首先计算当前节点作为根节点时的总价格,然后递归地计算其子节点作为根节点时的最小总价格,并根据题目要求进行选择。

      # 动态规划,计算每个节点作为根节点时的最小总价格
            def dp(node: int, parent: int) -> List[int]:
                res = [
                    price[node] * count[node], price[node] * count[node] // 2
                ]
                for child in children[node]:
                    if child == parent:
                        continue
                    [x, y] = dp(child, node)
                    # node 没有减半,因此可以取子树的两种情况的最小值
                    # node 减半,只能取子树没有减半的情况
                    res[0], res[1] = res[0] + min(x, y), res[1] + x
                return res
    
  6. 最终返回根节点为0时的最小总价格。

        # 返回根节点为0时的最小总价格
        return min(dp(0, -1))

参考代码

这段代码是一个解决旅行商问题(TSP)的算法,通过构建树结构、计算节点出现次数和使用动态规划来计算旅行商问题的最小总价格。

class Solution:
    def minimumTotalPrice(self, n: int, edges: List[List[int]], price: List[int], trips: List[List[int]]) -> int:
        children = [[] for _ in range(n)]
        for edge in edges:
            children[edge[0]].append(edge[1])
            children[edge[1]].append(edge[0])
        
        count = [0] * n
        def dfs(node: int, parent: int, end: int) -> bool:
            if node == end:
                count[node] += 1
                return True
            for child in children[node]:
                if child == parent:
                    continue
                if dfs(child, node, end):
                    count[node] += 1
                    return True
            return False
        
        for [x, y] in trips:
            dfs(x, -1, y)
        
        def dp(node: int, parent: int) -> List[int]:
            res = [
                price[node] * count[node], price[node] * count[node] // 2
            ]
            for child in children[node]:
                if child == parent:
                    continue
                [x, y] = dp(child, node)
                # node 没有减半,因此可以取子树的两种情况的最小值
                # node 减半,只能取子树没有减半的情况
                res[0], res[1] = res[0] + min(x, y), res[1] + x
            return res

        return min(dp(0, -1))

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

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

相关文章

【Spark学习笔记】- 5.1 IO基本实现原理

IO基本实现原理 Input& Output 字节流 InputStream in new FileInputStream("path") int i -1while ( (i in.read()) ! -1 ) {println(i); }上述为字节流 需要一个字节一个字节读取数据&#xff0c;读一个打印一个。功能可以实现&#xff0c;效率不高。 缓…

9_企业架构队列缓存中间件分布式Redis

企业架构队列缓存中间件分布式Redis 学习目标和内容 1、能够描述Redis作用及其业务适用场景 2、能够安装配置启动Redis 3、能够使用命令行客户端简单操作Redis 4、能够实现操作基本数据类型 5、能够理解描述Redis数据持久化机制 6、能够操作安装php的Redis扩展 7、能够操作实现…

AI跨界学习,不再是梦!

大家好&#xff01;今天给大家推荐的 GPTs 是【行业知识脉络】&#xff0c;帮助大家快速了解某个领域的脉络&#xff0c;并提供足够的学习资料和建议。 在AI时代&#xff0c;从小白到专家的1万小时定律即将失效&#xff0c;用少于1千小时掌握行业知识树和其核心概念是如何学习的…

内核无锁队列kfifo

文章目录 1、抛砖引玉2、内核无锁队列kfifo2.1 kfifo结构2.2 kfifo分配内存2.3 kfifo初始化2.4 kfifo释放2.5 kfifo入队列2.6 kfifo出队列2.7 kfifo的判空和判满2.8 关于内存屏障 1、抛砖引玉 昨天遇到这样一个问题&#xff0c;有多个生产者&#xff0c;多个消费者&#xff0c…

使用Java网络编程,窗口,线程,IO,内部类等实现多人在线聊天1.0

1.整体思路 思路图 整体思路如上: 涉及知识点:线程网络编程集合IO等 TCP 协议 2.代码实现过程 服务端 import javax.swing.*; import java.awt.*; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import java.awt.event.KeyAdapter; import jav…

SQL手工注入漏洞测试(Sql Server数据库)-墨者

———靶场专栏——— 声明&#xff1a;文章由作者weoptions学习或练习过程中的步骤及思路&#xff0c;非正式答案&#xff0c;仅供学习和参考。 靶场背景&#xff1a; 来源&#xff1a; 墨者学院 简介&#xff1a; 安全工程师"墨者"最近在练习SQL手工注入漏洞&#…

大模型应用设计的10个思考

技术不是万能的&#xff0c;但没有技术却可能是万万不能的&#xff0c;对于大模型可能也是如此。基于大模型的应用设计需要聚焦于所解决的问题&#xff0c;在自然语言处理领域&#xff0c;大模型本身在一定程度上只是将各种NLP任务统一成了sequence 到 sequence 的模型。利用大…

使用 Webshell 访问 SQL Server 主机并利用 SSRS

本文将指导您使用RDS SQL Server实例的主机账号登录和管理SQL Server Reporting Services&#xff08;SSRS&#xff09;数据库。 背景信息 RDS SQL Server提供Webshell功能&#xff0c;用户可以通过Web界面登录RDS SQL Server实例的操作系统。通过Webshell&#xff0c;用户可…

一次重新加载所有 maven 项目产生的 OOM

1、解决什么问题&#xff1f; 忘了截图了&#xff0c;用文字描述就是由于Reload All Maven Projects导致的 OOM 异常。 2、尝试与解决 2.1、尝试 2.1.1、尝试清理idea缓存&#xff08;无效&#xff09; 2.1.2、重启idea&#xff08;无效&#xff09; 2.1.3、重启电脑&am…

硬件连通性测试对象与实施过程

硬件连通性测试是一种系统性的测试方法&#xff0c;用于验证硬件设备之间的连接、通信和协作是否正常。这包括各种硬件组件&#xff0c;如计算机、网络设备、传感器、打印机等。测试的目的是确保硬件设备在其设计和运行环境中能够正确地交互和通信。 一、硬件连通性测试对象 网…

Slurm集群管理系统

Slurm集群管理系统 Slurm&#xff08;Simple Linux Utility for Resource Management&#xff0c;https://slurm.schedmd.com/&#xff09;是一个开源的、容错的、高度可扩展的集群管理和作业调度系统&#xff0c;适用于大型和小型高性能计算&#xff08;HPC&#xff09;集群。…

憋了个大招_群发版

大家好&#xff0c;我是良许。 憋了个大招&#xff0c;兄弟们&#xff01;我花了两个月的时间&#xff0c;搭建了一个自己的网站啦&#xff5e; 不卖关子&#xff0c;网站链接为&#xff1a; www.lxlinux.net/e/ 网站首页截图如下&#xff1a; 这个网站全部都是关于嵌入式及…

【JavaWeb学习笔记】6 - Tomcat

项目代码 零、在线文档 Apache Tomcat 8 (8.0.53) - Documentation Index WEB开发 1. WEB,在英语中web表示网/网络资源(页面&#xff0c;图片,css,js)意思&#xff0c;它用于表示WEB服务器(主机)供浏览器访问的资源 2. WEB服务器(主机)上供外界访问的Web资源分为: 静态web…

动手学习深度学习-跟李沐学AI-自学笔记(3)

一、深度学习硬件-CPU和GPU 芯片&#xff1a;Intel or AMD 内存&#xff1a;DDR4 显卡&#xff1a;nVidia 芯片可以和GPU与内存通信 GPU不能和内存通信 1. CPU 能算出每一秒能运算的浮点运算数&#xff08;大概0.15左右&#xff09; 1.1 提升CPU利用率 1.1.1 提升缓存…

Vite4、Vue3、Axios 针对请求模块化封装搭配自动化导入(简单易用)

针对请求模块化封装搭配自动化导入&#xff08;简单易用&#xff09; 目标目录目标代码前提步入正题src / utils / index.jssrc /api / index.jssrc /api / request.jssrc /api / service.jssrc /api / utils.jssrc /api / modules / demo.js 自动化配置vite.config.jseslint 校…

2023中医药国际传承传播大会暨中医药图片和非遗艺术展隆重揭幕

由世界针灸学会联合会、中新社国际传播集团、中国新闻图片网、中国民族医药学会、中国针灸学会联合主办的“2023中医药国际传承传播大会”3日在广东省深圳市举办&#xff0c;“中医药国际传承传播图片展”与“非遗艺术展”在大会举办期间开展迎客。会议聚焦非遗健康、非遗传承等…

案例049:基于微信小程序的校园外卖平台设计与实现

文末获取源码 开发语言&#xff1a;Java 框架&#xff1a;SSM JDK版本&#xff1a;JDK1.8 数据库&#xff1a;mysql 5.7 开发软件&#xff1a;eclipse/myeclipse/idea Maven包&#xff1a;Maven3.5.4 小程序框架&#xff1a;uniapp 小程序开发软件&#xff1a;HBuilder X 小程序…

【vue】点击导航菜单切换局部页面,打开展示默认栏目,页面刷新等问题

非专业前端&#xff0c;局限性较高&#xff0c;有些问题看起来很小&#xff0c;但是初次接触很棘手&#xff0c;需要查找很多博客&#xff0c;内容也很杂。以下只是过程中总结下来的&#xff0c;要解决的就是标题中的三个问题。 这是我需要达成的效果。 1.第一个是进入导航菜单…

LeetCode:2646. 最小化旅行的价格总和(dfs + 树形dp C++、Java)

目录 2646. 最小化旅行的价格总和 题目描述&#xff1a; 实现代码与解析&#xff1a; DFS DP 原理思路&#xff1a; 2646. 最小化旅行的价格总和 题目描述&#xff1a; 现有一棵无向、无根的树&#xff0c;树中有 n 个节点&#xff0c;按从 0 到 n - 1 编号。给你一个整数…

团队git操作流程

项目的开发要求&#xff1a;&#xff08;1&#xff09;项目组厉员代码提交不少于20次 &#xff08;2&#xff09;项目组厉员每天提交不少于20次 &#xff08;3&#xff09;企业项目开发代码的每天的提交一般提交3-5次 &#xff08;4&#xff09;代码仓库的管理 git的基础操作流…