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的。 ”
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