题解 | #牛群迁徙#
牛群迁徙
https://www.nowcoder.com/practice/686d79ac54874f5f8abbb83184102873
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param rivers int整型一维数组 * @return int整型 */ public int min_jumps (int[] rivers) { // write code here int left = 0; int count = 0; while (left<rivers.length-1){ count++; if(left+rivers[left]>=rivers.length-1){ break; } int index = 0; int right = left; for(int i=left+1;i<=left+rivers[left] && i<rivers.length;i++){ if(i+rivers[i]>index){ index = i+rivers[i]; right = i; } } left = right; } return count; } }
本题考察的知识点是贪心算法,所用编程语言是java。
我们要求跳到河岸的步数最小,按照贪心的想法我们应该每一步都跳到最大值才能够步数最小。那么接下来我们应该想一想如何做到每一步都跳到最大值,我们每一步的选择只能是当前位置能跳的距离之内,我们应该选择下一步位置加上下一步位置能够跳的距离最大值