Can't I travel from right to left?


  • 0
    Input:	[1,2,3,3], [2,1,5,1]
    Output:	2
    Expected:	3
    

    Can't I travel from station[2] to the left?

    from to   tank gas cost
    2    1    0    3   1
    1    0    2    2   2
    0    3    2    1   1
    3    2    2    3   5 [OK]
    

    Thanks Shangrila. The key is "from station i to its next station i + 1", but I recommend to add some words to clarify this unidirection circle problem.

    My solution

    class Solution {
    public:
        int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        	int n = gas.size();
        	int sumVal = 0, tmpSumVal = 0, maxVal = 0, maxIndex = 0;
            for(int i = 0; i < n; ++i){
                int val = gas[i] - cost[i];
                if(val > maxVal || val == maxVal && tmpSumVal < 0){
                    maxIndex = i;
                    maxVal = val;
                    tmpSumVal = val;
                }
                sumVal += val;
                tmpSumVal += val;
            }
            return sumVal >= 0 ? maxIndex : -1;
        }
    };

  • 2
    S

    Here is the piece in problem description.

    You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

    For this specific 'Gas Station' problem, we can only move from i to i + 1, not in the opposite way.


  • 0
    M

    I suppose technically, you could look at the next station and see "how much gas will it take to get there" going in the reverse direction by checking cost[i-1] from station i, then filling up at station i to attempt to reach it.


  • 0
    A

    Here is the description:

    You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

    I take it as travel station i to next station ((i+1) % n), since it is a circle.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.