directory

  • The title
  • 1, violence method, double layer traversal
  • 2, greedy

The title

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.

Example 1:

Input: gas = [1,2,3,4,5] cost = [3,4,5,1,2] output: 3 In this case, the fuel tank has = 0 + 4 = 4 liters of gasoline to the no. 4 gas station, and 4-1 + 5 = 8 liters of gasoline to the No. 0 gas station, and 8-2 + 1 = 7 liters of gasoline to the No. 1 gas station. Now you have 7-3 + 2 = 6 liters of gas going to gas station no. 2, and 6-4 + 3 = 5 liters of gas going to gas station No. 3. You need to consume 5 liters of gas, which is just enough to go back to gas station No. 3. Therefore, 3 can be the starting index.

Example 2:

Input: gas = [2,3,4] cost = [3,4,3] output: -1 explanation: you cannot start at gas station 0 or 1 because there is not enough gas to get you to the next gas station. We can get four litres of petrol from station No. 2. You can’t go back to gas station no. 2 because you’re going to use 4 liters of gas to get back, But you only have three liters in your tank. So, anyway, you can’t go all the way around the loop.

1, violence method, double layer traversal

Try each gas station as the starting point. If the current loss is greater than the current amount of fuel, it indicates that this method is not valid. Otherwise, accumulate the stations already passed. If you start at I in the current, and you have gone through N stations, then this is true, and you just return I, because you have determined that there is only one solution. If you run through all the cases, if none of them are correct, you return -1

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int N = gas.size(a);for(int i = 0; i < N; i++)
        {        
            int sumgas = 0;
            int sumcost = 0;
            int step = 0;
            while(step < N)
            {
                int j = (i + step) % N;
                sumgas += gas[j];
                sumcost += cost[j];
                // If the current loss is greater than the current oil quantity, this method is invalid
                if(sumcost > sumgas)
                {
                    break;
                }
                // If you can go, step+1
                step += 1;
            }
            // If you have completed one lap, return to the starting coordinate (the answer is unique)
            if(step == N) return i;
        }
        // If no result is found, return -1
        return - 1; }};Copy the code

2, greedy

Refer to the second idea in the code Catalog:

1, if the total amount of oil minus total consumption >=0 can certainly run a lap. 2. The remaining amount remain[I] of each gas station is gas[I] -cost [I]. 3. Cur_sum_error is the sum of the difference between gas and cost from the starting point to the current one. <0 indicates that the amount of oil obtained in the current interval is not enough to run, so the starting point must not be in this interval, and sufficient amount of oil must be obtained from other intervals before running this distance. 4. Determine the starting point backwards from 0. Cur_sum_error is zeroed out every time the start point is updated, as it is accumulated backwards from the new start point. 5. Total_sum_error is the sum of the difference between gas and cost at all gas stations, which is less than 0, indicating that there is no method that can complete a lap.

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int N = gas.size(a);// From the start point to the sum of the difference between the current gas and cost, <0 indicates that the amount of oil obtained in the current interval is not enough to run, so the starting point must not be in this interval, so we must obtain enough oil from other intervals before running this distance.
        int cur_sum_error = 0;
        int total_sum_error = 0;
        int start = 0;
        for(int i = 0; i < N; i++)
        {
            int remain_i = gas[i] - cost[i];
            cur_sum_error += remain_i;
            total_sum_error += remain_i;
            // If the current interval is not enough oil to run
            if(cur_sum_error < 0)
            {
                // The starting point may be next
                start = i+1;
                // The cur_sum_error value needs to be cleared
                cur_sum_error = 0; }}// If there is not enough oil in the whole process, there is no solution
        if(total_sum_error < 0) return - 1;
        // Otherwise there is a solution and the starting point is
        returnstart; }};Copy the code