If the SumRe is positive, there must be a solution to this problem.


  • 0
    A

    class Solution
    {
    static int GetNext(const vector<int> &dataSpace, int index)
    {
    if(index == dataSpace.size() - 1)
    return 0;
    else
    return index + 1;
    }

    public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost)
    {
    // the start station
    if (gas.size() != cost.size())
    return -1;
    if (gas.size() == 0)
    return -1;

    	vector<int> dataSpace; int SumRe = 0;
    	for (unsigned int i = 0; i < gas.size(); i++)
    	{
    		dataSpace.push_back(gas[i] - cost[i]);
    		SumRe += gas[i] - cost[i];
    	}
    	
    	if(SumRe < 0)
    		return -1;
    	int startIndex = 0; int endIndex = 0; int Sum = 0;
    	while (startIndex != GetNext(dataSpace, endIndex))
    	{
    		Sum += dataSpace[endIndex];
    		if (Sum < 0)
    		{
    			endIndex = GetNext(dataSpace, endIndex);
    			startIndex = endIndex;
    			Sum = 0; 
    		}
    		else
    		{
    			endIndex = GetNext(dataSpace, endIndex);
    		}
    	}
    	return startIndex;
    }
    

    };


Log in to reply
 

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