← Static tasks

134. Gas Station

leetcode medium

#array#csharp#leetcode#medium

Task

Вдоль кругового маршрута расположены n заправочных станций, на каждой из которых находится определённое количество топлива gas[i].

У вас есть автомобиль с неограниченным топливным баком, и для проезда от i-й станции к следующей (i + 1)-й станции требуется cost[i] топлива. Путешествие начинается с пустым баком на одной из заправочных станций.

C# solution

matched/original
public class Solution {
    public int CanCompleteCircuit(int[] gas, int[] cost) {
        int currGain = 0, totalGain = 0, answer = 0;
        for (int i = 0; i < gas.Length; ++i) {
            totalGain += gas[i] - cost[i];
            currGain += gas[i] - cost[i];
            if (currGain < 0) {
                answer = i + 1;
                currGain = 0;
            }
        }
        return totalGain >= 0 ? answer : -1;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int CanCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int currGain = 0, totalGain = 0, answer = 0;
        for (int i = 0; i < gas.size(); ++i) {
            totalGain += gas[i] - cost[i];
            currGain += gas[i] - cost[i];
            if (currGain < 0) {
                answer = i + 1;
                currGain = 0;
            }
        }
        return totalGain >= 0 ? answer : -1;
    }
}

Java solution

matched/original
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int currGain = 0, totalGain = 0, answer = 0;

        for (int i = 0; i < gas.length; ++i) {
            totalGain += gas[i] - cost[i];
            currGain += gas[i] - cost[i];
            if (currGain < 0) {
                answer = i + 1;
                currGain = 0;
            }
        }

        return totalGain >= 0 ? answer : -1;
    }
}

JavaScript solution

matched/original
var canCompleteCircuit = function (gas, cost) {
    let currGain = 0,
        totalGain = 0,
        answer = 0;
    for (let i = 0; i < gas.length; ++i) {
        totalGain += gas[i] - cost[i];
        currGain += gas[i] - cost[i];
        if (currGain < 0) {
            answer = i + 1;
            currGain = 0;
        }
    }
    return totalGain >= 0 ? answer : -1;
};

Python solution

matched/original
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        total_gain = 0
        curr_gain = 0
        answer = 0

        for i in range(len(gas)):
            total_gain += gas[i] - cost[i]
            curr_gain += gas[i] - cost[i]
            if curr_gain < 0:
                curr_gain = 0
                answer = i + 1

        return answer if total_gain >= 0 else -1

Go solution

matched/original
func canCompleteCircuit(gas []int, cost []int) int {
    var currGain int = 0
    var totalGain int = 0
    var answer int = 0
    for i := 0; i < len(gas); i++ {
        totalGain += gas[i] - cost[i]
        currGain += gas[i] - cost[i]
        if currGain < 0 {
            answer = i + 1
            currGain = 0
        }
    }
    if totalGain >= 0 {
        return answer
    } else {
        return -1
    }
}

Explanation