华为OD机试真题（Java），最小步骤数（100%通过+复盘思路）

一、题目描述

一个正整数数组 设为nums，最大为100个成员，求从第一个成员开始正好走到数组最后一个成员所使用的最小步骤数。

要求：

1. 第一步 必须从第一元素起 且 1<=第一步步长<len/2 (len为数组长度)；
2. 从第二步开始只能以所在成员的数字走相应的步数，不能多不能少， 如果目标不可达返回-1， 只输出最小的步骤数量；
3. 只能向数组的尾部走不能向回走。

二、输入描述

有正整数数组空格分割，数组长度<100。

三、输出描述

正整数 最小步数，不存在输出-1。

四、Java算法源码

public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String[] nums = scanner.nextLine().split(" ");int len = nums.length;int[] arr = new int[len];for (int i = 0; i < len; i++) {arr[i] = Integer.parseInt(nums[i]);}int minCount = 0;// 第1步最多只能走 len/2，遍历各种情况for (int i = 1; i < len / 2; i++) {// 走出第一步后的步数和位置int count = 1;int index = i;// 从第2步开始只能以所在成员的数字走相应的步数while (true) {// 再走一步index += arr[index];// 步数加1count++;if (index > len - 1) {// 当走的长度超出了范围，说明这种情况不符合要求break;} else if (index == len - 1) {// 刚好走到最后一个成员，更新最小步数if (minCount == 0) {minCount = count;} else {minCount = Math.min(minCount, count);}break;}}}if (minCount == 0) {System.out.println(-1);} else {System.out.println(minCount);}
}

五、效果展示

1、输入：4 8 7 5 2 3 6 4 8 1

2、输出：2

3、说明：

1. 第一个可选步长选择2；
2. 从第一个成员4开始走两步到7；
3. 第二步：从7经过7个成员到最后。

4、思路分析

1. 1<=第一步步长<len/2 (len为数组长度)，需要遍历第一步的各种可能；
2. 从第二步开始只能以所在成员的数字走相应的步数，不能多不能少；
3. 只能向数组的尾部走不能向回走；

🏆本文收录于，华为OD机试2023（Java）

本专栏包含了最新最全的2023年华为OD机试真题，有详细的分析和Java解答。已帮助1000+同学顺利通过OD机考。专栏会持续更新，每天在线答疑。