Study Plan For Algorithms - Part23

1. 跳跃游戏 II
题目链接：https://leetcode.cn/problems/jump-game-ii/
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度:

• 0 <= j <= nums[i]
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        jumps = 0
        cur_end = 0
        cur_farthest = 0
        for i in range(n - 1):
            cur_farthest = max(cur_farthest, i + nums[i])
            if i == cur_end:
                jumps += 1
                cur_end = cur_farthest
        return jumps

2. 全排列
题目链接：https://leetcode.cn/problems/permutations/
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrack(nums, path, res):
            if not nums:
                res.append(path)
                return
            for i in range(len(nums)):
                backtrack(nums[:i] + nums[i + 1:], path + [nums[i]], res)

        res = []
        backtrack(nums, [], res)
        return res