欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 房产 > 家装 > 2025-3-14 leetcode刷题情况(贪心算法)

2025-3-14 leetcode刷题情况(贪心算法)

2025/3/17 1:52:07 来源:https://blog.csdn.net/2201_75583057/article/details/146258649  浏览:    关键词:2025-3-14 leetcode刷题情况(贪心算法)

一、53.最大子序和

1.题目描述

2.代码

3.思路

先特殊处理数组只有一个数的情况,再定义两个变量,sum用于记录最大子数组和,count用于记录当前连续子数组的和。使用for循环遍历数组nums中的每个元素。对于每个元素nums[i],将其累加到count中。每次累加后,使用Math.max函数比较sumcount的大小,将较大值更新到sum中,确保sum始终记录最大子数组和。如果count小于等于 0,说明当前连续子数组的和为负数或 0,继续往后累加这个子数组不会得到更大的和,因此将count重置为 0,重新开始计算新的连续子数组和。遍历结束后,sum中存储的就是最大子数组和,将其返回。

二、134.加油站

1.题目描述

2.代码

3.思路

  1. 变量初始化
    • curSum:用于记录从当前起始加油站出发,到当前遍历到的加油站时,剩余的汽油量。初始化为 0。
    • totalSum:用于记录整个环形路线中,汽油总量与消耗总量的差值。初始化为 0。
    • index:用于记录可能的起始加油站的索引,初始化为 0。
  2. 遍历加油站
    • 使用 for 循环遍历每个加油站,索引为 i
    • 对于每个加油站,计算在该加油站补充汽油并前往下一个加油站后的剩余汽油量,即 gas[i] - cost[i],将其累加到 curSum 和 totalSum 中。
    • 如果 curSum 小于 0,说明从当前起始加油站出发无法到达当前加油站,需要更换起始加油站。将起始加油站的索引更新为 (i + 1) % gas.length,并将 curSum 重置为 0,重新开始计算剩余汽油量。
  3. 判断是否能完成一圈行驶
    • 遍历结束后,检查 totalSum 的值。如果 totalSum 小于 0,说明整个环形路线上的汽油总量小于消耗总量,无论从哪个加油站出发都无法完成一圈行驶,返回 -1。
    • 如果 totalSum 大于等于 0,说明存在可以完成一圈行驶的起始加油站,返回 index

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词