Leetcode Greedy 134, 55 @Python－CONY的世界

134. 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.

紀錄這題我一開始想到的就是想找扣最多當最後，然後向後找正值當起頭

結果很難寫.....就去解答了

這題用到蠻重要的一個觀念

When sum(i, j) < 0, start = i + 1

Since there is always a solution, once we find a range sum < 0, we can let this range be the last range in the whole trip. Then, start = i + 1.
If car starts at i and can not reach j. Any station between i and j can not reach B.( j is the first station that i can not reach.)

         ex. reamin = gas - cost = 2+3+(-7)           ( even start from 3, remain would be still not enough )

Success:

38 ms, beats 70.82 % of python submissions

class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        """
        :type gas: List[int]
        :type cost: List[int]
        :rtype: int
        """
        start, balance = 0, 0
        if sum(gas) - sum(cost) < 0:
            return -1
        for index in range(len(gas)):
            balance += gas[index] - cost[index]
            if balance < 0: 
                start = index + 1
                balance = 0
        return start

55. Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

這題我的概念是看能走多遠，所以用 reach 當變數名稱

當reach == position 時表示最遠只能到這裡了，所以就跳出

只要pos 還沒走到 reach，就可邊走邊看能不能更新到更遠的reach

Success:

52 ms, beats 57.04 % of python submissions

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        reach, length = 0, len(nums)
        for pos in range(length):
            reach = max(pos + nums[pos], reach)
            if pos == reach: break
        return True if reach >= length-1 else False

更簡潔的寫法，不過時間一樣

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        reach = 0
        for pos, value in enumerate(nums):
            if pos > reach: return False 
            reach = max(pos + value, reach)
        return True


然後更有趣的一行寫法，大概因為過於複雜，所以速度竟然更慢呢wwww

72 ms, beats 15.54 % of python submissions

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        return reduce(lambda m, (i, n): max(m, i+n) * (i <= m), enumerate(nums, 1), 1) > 0