Jumping Frog
Each element in array nums represents the maximum jump length that can be done from this position. The frog's start position is the array’s first index, and each time at the position i it moves forward on 1, 2, … , or nums[i] steps. Return true if the frog can reach the last index, and false if not.
Example 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation: frog will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
At first sight, there are too many possible ways to reach it, and you can simply check them all until you find any. But this approach is not optimal enough. Let’s take a look at a greedy approach: let pos be the biggest index that a frog can reach in the current situation. Then, let’s try to make this value as much as possible, i. e. either jump to the i+nums[i] position or stay at the position pos (sometimes there is no sense to jump because you won’t come closer to the last index). We’ll update pos for each i from 0 to n, since the frog can jump to any position from i to a[i]+i. Note that some positions may be non-accessible, and when it happens, pos index becomes less than i.
Overall, there is an algorithm:
12345pos = 0 for i in range(n): if pos < i: return false # i is not accessible pos = max(pos, i+nums[i]) return pos >= i
Swipe to start coding
Put this algorithm inside jumping() function. Call the function.
Grazie per i tuoi commenti!
single
Chieda ad AI
Chieda ad AI
Chieda pure quello che desidera o provi una delle domande suggerite per iniziare la nostra conversazione
Awesome!
Completion rate improved to 7.69Jumping Frog
Scorri per mostrare il menu
Each element in array nums represents the maximum jump length that can be done from this position. The frog's start position is the array’s first index, and each time at the position i it moves forward on 1, 2, … , or nums[i] steps. Return true if the frog can reach the last index, and false if not.
Example 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation: frog will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
At first sight, there are too many possible ways to reach it, and you can simply check them all until you find any. But this approach is not optimal enough. Let’s take a look at a greedy approach: let pos be the biggest index that a frog can reach in the current situation. Then, let’s try to make this value as much as possible, i. e. either jump to the i+nums[i] position or stay at the position pos (sometimes there is no sense to jump because you won’t come closer to the last index). We’ll update pos for each i from 0 to n, since the frog can jump to any position from i to a[i]+i. Note that some positions may be non-accessible, and when it happens, pos index becomes less than i.
Overall, there is an algorithm:
12345pos = 0 for i in range(n): if pos < i: return false # i is not accessible pos = max(pos, i+nums[i]) return pos >= i
Swipe to start coding
Put this algorithm inside jumping() function. Call the function.
Cambia al desktop per esercitarti nel mondo realeContinua da dove ti trovi utilizzando una delle opzioni seguentiGrazie per i tuoi commenti!
single
