网址注册了怎么做网站,开发网站找什么公司,丽水市企业网站建设 微信营销 影视拍摄,wordpress 主题 对比一、题目描述 二、解题思路
1.运动过程分析 这里需要一个油箱剩余油量的变量resGas#xff0c;初始化resGas0#xff1b;还需要一个标记从什么位置当做初始位置的startIdx#xff0c;初始化startIdx0。 我们从数组下标idx0处开始向后遍历#xff0c;初始时startIdx0#…一、题目描述 二、解题思路
1.运动过程分析 这里需要一个油箱剩余油量的变量resGas初始化resGas0还需要一个标记从什么位置当做初始位置的startIdx初始化startIdx0。 我们从数组下标idx0处开始向后遍历初始时startIdx0遇到下标为idx的加油站时看邮箱内此时剩余油量能否到达下一个油站 resGasresGasgas[i]-cost[i] 当resGas0时可以到达下一个油站 当resGas0时不可以到达下一个油站此时也意味着从startIdx开始运动到达不了idx位置从startIdx到idx之间的所有位置也同样不可达idx。此时把startIdx设置为idx1。 这里用startIdx-idx小车运动不可达的图示解释一下上面标注黄色部分 2.可以循环的条件判断 这里需要注意的是小车从startIdx-加油站数组末尾时如果可达需要将idx(idx1)%gas.length如果整个过程一直可达等到二次循环idx1startidx时意味着从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开始寻找设置油箱剩余量resGasint lengas.length;int startidx0,residx0;int resGas0;//初始时油箱剩余油量为0int nowidx0;boolean newloopfalse;while(nowidxlen){int nowGasresGasgas[nowidx]-cost[nowidx];if(nowidx1len){newlooptrue;}if(nowGas0){//表示从startidx开始到达不了startidx(nowidx1)%len;resGas0;if(newloop){residx-1;break;}}else{//表示当前油量还可以支撑往后走resGasnowGas;if(newloop((nowidx1)%lenstartidx)){residxstartidx;break;}}nowidx(nowidx1)%len;}return residx;}
}
四、刷题链接
加油站_牛客题霸_牛客网
