Contenu du cours
Greedy Algorithms using Python
Greedy Algorithms using Python
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:
pos = 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.
Passez à un bureau pour une pratique réelleContinuez d'où vous êtes en utilisant l'une des options ci-dessousMerci pour vos commentaires !
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:
pos = 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.
Passez à un bureau pour une pratique réelleContinuez d'où vous êtes en utilisant l'une des options ci-dessousMerci pour vos commentaires !
Passez à un bureau pour une pratique réelleContinuez d'où vous êtes en utilisant l'une des options ci-dessous