Leetcode exercise - jumping game, combination summation

Jumping game II

subject

Here's an array of nonnegative integers nums , You are first in the array .

Each element in the array represents the maximum length you can jump at that location .

Your goal is to reach the last position of the array with the least number of jumps .

Suppose you can always reach the last position of the array .

Example

Input : nums = [2,3,1,1,4]
Output : 2
explain : The minimum number of jumps to the last position is 2.
From the subscript for 0 Jump to subscript 1 The location of , jump 1 Step , Then jump 3 Step to the last position of the array .

Input : nums = [2,3,0,1,4]
Output : 2

Code

class Solution(object):
    def jump(self, nums):
        if len(nums) == 1: return 0
        ans = 0 # Indicates the farthest position reached 
        curDistance = 0 #  Parameter initialization simplified writing 
        nextDistance = 0
        for i in range(len(nums)): # Traverse nums Each location in 
            nextDistance = max(i + nums[i], nextDistance) #  Next jump position 
            if i == curDistance:
                if curDistance != len(nums) - 1:
                    ans += 1
                    curDistance = nextDistance
                    if nextDistance >= len(nums) - 1: break
        return ans

Combinatorial summation II

subject

Given an array without repeating elements candidates And a target number target , find candidates All can make numbers and target The combination of .
candidates Each number in can only be used in each combination once .
explain ：
All figures （ Include target） Positive integers
The solution set cannot include duplicate combinations

Example

Input : candidates = [10,1,2,7,6,1,5], target = 8,
Output :
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Input : candidates = [2,5,2,1,2], target = 5,
Output :
[
[1,2,2],
[5]
]

Code

class Solution(object):
    def combinationSum2(self, candidates, target): # Combinatorial summation 
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []
        path = []
        def backtrack(candidates,target,sum,startIndex):
            if sum == target: res.append(path[:])
            for i in range(startIndex,len(candidates)): # To skip elements used in the same layer  
                if sum + candidates[i] > target: return 
                if i > startIndex and candidates[i] == candidates[i-1]: continue  # Direct use startIndex To and fro , To skip elements used in the same tree layer 
                sum += candidates[i]
                path.append(candidates[i])
                backtrack(candidates,target,sum,i+1) # i+1  Each number can only be used once in each combination  
                sum -= candidates[i]  # backtracking 
                path.pop()  
        candidates = sorted(candidates)  # Sort 
        backtrack(candidates,target,0,0)
        return res