首页 > ACM题库 > LeetCode > LeetCode-Gas Station
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.

题目链接:https://oj.leetcode.com/problems/gas-station/

今年乐视网的笔试题就出了这一题。一个重要的条件:保证会只有一个结果,有了这个保证,题目就比较简单了。

假设 E[i,k] (k <= n)是从i开始走k个station后,剩余的油量。

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
其中 gas_earn[i] = gas[i mod n] – cost[i mod n]  所以问题转化为了找到一个i,使得 E[i,k]>=0, k=0,1,…,n.

需要证明的是:当 sum(gas[0..n-1]) >= sum(cost[0..n-1]),即代码中的 total >= 0,问题比有解。

参考:http://www.cnblogs.com/zzzdevil/p/3651168.html 给出的证明

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)

输出:start station :  2


  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