My python solution with some explanation.


  • 0
    M

    As for the prob, it's equals to find a position i satisfies the condition that for j (j=i,i+1,...,l-1,0,1,...i-1) and
    sigma(gas[k]-cost[k]) >= 0 (k=i to j). It maybe confused here. But we may think it more deeply. If one position
    i satisfies the condition, any position p that can reach i MUST satisfy it. However, the prob claims that the
    position is unique if have. We CAN go on looking for the position at the failed position. Every point could
    never be scanned more than twice. The complexity is O(n) in general. Here is my code.;)

    class Solution:
        # 134
        # @param {integer[]} gas
        # @param {integer[]} cost
        # @return {integer}
        def canCompleteCircuit(self, gas, cost):
            l = len(gas)
            cur = 0
            while cur<l:
                pos = cur
                bj = cur
                cnt = 0
                while True:
                    if cnt + gas[cur] < cost[cur]:
                        break
                    cnt = cnt + gas[cur] - cost[cur]
                    cur = (cur + 1) % l
                    if cur == pos: return pos
                if cur < bj: break
                cur += 1
    
            return -1

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.