2014
10-10

# LeetCode-Gas Station

Gas Station

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.

E[i,k] = 0, if k=0
E[i,k] = gas_earn[i] + gas_earn[i+1] + … + gas_earn[i+k-1], if 0 < k <= n

python代码：

class Solution:
# @param gas, a list of integers
# @param cost, a list of integers
# @return an integer
def canCompleteCircuit(self, gas, cost):
n = len(gas)
pre = 0
curr_sum = 0
total = 0
for i in range(n):
total += gas[i] - cost[i]
curr_sum += gas[i] - cost[i]
if curr_sum < 0:
curr_sum = 0
pre = i+1
if total < 0:
return -1
else:
return pre

s = Solution()
start = s.canCompleteCircuit([1,5,1,5],[2,7,1,1])
print("start station : ", start)

1. for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
dp = dp [j-1] + 1;
if(s1.charAt(i-1) == s3.charAt(i+j-1))
dp = dp[i-1] + 1;
if(s2.charAt(j-1) == s3.charAt(i+j-1))
dp = Math.max(dp [j - 1] + 1, dp );
}
}
这里的代码似乎有点问题？ dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false