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

LeetCode134☞加油站

关联LeetCode题号134

本题特点
  • 贪心
  • 局部最优解-部分差值 如果小于0(消耗大于油站油量) 就从下一个加油站开始,因为如果中间有小于0的情况 当前站就不可能是始发站,
  • 整体最优解-整体差值 如果小于0 ,那么就是不能有始发站
本题思路
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        curSum = 0
        totalSum = 0
        start = 0
        
        for i in range(len(gas)):
            curSum += gas[i] - cost[i]
            totalSum += gas[i] - cost[i]
            
            if curSum < 0:
                start = i + 1
                curSum = 0
        
        if totalSum < 0:
            return -1
        return start
java写法
package leetcode;

import org.junit.jupiter.api.Test;

/**
 * File Description: gasStation_134
 * Author: Your Name
 * Date: 2024/12/24
 */
public class gasStation_134 {

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int curSum = 0;
        int totalSum = 0;
        int start = 0;
        for (int i = 0; i < gas.length; i++){
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if(curSum < 0){
                start = i + 1;
                curSum = 0;
            }
        }
        if (totalSum < 0){
            return -1;
        }
        return start;

    }

    @Test
    public void TestCanCompleteCircuit() {
        int[] gas = {2,3,4};
        int[] cost = {3,4,3};
        int start = canCompleteCircuit(gas, cost);
        System.out.println(start);
    }

}

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

相关文章:

  • 【农业大数据处理与应用】实验二 随机森林算法与LSTM循环神经网络
  • 来客推商城V3多用户uni-app商城源码怎么样?
  • Spark DataFrame、Dataset 和 SQL 解析原理深入解析(万字长文多张原理图)
  • 嵌入式Linux | 什么是 BootLoader、Linux 内核(kernel)、和文件系统?
  • 对最近的刷题做一个小总结(关于动态规划和贪心)
  • LVDS(Low Voltage Differential Signaling)电平详解
  • 【每日学点HarmonyOS Next知识】上下拉列表、停止无限循环动画、页面列表跟随列表滑动、otf字体、日期选择
  • Linux目录理解
  • 海外红人营销助力游戏出海:从单一营销到生态构建的转变
  • uniapp APP权限弹框
  • 图论——广度优先搜索实现
  • golang-嵌套结构体
  • Python----计算机视觉处理(Opencv:ROI图像切割)
  • 基于FPGA的3U机箱轨道交通网络通讯板,对内和主控板、各类IO板通信,对外可进行RS485、CAN或MVB组网通信
  • 结构型模式之组合模式:让对象构成树形结构
  • 数据结构——双向链表dlist
  • 360安全软件拦截鼠标键盘模拟操作的解决方法
  • 【CPU】CPU多级缓存和MESI一致性协议
  • C# 封装数据 详解
  • Prompt Learning Awesome