Python O(N) beats 99% Greedy with explanation


  • 0
    B

    1.Fist if the sum of the total gas greater than the total cost, we always can find a location to travel all of those places.
    2.then we need to find which locations are possible: we start from 0 if we go to specific location j and run out all of our gas ,THAT'S means all of the node from 0 to j can't be the desired start place , then we try j +1, let j+1 become new start place, at the end, we definitely can find a desired place.
    code as follows:

    class Solution(object):
        def canCompleteCircuit(self, gas, cost):
    
            gain = [gas[i] - cost[i] for i in xrange(len(cost))]
            if sum(gain) < 0: return -1
            index = tmp = 0
            for i in xrange(len(cost)):
                tmp += gain[i]
                if tmp < 0:
                    tmp = 0
                    index = i+1
            return index
    

Log in to reply
 

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