LeetCode:1402. 做菜顺序、2316. 统计无向图中无法互相到达点对数

本文主要是介绍LeetCode:1402. 做菜顺序、2316. 统计无向图中无法互相到达点对数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1. 1402 做菜顺序

题目详细为:

一个厨师收集了他 n 道菜的满意程度 satisfaction ,这个厨师做出每道菜的时间都是 1 单位时间。
一道菜的 「 like-time 系数 」定义为烹饪这道菜结束的时间(包含之前每道菜所花费的时间)乘以这道菜的满意程度,也就是 time[i]*satisfaction[i] 。
返回厨师在准备了一定数量的菜肴后可以获得的最大 like-time 系数 总和。
你可以按 任意 顺序安排做菜的顺序,你也可以选择放弃做某些菜来获得更大的总和。

示例为:

示例 1:
输入:satisfaction = [-1,-8,0,5,-9]
输出:14
解释:去掉第二道和最后一道菜,最大的 like-time 系数和为 (-11 + 02 + 53 = 14) 。每道菜都需要花费 1 单位时间完成。
示例 2:
输入:satisfaction = [4,3,2]
输出:20
解释:可以按照任意顺序做菜 (2
1 + 32 + 43 = 20)
示例 3:
输入:satisfaction = [-1,-4,-5]
输出:0
解释:大家都不喜欢这些菜,所以不做任何菜就可以获得最大的 like-time 系数。

提示:

n == satisfaction.length
1 <= n <= 500
-1000 <= satisfaction[i] <= 1000

难度:【困难

算法思路:
由于n的取值并没有很大,所以使用暴力解法解决这题完全没有问题,但是个人觉得可以这样来实现。
可以分为三类情况,(1)satisfaction这个数组(列表)中的最大数小于零,这样得到最终结果(按照上述公式)肯定小于0,那么直接返回0即可;(2)satisfaction这个数组(列表)中的最小数大于零,对这个数组进行升序排序,然后利用上述公式计算返回即可;(3)satisfaction这个数组(列表)中同时存在小于0和大于0的数,首先对这个数组进行升序排序,然后用一个变量根据上述公式计算对应结果num2,用变量num存储数组的和,之后再遍历这个数组,变量ans(初始值为0)返回最终结果,执行下述操作即可,ans = max(ans,num2),num2 -= num,num -= satisfaction[i],示意图如下:


satisfaction数组
排序前  [-1,-8,0,5,-9]
排序后 [-9,-8,-1,0,5]
num的值为:-13
num2的值为:-9 * 1 + -8 * 2 + -1 * 3 + 0 * 4 + 5 * 5 =  -3
ans = 0
遍历次数 ans num num2
1 0 -13 -3
2 0 -4 10
3 10 4 14
4 14 5 10
5 14 5 5

参考代码如下:

class Solution(object):def maxSatisfaction(self, satisfaction):""":type satisfaction: List[int]:rtype: int"""satisfaction.sort()if satisfaction[-1] < 0:return 0ans = 0n = len(satisfaction)if satisfaction[0] > 0:start = 1for e in satisfaction:ans += start * estart += 1else:num = sum(satisfaction)num2 = 0for i in range(n):num2 += satisfaction[i] * (i+1)for i in range(n):ans = max(ans,num2)num2 -= numnum -= satisfaction[i]return ansa = Solution()
print(a.maxSatisfaction(satisfaction = [-1,-8,0,5,-9]))

运行结果:
请添加图片描述
虽然算法效率总体还不怎么的,但是比暴力肯定要好一些。

2. 2316. 统计无向图中无法互相到达点对数

题目详细为:

给你一个整数 n ,表示一张 无向图 中有 n 个节点,编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ,其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。
请你返回 无法互相到达 的不同 点对数目 。

示例为:

在这里插入图片描述
输入:n = 3, edges = [[0,1],[0,2],[1,2]]
输出:0
解释:所有点都能互相到达,意味着没有点对无法互相到达,所以我们返回 0 。
2.
在这里插入图片描述
输入:n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
输出:14
解释:总共有 14 个点对互相无法到达:
[[0,1],[0,3],[0,6],[1,2],[1,3],[1,4],[1,5],[2,3],[2,6],[3,4],[3,5],[3,6],[4,6],[5,6]]
所以我们返回 14 。

提示:

提示:
1 <= n <= 105
0 <= edges.length <= 2 * 105
edges[i].length == 2
0 <= ai, bi < n
ai != bi
不会有重复边。

