This is the 11th day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021

After a period of time, I retrained the greedy algorithm to see if my speed was improved. The result was still good. The greedy algorithm with the same difficulty in Leetcode solved the problem faster and faster than before.

Gas station

Subject address: leetcode-cn.com/problems/ga…

Title description:

There are N gas stations on a loop, and the ith gas station has a liter of gas.

You have a car with an infinite tank, and it costs you [I] liters of gas to go from the ith gas station to the I +1 gas station. You start at one of the gas stations with an empty tank.

Return the number of the gas station at the time of departure if you can make a full loop, otherwise -1.

Description:

If the problem has a solution, that answer is the only answer.

Input arrays are all non-empty arrays of the same length.

The elements in the input array are non-negative.

The sample

Input: gas = [1.2.3.4.5]
cost = [3.4.5.1.2] output:3Explanation: from3Gas station no. (index is3Start, available4Litre of petrol. So I have lambda equals theta0 + 4 = 4Litre of petrol4Gas station number two, there's gas in the tank4 - 1 + 5 = 8Litre of petrol0Gas station number two, there's gas in the tank8 - 2 + 1 = 7Litre of petrol1Gas station number two, there's gas in the tank7 - 3 + 2 = 6Litre of petrol2Gas station number two, there's gas in the tank6 - 4 + 3 = 5Litre of petrol3Gas station Number two, you need to consume5Liters of gas, just enough to get you back to3Gas station No. As a result,3Can be the starting index.Copy the code

Subject analysis

In my opinion, the first impression and had done a “two place scheduling” problem is very similar, are greedy algorithms

When comparing the two arrays of fuel quantity and consumption at the gas station, you can subtract them and get a new array to figure out whether the fuel tank is negative or positive at the gas station

Of course, even though the new array is summing up again, if the sum is less than 0, you can’t go all the way around, and you can return -1.

But there’s still a problem, and that’s how you get to the starting point if you can finish.

If total is negative, record that total to lastTotal and index to firstZ, reset total to 0, and then continue, negative again. LastTotal summation, adjusting firstZ to the latest index.

When the array is iterated, add the lastTotal and lastTotal to add up the array. The sum is greater than or equal to zero, and lastTotal is zero, which means we can go from the first value. Otherwise the starting position is firstZ plus 1.

var canCompleteCircuit = function(gas, cost) {
    let firstZ = 0, lastTotal = 0, total = 0;
    gas.forEach((item,index) = >{
        let n = item - cost[index];
        total += n;
        // Record total and index
        if (total < 0) {
            lastTotal += total;
            total = 0; firstZ = index; }})// lastTotal + total = total
    if ((lastTotal + total) < 0) {
        return -1;
    } else {
        if (lastTotal == 0) { return 0; }
        return firstZ + 1; }};Copy the code