贪心算法-加油站

一、题目描述

二、解题思路

1.运动过程分析

        这里需要一个油箱剩余油量的变量resGas,初始化resGas=0;还需要一个标记从什么位置当做初始位置的startIdx,初始化startIdx=0。

        我们从数组下标idx=0处开始向后遍历,初始时startIdx=0,遇到下标为idx的加油站时,看邮箱内此时剩余油量能否到达下一个油站:

        resGas=resGas+gas[i]-cost[i]

        当resGas>=0时,可以到达下一个油站;

        当resGas<0时,不可以到达下一个油站,此时也意味着从startIdx开始运动到达不了idx位置,从startIdx到idx之间的所有位置也同样不可达idx此时把startIdx设置为idx+1。

        这里用startIdx->idx小车运动不可达的图示解释一下上面标注黄色部分:

2.可以循环的条件判断

        这里需要注意的是,小车从startIdx->加油站数组末尾时,如果可达,需要将idx=(idx+1)%gas.length,如果整个过程一直可达,等到二次循环idx+1==startidx时,意味着从startIdx开始行驶一定可以循环一周,返回startIdx。所以我们还要添加一个变量标注一下此时是否已经二次循环,实现代码内用newloop来标识

3.不可以循环的条件判断

        不存在循环一周的情况:当二次循环过程中还是出现了不可达的情况,那么就意味着不存在循环的情况,返回-1,图示:

        就意味着从startIdx到末尾之间的元素和下标0到下标3之间的所有元素下标3都不可达,此前已经确定了从下标0到下标4之间的元素已经不可达,所以肯定不能形成循环。

        整个过程需要执行两次数组遍历,所以时间复杂度为O(n),效率还是可以的。

三、代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param gas int整型一维数组 
     * @param cost int整型一维数组 
     * @return int整型
     */
    public int gasStation (int[] gas, int[] cost) {
        // 就从0开始寻找,设置油箱剩余量resGas,
        int len=gas.length;
        int startidx=0,residx=0;
        int resGas=0;//初始时油箱剩余油量为0
        int nowidx=0;
        boolean newloop=false;
        while(nowidx<len){
            int nowGas=resGas+gas[nowidx]-cost[nowidx];
            if(nowidx+1==len){
                newloop=true;
            }
            if(nowGas<0){//表示从startidx开始到达不了
                startidx=(nowidx+1)%len;
                resGas=0;
                if(newloop){
                    residx=-1;
                    break;
                }
            }else{//表示当前油量还可以支撑往后走
                resGas=nowGas;
                if(newloop&&((nowidx+1)%len==startidx)){
                    residx=startidx;
                    break;
                }
            }
            nowidx=(nowidx+1)%len;
        }
        return residx;
    }
}

四、刷题链接

加油站_牛客题霸_牛客网

相关推荐

最近更新

  1. 浔川画板v5.0——浔川python科技社

    2024-06-09 13:30:03       0 阅读
  2. C# —— for循环语句

    2024-06-09 13:30:03       0 阅读
  3. 鸿蒙开发:【启动本地PageAbility】

    2024-06-09 13:30:03       0 阅读
  4. 地学类期刊最新CiteScore™ 汇总

    2024-06-09 13:30:03       0 阅读
  5. 怎么通过AI构架一个个人简介并且写出来

    2024-06-09 13:30:03       0 阅读

热门阅读

  1. 深入了解Git:从数据模型到集成IDEA

    2024-06-09 13:30:03       5 阅读
  2. C语言---深入指针(4)

    2024-06-09 13:30:03       4 阅读
  3. 回溯之分割回文串

    2024-06-09 13:30:03       7 阅读
  4. 【环境搭建】2.阿里云ECS服务器 安装MySQL

    2024-06-09 13:30:03       4 阅读
  5. 2 程序的灵魂—算法-2.2 简单算法举例-【例 2.5】

    2024-06-09 13:30:03       5 阅读
  6. 【小海实习日记】金融-现货以及合约理解

    2024-06-09 13:30:03       7 阅读
  7. 【Qt】Item Views与Item Widgets的区别

    2024-06-09 13:30:03       5 阅读
  8. qt自定义事件过滤器

    2024-06-09 13:30:03       5 阅读
  9. liunx查看日志

    2024-06-09 13:30:03       6 阅读
  10. FPGA复位:(43)复位高扇出的解决方案?

    2024-06-09 13:30:03       5 阅读
  11. vue3模板语法总结

    2024-06-09 13:30:03       4 阅读