Jump Game II
You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].
Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:
0 <= j <= nums[i] and
i + j < n
Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].
class Solution:
def jump(self, nums: List[int]) -> int:
size = len(nums)
# destination is last index
destination = size - 1
# record of current coverage, record of last jump index
cur_coverage, last_jump_index = 0, 0
# counter for jump
times_of_jump = 0
# Quick response if start index == destination index == 0
if size == 1:
return 0
# Greedy strategy: extend coverage as long as possible with lazy jump
for i in range( 0, size):
# extend current coverage as further as possible
cur_coverage = max( cur_coverage, i + nums[i] )
# forced to jump (by lazy jump) to extend coverage
if i == last_jump_index:
# update last jump index
last_jump_index = cur_coverage
# update counter of jump by +1
times_of_jump += 1
# check if reached destination already
if cur_coverage >= destination:
return times_of_jump
return times_of_jumpRelated Problems
You are given an array of CPU tasks, each represented by letters A to Z, and a cooling time, n. Each cycle or interval allows the completion of one task. Tasks can be completed in any order, but there's a constraint: identical tasks must be separated by at least n intervals due to cooling time.
Return the minimum number of intervals required to complete all tasks.
Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element.
We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).
You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.
Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.