?LeetCode刷題實(shí)戰(zhàn)45：跳躍游戲 II

樣例

輸入: [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個(gè)位置的最小跳躍數(shù)是 2。從下標(biāo)為 0?跳到下標(biāo)為 1?的位置，跳?1?步，然后跳?3?步到達(dá)數(shù)組的最后一個(gè)位置。

說明:
假設(shè)你總是可以到達(dá)數(shù)組的最后一個(gè)位置。

解題

搜索

class Solution:
    def jump(self, nums: List[int]) -> int:
        import queue
        n = len(nums)
        que = queue.Queue()
        que.put((0, 0))
        while not que.empty():
            pos, step = que.get()
            if pos >= n-1:
                return step
            for i in range(pos, min(n, pos+nums[pos] + 1)):
                que.put((i, step+1))

class Solution:
    def jump(self, nums: List[int]) -> int:
        import queue
        n = len(nums)
        que = queue.Queue()
        que.put((0, 0))
        visited = set()
        while not que.empty():
            pos, step = que.get()
            if pos >= n-1:
                return step
            
            for i in range(pos, min(n, pos+nums[pos] + 1)):
                # 如果已經(jīng)入過隊(duì)列了則跳過
                if i in visited:
                    continue
                que.put((i, step+1))
                visited.add(i)

class Solution:
    def jump(self, nums: List[int]) -> int:
        import queue
        n = len(nums)
        que = queue.Queue()
        que.put((0, 0))
        visited = set()
        while not que.empty():
            pos, step = que.get()
            if pos >= n-1:
                return step
            
            # 倒敘遍歷
            for i in range(min(n-1, pos+nums[pos]), pos, -1):
                # 當(dāng)遇到已經(jīng)遍歷過的元素的時(shí)候直接break
                if i in visited:
                    break
                que.put((i, step+1))
                visited.add(i)

class Solution:
    def jump(self, nums: List[int]) -> int:
        import queue
        n = len(nums)
        # 使用優(yōu)先隊(duì)列
        que = queue.PriorityQueue()
        que.put((0, 0, 0))
        visited = set()
        while not que.empty():
            _, pos, step = que.get()
            if pos >= n-1:
                return step
            
            # 倒敘遍歷
            for i in range(min(n-1, pos+nums[pos]), pos, -1):
                if i in visited:
                    break
                # 由于優(yōu)先隊(duì)列是默認(rèn)元素小的排在前面，所以加上負(fù)號(hào)
                que.put((-i - nums[i] ,i, step+1))
                visited.add(i)

貪心

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        start, end = 0, nums[0]
        step = 1
        if n == 1:
            return 0
        while end < n-1:
            maxi, idx = 0, 0
            # 維護(hù)下一個(gè)區(qū)間
            for i in range(start, end+1):
                if i + nums[i] > maxi:
                    maxi, idx = i + nums[i], i
            # 下一個(gè)區(qū)間的起始范圍
            start, end = end+1, maxi
            step += 1
        return step