算法思路:
从0号节点依次遍历到n-1号节点,如果遍历到某节点时,在map中已经存在了,那么不需要再进行接下来的操作,否则,在map中记录当前节点,然后依次遍历与该节点连通的节点,继续上述操作,直到遍历完某节点所有连通的节点,此时map中存储的节点个数减去pre(初始为0),即可得到一组不为0数,用一个数组arr存储,直到所有节点全部遍历完,然后计算arr中的数即可得到最终结果。但是有问题遍历arr需要两层,应该提交不了,为此直接在遍历节点的同时计算最终结果(但是最终还是差几个用例没有通过,最后参考官方代码改进才通过)。

参考代码为:

class Solution(object):def countPairs(self, n, edges):""":type n: int:type edges: List[List[int]]:rtype: int"""map = {}for e in range(n):map[e] = []for key,value in edges:map[key].append(value)map[value].append(key)map2 = {}def dfs(cur_node):map2[cur_node] = 1arr = map[cur_node]count = 1for e in arr:if not map2.get(e,None):count += dfs(e)return countans = 0pre = 0for i in range(n):if not map2.get(i,None):count = dfs(i)ans += pre * countpre += countreturn ans

运行结果:
请添加图片描述

这篇关于LeetCode:1402. 做菜顺序、2316. 统计无向图中无法互相到达点对数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

SQL Server配置管理器无法打开的四种解决方法

《SQLServer配置管理器无法打开的四种解决方法》本文总结了SQLServer配置管理器无法打开的四种解决方法,文中通过图文示例介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录方法一:桌面图标进入方法二:运行窗口进入检查版本号对照表php方法三:查找文件路径方法四:检查 S

在Linux终端中统计非二进制文件行数的实现方法

《在Linux终端中统计非二进制文件行数的实现方法》在Linux系统中,有时需要统计非二进制文件(如CSV、TXT文件)的行数,而不希望手动打开文件进行查看,例如,在处理大型日志文件、数据文件时,了解... 目录在linux终端中统计非二进制文件的行数技术背景实现步骤1. 使用wc命令2. 使用grep命令

Python中Tensorflow无法调用GPU问题的解决方法

《Python中Tensorflow无法调用GPU问题的解决方法》文章详解如何解决TensorFlow在Windows无法识别GPU的问题,需降级至2.10版本,安装匹配CUDA11.2和cuDNN... 当用以下代码查看GPU数量时,gpuspython返回的是一个空列表,说明tensorflow没有找到

Spring如何使用注解@DependsOn控制Bean加载顺序

《Spring如何使用注解@DependsOn控制Bean加载顺序》:本文主要介绍Spring如何使用注解@DependsOn控制Bean加载顺序,具有很好的参考价值,希望对大家有所帮助,如有错误... 目录1.javascript 前言2. 代码实现总结1. 前言默认情况下,Spring加载Bean的顺

Oracle修改端口号之后无法启动的解决方案

《Oracle修改端口号之后无法启动的解决方案》Oracle数据库更改端口后出现监听器无法启动的问题确实较为常见,但并非必然发生,这一问题通常源于​​配置错误或环境冲突​​,而非端口修改本身,以下是系... 目录一、问题根源分析​​​二、保姆级解决方案​​​​步骤1:修正监听器配置文件 (listener.

MySQL版本问题导致项目无法启动问题的解决方案

《MySQL版本问题导致项目无法启动问题的解决方案》本文记录了一次因MySQL版本不一致导致项目启动失败的经历,详细解析了连接错误的原因,并提供了两种解决方案:调整连接字符串禁用SSL或统一MySQL... 目录本地项目启动报错报错原因:解决方案第一个:第二种:容器启动mysql的坑两种修改时区的方法:本地

Java中JSON格式反序列化为Map且保证存取顺序一致的问题

《Java中JSON格式反序列化为Map且保证存取顺序一致的问题》:本文主要介绍Java中JSON格式反序列化为Map且保证存取顺序一致的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未... 目录背景问题解决方法总结背景做项目涉及两个微服务之间传数据时,需要提供方将Map类型的数据序列化为co

VS配置好Qt环境之后但无法打开ui界面的问题解决

《VS配置好Qt环境之后但无法打开ui界面的问题解决》本文主要介绍了VS配置好Qt环境之后但无法打开ui界面的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要... 目UKeLvb录找到Qt安装目录中designer.UKeLvBexe的路径找到vs中的解决方案资源

详解如何使用Python从零开始构建文本统计模型

《详解如何使用Python从零开始构建文本统计模型》在自然语言处理领域,词汇表构建是文本预处理的关键环节,本文通过Python代码实践,演示如何从原始文本中提取多尺度特征,并通过动态调整机制构建更精确... 目录一、项目背景与核心思想二、核心代码解析1. 数据加载与预处理2. 多尺度字符统计3. 统计结果可

如何解决yum无法安装epel-release的问题

《如何解决yum无法安装epel-release的问题》:本文主要介绍如何解决yum无法安装epel-release的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录yum无法安装epel-release尝试了第一种方法第二种方法(我就是用这种方法解决的)总结yum