2025-3-14 leetcode刷题情况(贪心算法)
一、53.最大子序和
1.题目描述
2.代码
3.思路
先特殊处理数组只有一个数的情况,再定义两个变量,sum用于记录最大子数组和,count
用于记录当前连续子数组的和。使用for
循环遍历数组nums
中的每个元素。对于每个元素nums[i]
,将其累加到count
中。每次累加后,使用Math.max
函数比较sum
和count
的大小,将较大值更新到sum
中,确保sum
始终记录最大子数组和。如果count
小于等于 0,说明当前连续子数组的和为负数或 0,继续往后累加这个子数组不会得到更大的和,因此将count
重置为 0,重新开始计算新的连续子数组和。遍历结束后,sum
中存储的就是最大子数组和,将其返回。
二、134.加油站
1.题目描述
2.代码
3.思路
- 变量初始化:
curSum
:用于记录从当前起始加油站出发,到当前遍历到的加油站时,剩余的汽油量。初始化为 0。totalSum
:用于记录整个环形路线中,汽油总量与消耗总量的差值。初始化为 0。index
:用于记录可能的起始加油站的索引,初始化为 0。
- 遍历加油站:
- 使用
for
循环遍历每个加油站,索引为i
。 - 对于每个加油站,计算在该加油站补充汽油并前往下一个加油站后的剩余汽油量,即
gas[i] - cost[i]
,将其累加到curSum
和totalSum
中。 - 如果
curSum
小于 0,说明从当前起始加油站出发无法到达当前加油站,需要更换起始加油站。将起始加油站的索引更新为(i + 1) % gas.length
,并将curSum
重置为 0,重新开始计算剩余汽油量。
- 使用
- 判断是否能完成一圈行驶:
- 遍历结束后,检查
totalSum
的值。如果totalSum
小于 0,说明整个环形路线上的汽油总量小于消耗总量,无论从哪个加油站出发都无法完成一圈行驶,返回 -1。 - 如果
totalSum
大于等于 0,说明存在可以完成一圈行驶的起始加油站,返回index
。
- 遍历结束后,检查