在一条环路上有 n 个加油站,其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。
给定两个整数数组 gas 和 cost ,如果你可以绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1 。如果存在解,则 保证 它是 唯一 的。
https://leetcode.cn/problems/gas-station/
/** Copyright (c) Huawei Technologies Co., Ltd. 2023-2023. All rights reserved.*/package com.huawei.prac;import java.util.Arrays;public class Solution7th {public static void main(String[] args) {int[] gas = {1, 2, 3, 4, 5};int[] cost = {3, 4, 5, 1, 2};System.out.println(canCompleteCircuit(gas, cost));}/*** 134. 加油站[简单模拟 + 逻辑转化]** @param gas 已有汽油* @param cost 所需汽油* @return 可绕环路行驶一周的起点*/public static int canCompleteCircuit(int[] gas, int[] cost) {int sumGas = Arrays.stream(gas).sum();int sumCost = Arrays.stream(cost).sum();if (sumCost > sumGas) {return -1;}int[] cha = new int[gas.length];for (int i = 0; i < cha.length; i++) {cha[i] = gas[i] - cost[i];}int sum;int index;for (int i = 0; i < cha.length; i++) {if (cha[i] > 0) {index = i;sum = cha[i];boolean find = true;for (int j = i + 1; j < cha.length; j++) {sum += cha[j];if (sum < 0) {find = false;break;}}if (find) {return index;}}}// 特殊情况:差值为零return 0;}
}