Gas station (greedy)

---

title: Gas station （ greedy ）
date: 2022-04-29 14:43:09
categories: LeetCode
tags:

• greedy
• Make a little progress every day

---

subject

Gas station

difficulty secondary

There is... On a ring road n A gas station , Among them the first i Gas stations have gas gas[i] l . You have a car with unlimited tank capacity , From i A gas station goes to the i+1 A gas station needs gas cost[i] l . You start from one of the gas stations , The tank is empty at first . Given two arrays of integers gas and cost , If you can drive around the loop , Then return to the number of the gas station at the time of departure , Otherwise return to -1 . If there is a solution , be Guarantee It is only Of .

Example 1:

Input : gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output : 3
explain :
from 3 Gas station ( The index for 3 It's about ) set out , Can be obtained 4 A litre of petrol . Now the tank has = 0 + 4 = 4 A litre of petrol
Go to 4 Gas station , Now the tank has 4 - 1 + 5 = 8 A litre of petrol
Go to 0 Gas station , Now the tank has 8 - 2 + 1 = 7 A litre of petrol
Go to 1 Gas station , Now the tank has 7 - 3 + 2 = 6 A litre of petrol
Go to 2 Gas station , Now the tank has 6 - 4 + 3 = 5 A litre of petrol
Go to 3 Gas station , You need to consume 5 A litre of petrol , Just enough for you to return to 3 Gas station .
therefore ,3 Can be the starting index .

Example 2:

Input : gas = [2,3,4], cost = [3,4,3]
Output : -1

explain :
You can't 0 Number or 1 Gas station No.1 starts , Because there's not enough gas to get you to the next gas station .
We from 2 Gas station No.1 starts , You can get 4 A litre of petrol . Now the tank has = 0 + 4 = 4 A litre of petrol
Go to 0 Gas station , Now the tank has 4 - 3 + 2 = 3 A litre of petrol
Go to 1 Gas station , Now the tank has 3 - 3 + 3 = 3 A litre of petrol
You can't go back 2 Gas station , Because the return journey costs 4 A litre of petrol , But your tank only has 3 A litre of petrol .
therefore , No matter what , You can't even drive around the loop .

Tips :gas.length == n
cost.length == n
1 <= n <= 105
0 <= gas[i], cost[i] <= 104

Code ：

class Solution {    public int canCompleteCircuit(int[] gas, int[] cost) {        // Rule out special circumstances first         if(gas == null || cost == null || gas.length == 0 || cost.length == 0){            return -1;        }        if(gas.length == 1 && cost[0]== gas[0]){            return 0;        }        // The remaining array         int[] last = new int[gas.length];        // List of possible locations for starting points         List<Integer> list = new ArrayList<>();        int sum = 0;        for (int i = 0; i < gas.length; i++) {            last[i] = gas[i] - cost[i];            sum+=last[i];            if(last[i]>0){                list.add(i);            }        }        // It's impossible to run a lap         if(sum<0){            return -1;        }        int res = -1;        // Traverse all possible nodes         for (Integer i : list) {            boolean[] flag = new boolean[gas.length];            flag[i] = true;            int curr = i;            int j=0;            sum = last[curr];            // Running circle             for(j=0;j<gas.length;j++){                int next = curr+1==gas.length?0:curr+1;                sum +=last[next];                // There's not enough oil                 if(sum < 0){                    break;                }                curr = curr+1==gas.length?0:curr+1;            }            // You can run a lap             if(j==gas.length){                return i;            }        }        return res;    }}

To streamline the code ：

class Solution {    public int canCompleteCircuit(int[] gas, int[] cost) {        int start = 0, sum = 0, tank = 0;        for (int i = 0; i < gas.length; i++) {            tank += gas[i] - cost[i];            if (tank < 0) {                start = i + 1;                sum += tank;                tank = 0;            }        }        return sum + tank >= 0 ? start : -1;    }}

The above is the gas station （ greedy ）【LeetCode】 The whole content of

Copyright notice ：keafmd
Original Blogger ： Cowherd Conan
Blogger original link ：https://keafmd.blog.csdn.net/
Personal blog links ：https://www.keafmd.top/

If it helps you , Thank you for clicking on == One key, three links == Support ！
[ ha-ha ][ Huai Quan ]

come on. ！

Joint efforts ！

Keafmd

You can see it here , You know the following , Let's make progress together ！