当前位置: 首页 > article >正文

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

http://www.kler.cn/a/586759.html

相关文章:

  • 开发、科研、日常办公工具汇总(自用,持续更新)
  • MATLAB中events函数用法
  • Linux系统之美:进程初识
  • 蓝桥杯 阶乘求值【省模拟赛】
  • 谷歌Chrome或微软Edge浏览器修改网页任意内容
  • C++笔记-类与对象(中)
  • 二分+前缀和/滑动窗口——成绩统计
  • 神经网络:定义与核心原理
  • 基于 Verilog 的多路复用显示驱动设计与测试:实践与探索
  • Visual Studio里的调试(debugging)功能介绍
  • Tomato靶机
  • Vue 中的 v-for 如何遍历对象?
  • 【模拟算法】
  • misc19~21
  • 如何在AVL树中高效插入并保持平衡:一步步掌握旋转与平衡因子 —— 旋转篇
  • ​​​​​​​大语言模型安全风险分析及相关解决方案
  • P3379 【模板】最近公共祖先(LCA)【题解】(倍增法)
  • 链表·简单归并
  • OpenBMC:BmcWeb添加路由3 设置权限
  • 机器学习 Day05 pandas库