下载ppt模板免费的网站,制作个网站,宿迁房产网信息网,怎么修改网站后台路径在一条环路上有 n 个加油站#xff0c;其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车#xff0c;从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发#xff0c;开始时油箱为空。
给定两个整数数组 gas 和 cost 其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发开始时油箱为空。
给定两个整数数组 gas 和 cost 如果你可以按顺序绕环路行驶一周则返回出发时加油站的编号否则返回 -1 。如果存在解则 保证 它是 唯一 的。 示例 1:
输入: gas [1,2,3,4,5], cost [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发可获得 4 升汽油。此时油箱有 0 4 4 升汽油
开往 4 号加油站此时油箱有 4 - 1 5 8 升汽油
开往 0 号加油站此时油箱有 8 - 2 1 7 升汽油
开往 1 号加油站此时油箱有 7 - 3 2 6 升汽油
开往 2 号加油站此时油箱有 6 - 4 3 5 升汽油
开往 3 号加油站你需要消耗 5 升汽油正好足够你返回到 3 号加油站。
因此3 可为起始索引。
示例 2:
输入: gas [2,3,4], cost [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发可以获得 4 升汽油。 此时油箱有 0 4 4 升汽油
开往 0 号加油站此时油箱有 4 - 3 2 3 升汽油
开往 1 号加油站此时油箱有 3 - 3 3 3 升汽油
你无法返回 2 号加油站因为返程需要消耗 4 升汽油但是你的油箱只有 3 升汽油。
因此无论怎样你都不可能绕环路行驶一周。 提示:
gas.length ncost.length n1 n 1050 gas[i], cost[i] 104 我这个代码里解的题比Leetcode134更复杂一些
package dataStructure.slideWindow;import java.util.LinkedList;/*** 原题目https://leetcode.cn/problems/gas-station/* 在一条环路上有 n个加油站其中第 i个加油站有汽油gas[i]升。** 你有一辆油箱容量无限的的汽车从第 i 个加油站开往第 i1个加油站需要消耗汽油cost[i]升。你从其中的一个加油站出发开始时油箱为空。** 给定两个整数数组 gas 和 cost 如果你可以绕环路行驶一周则返回出发时加油站的编号否则返回 -1 。如果存在解则 保证 它是 唯一 的。**/
public class CanCompleteCircuit_Leecode131 {/*** 这个题是一个简化的题我们定义一个方法求出复杂问题返回所有的点能不能回到原点* param gas* param cost* return*/public static boolean[] canCompleteCircuitComplex(int[] gas, int[] cost) {if(gas null || cost null || gas.length ! cost.length || gas.length 0) {return null;}//数组长度int N gas.length;//结果数组result[i]表示第i个加油站能不能走完回到i位置所以一共是N个点boolean[] result new boolean[N];//这个数组表示每个加油站的汽油的量和他到下一个点需要消耗的汽油的差值int[] gap new int[N];for(int i 0; i N; i) {gap[i] gas[i] - cost[i];}//前缀和数组代表gap数组的前缀和因为我们每次要计算从i开始的N个加油站所以使用两倍长度比如计算5加油站的时候是preSum 5-11的位置中找最小值int[] preSum new int[2 * N];//数组的初始化的过程,0位置前面没有数所以preSum[0] gap[0]preSum[0] gap[0];//1位置开始preSum[i] preSum[i - 1] gap[i % N]for(int i 1; i 2 * N; i) {preSum[i] preSum[i - 1] gap[i % N];}//最小值窗口存放当前窗口内的最小值窗口内从first到last从小到大排列LinkedListInteger minWindow new LinkedList();int L 0;int R 0;//L从0到N-1这里也可以写成for(L 0; L N ; L)while(L N) {//R是窗口的右边界因为窗口是固定大小N所以R最大只能到L N这个同时也保证不会越界while(R L N) {//每次都是把R位置放入窗口放入之前如果当前窗口内有比当前数大的依次弹出while(!minWindow.isEmpty() preSum[minWindow.peekLast()] preSum[R]) {minWindow.pollLast();}minWindow.addLast(R);R ;}//当前L位置的窗口已经确定first位置就是当前窗口的最小值L 0的时候不需要最任何计算, preSum[minWindow.peekFirst()]就是当前窗口内最薄弱的点//如果L不等于0则需要减去L-1位置的前缀和//minValue代表当前窗口内最薄弱也就是最可能出现到不了下一个的点int minValue L 0 ? preSum[minWindow.peekFirst()] : preSum[minWindow.peekFirst()] - preSum[L - 1];if(minWindow.peekFirst() L) {minWindow.pollFirst();}//如果连最可能出现到不了下一个加油站的点最薄弱的点都大于等于0则所有的其他都肯定没有问题if(minValue 0) result[L] true;L ;}return result;}/*** Leecode原题比较简单* param gas* param cost* return*/public static int canCompleteCircuit(int[] gas, int[] cost) {boolean[] result canCompleteCircuitComplex(gas, cost);int ret -1;for (int i 0; i result.length; i) {if(result[i]) {ret i;break;}}return ret;}public static void main(String[] args) {int[] gas {1,1,6,4,7,2};int[] cost {3,4,2,6,1,3};//canCompleteCircuitComplex(gas, cost);System.out.println(canCompleteCircuit(gas, cost));}
}
