代码随想录算法训练营第三十三天丨1005. K 次取反后最大化的数组和、134. 加油站、135. 分发糖果

本文主要是介绍代码随想录算法训练营第三十三天丨1005. K 次取反后最大化的数组和、134. 加油站、135. 分发糖果,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1005. K 次取反后最大化的数组和

两次贪心:

先按绝对值排序,第一次从大到小反转绝对值大的负值。如果数组都非负了k还有剩余,一直反转绝对值最小的值直到k为0。

class Solution:def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:nums.sort(key = abs, reverse = True)for i in range(len(nums)):if k == 0:breakelif nums[i] < 0:nums[i] *= -1k -= 1print(nums)if k > 0:nums[-1]  = (-1) ** k * nums[-1]return sum(nums) 

134. 加油站

我的思路:

我的想法是,计算两个数组的差值数组,元素表示的就是从i 到 i + 1剩余的油量。由于是环形路线,将diff数组扩展一倍,如果存在非负最大子数组,最大子数组的起始点就是结果。

class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:diffs = [gas[i] - cost[i] for i in range(len(gas))] * 2cur_max = global_max = diffs[0]i = 0for pos in range(1, len(diffs)):if cur_max < 0:i = poscur_max = diffs[pos]else:cur_max += diffs[pos]global_max = max(cur_max, global_max)return i if i < len(gas) else -1

优化:

实际上没有想到这道题的精髓,这道题不需要求最大子数组,大小什么的都无所谓,只要能是非负的就可以了。

首先要明确一点,如果总油量大于总消耗,一定从某点开始可以环绕一周,算法就是按照证明这一点设计的。如果总油量小于总消耗不能绕一周很好理解,那如何证明总油量不小于总消耗,一定可以环绕一周呢。

情况一:如果从0开始一直到n - 1一直是非负差值和,根据总油量不少于总消耗,说明从0开始就能绕一周,不需证明。

情况二:从0开始到i,在i处发现差值和为负,这说明从0到i总油量小于总消耗,从0到i任意一点开始无法到达i+1,但是整个环形线路总油量是大于总消耗的,说明假如从i + 1起步,i + 1到 n - 1之间,总油量是严格大于总消耗的,并且差值至少是之前累计的所有的负值。因此,把起始点移动到i + 1,继续累计差值,每次发现差值和为负,继续寻找下一个作为起点,直到某次ik + 1到 n - 1的差值和总为正,这说明从ik + 1不仅能到n - 1,还能弥补之前所有的负值和到达ik,因为总油量不小于总消耗,最终从ik能够到达ik + 1,ik + 1就是起点。

class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:start = curSum = totalSum = 0for i in range(len(gas)):curSum += gas[i] - cost[i]totalSum += gas[i] - cost[i]if curSum < 0:start = i + 1curSum = 0if totalSum < 0: return -1 return start

135. 分发糖果

一次从左向右遍历,确保每个孩子比他左边评分高的孩子获得更多的糖果;另一次从右向左遍历,确保每个孩子比他右边评分高的孩子获得更多的糖果。通过这两次遍历,可以保证所有孩子的糖果数既满足左边的条件,也满足右边的条件。

class Solution:def candy(self, ratings: List[int]) -> int:n = len(ratings)candies = [1] * n# 从左向右确保评分高的孩子比他左边的孩子获得更多的糖果for i in range(1, n):if ratings[i] > ratings[i - 1]:candies[i] = candies[i - 1] + 1# 从右向左确保评分高的孩子比他右边的孩子获得更多的糖果for i in range(n - 2, -1, -1):if ratings[i] > ratings[i + 1]:candies[i] = max(candies[i], candies[i + 1] + 1)# 计算总糖果数return sum(candies)

好难想到的。

这篇关于代码随想录算法训练营第三十三天丨1005. K 次取反后最大化的数组和、134. 加油站、135. 分发糖果的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面:本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN

Java实现自定义table宽高的示例代码

《Java实现自定义table宽高的示例代码》在桌面应用、管理系统乃至报表工具中,表格(JTable)作为最常用的数据展示组件,不仅承载对数据的增删改查,还需要配合布局与视觉需求,而JavaSwing... 目录一、项目背景详细介绍二、项目需求详细介绍三、相关技术详细介绍四、实现思路详细介绍五、完整实现代码

Go语言代码格式化的技巧分享

《Go语言代码格式化的技巧分享》在Go语言的开发过程中,代码格式化是一个看似细微却至关重要的环节,良好的代码格式化不仅能提升代码的可读性,还能促进团队协作,减少因代码风格差异引发的问题,Go在代码格式... 目录一、Go 语言代码格式化的重要性二、Go 语言代码格式化工具:gofmt 与 go fmt(一)

HTML5实现的移动端购物车自动结算功能示例代码

《HTML5实现的移动端购物车自动结算功能示例代码》本文介绍HTML5实现移动端购物车自动结算,通过WebStorage、事件监听、DOM操作等技术,确保实时更新与数据同步,优化性能及无障碍性,提升用... 目录1. 移动端购物车自动结算概述2. 数据存储与状态保存机制2.1 浏览器端的数据存储方式2.1.

基于 HTML5 Canvas 实现图片旋转与下载功能(完整代码展示)

《基于HTML5Canvas实现图片旋转与下载功能(完整代码展示)》本文将深入剖析一段基于HTML5Canvas的代码,该代码实现了图片的旋转(90度和180度)以及旋转后图片的下载... 目录一、引言二、html 结构分析三、css 样式分析四、JavaScript 功能实现一、引言在 Web 开发中,