Wednesday, October 2, 2013

Gas Station

Q;
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.
A:    解法二更简单明了~~~~~~~更深入核心~~~~~~




-----------------------------------------第二遍----------------------------
“假设,我们从环上取一个区间[i, j], j>i, 然后对于这个区间的diff加和,定义
sum[i,j] = ∑diff[k] where i<=k<j
如果sum[i,j]小于0,那么这个起点肯定不会在[i,j]这个区间里,跟第一个问题的原理一样。举个例子,假设i是[0,n]的解,那么我们知道 任意sum[k,i-1] (0<=k<i-1) 肯定是小于0的,否则解就应该是k。同理,sum[i,n]一定是大于0的,否则,解就不应该是i,而是i和n之间的某个点。所以第二题的答案,其实就是 在0到n之间,找到第一个连续子序列(这个子序列的长度必然是n)大于0的。   ”
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int A[2*n];
        for(int i =0;i<n;i++)
            A[i]=A[i+n] = gas[i] -cost[i];
        
        int presum = 0;
        for(int i = 0;i<2*n; ++i) // calculate the accumulated gas so far
        {
            A[i] += presum;
            presum = max(0,A[i]);
        }
        
        int count = 0;// count values that >=0
        for(int i =0;i<2*n;++i)
        {
            count = A[i]>=0?count+1:0;
            if(count==n)
                return i-count+1;
        }
        return -1;
    }
};

 -------------------------------------------3 rd ----------------------------------------
这次, 第二遍是利用了extra array,  this time, we do not need extra array 
这一遍,自己是  寻找max sub array, (with size <= n), 然后记录下来。再去查看是否能跑完。
public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int start = 0;
        while(start<n){
            int end = start;// end is exclusive
            int sum = 0;
            while(sum >=0&& end-start < n){
                sum += gas[end%n] - cost[end%n] ;
                end ++;
            }
            if(sum<0)
                start = end;
            else
                return start;
        }
        return -1;
    }
}



 -------------------------------------------1 st ----------------------------------------
思路很简单, 就是CLRS chapter 4 的那个divide-and-conquer 思路。
稍微tricky的一点儿就是,把dif数组double了长度, 这样就避免了circle问题。

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
            // this problem is quite like that of finding the max-subarray.
            int n = gas.length;
            int[] dif = new int[2*n];
            for(int i =0;i<n;i++){
                dif[i] = gas[i] - cost[i];
                dif[n+i] = dif[i];
            }
            // find the max-sub array of the diff
            int[] arraIndexNSum = maxSubArray(dif,0,2*n-1);
            // test if we can traver all the circle
            int startIndex = arraIndexNSum[0];
            int sum =0;
            for( int i = startIndex;i<startIndex+n;i++){
                sum+=dif[i];
                if(sum<0){
                    return -1;
                }
            }
            return startIndex;
            
        }
        private int[] maxSubArray(int[] dif,int low, int high){
            // return the subarray index within which it has the max-sum
            if(high == low){
                int[] tmp = {low,high,dif[low]};
                return tmp;
            }
            // now  hig > low
            int mid = (low+high)/2;
            int[] left = maxSubArray(dif,low,mid);
            int[] right = maxSubArray(dif,mid+1,high);
            int[] cross = findMaxAcross(dif,low,mid,high);
            if(left[2] >= right[2] && left[2]>=cross[2]){
                return left;
            }else if(right[2] >= left[2] && right[2]>=cross[2]){
                return right;
            }else{
                return cross;
            }
        }
        private int[] findMaxAcross(int[] dif, int low,int mid, int high){
            // because that all solution is unique, we do not need to consider the case that they are 
            int leftSum = Integer.MIN_VALUE /2 -1;
            int sum =0;
            int maxLeft = mid;
            for(int i = mid ; i>=low ;i--){
                sum += dif[i];
                if(sum>leftSum){
                    leftSum = sum;
                    maxLeft = i;
                }
            }
            int rightSum = Integer.MIN_VALUE /2 -1;
            int length = dif.length/2;
            int maxRight = mid+1;
            sum = 0;
            for(int i=mid+1; i<high && (i-maxLeft+1)<=length; i++){
                sum += dif[i];
                if(sum> rightSum){
                    rightSum = sum;
                    maxRight = i;
                }
            }
            int[] tmp =  {maxLeft,maxRight,leftSum+rightSum};
            return tmp;
        }
        
    }

注意,这里,有一点儿其实是不太对的, 就是,利用了unique solution的情况。 导致了,我们在fincMaxAcroos的时候,不分左右,直接就在右边寻找的时候,限制了长度。
Mistakes:
1:在 findMaxAcross() 中,由于我们开始让
int leftSum = Integer.MIN_VALUE ;
int rightSum = Integer.MIN_VALUE  那么,在二者没有动的时候,两者相加,就得到一个很大, 正的 int数组。 --------------- 因此, 实际代码中,我们用
int leftSum = Integer.MIN_VALUE /2 -1;来代替。

2:   其实,要求max sum subarray, 有个更简单的算法, 也是O(n)的。  看本博客的帖子。

Learned:




No comments:

Post a Comment