kiddy

Gas station

leave a comment »

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

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.

Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int gsize = gas.size();
        if(gsize == 0)  return -1;
        int start = 0;
        int end = 0;
        int rem = 0;
        for(int i = 0; i < 2*gsize; i++){
            rem =  rem + gas[i%gsize]-cost[i%gsize];
            if(rem < 0){
                rem = 0;
                start = i+1;
                end = i+1;
            }else{
                end = i+1;
                if(end-start >= gsize){
                    return start;
                }
            }
        }
        return -1;
        
    }
};

Another solution: Do not need to scan for two cycles. Suppose j is the first return result from this program, that means before J gasSum is less than costSum. Suppose there is a i before j that make the cycle uncompleted, then before i and after j, the gasSum costSum, then there mush be a k before j, can be return from this problem, which is not contradict with the statement that j is the first.

class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int gasTotal = 0;
        int costTotal = 0;
        for(int i = 0; i < gas.size(); i++){
            gasTotal += gas[i];
            costTotal += cost[i];
        }
        if(gasTotal < costTotal)    return -1;
        int cur = 0;
        int index = 0;
        for(int i = 0; i < gas.size(); i++){
            cur += gas[i]-cost[i];
            if(cur < 0){
                index = i+1;
                cur = 0;
            }
        }
        return index;
    }
};
class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int size = gas.size();
        if (size == 0)  return 0;
        int startIdx = 0;
        int sumDiff = 0;
        int rem = 0;
        for (int i = 0; i < size; i++) {
            sumDiff += gas[i] - cost[i];
            if (rem < 0) {
                rem = gas[i] - cost[i];
                startIdx = i;
            } else {
                rem += gas[i] - cost[i];
            }
        }
        if (sumDiff >= 0) {
            return startIdx;
        } else { 
            return -1;
        }
    }
};
Advertisements

Written by linzhongzl

October 7, 2013 at 5:14 pm

Posted in Leetcode

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: