华为OD机考算法题：找终点

目录

题目部分

解读与分析

代码实现

---

题目部分

题目	找终点
难度	易
题目说明	给定一个正整数数组，设为nums，最大为100个成员，求从第一个成员开始，正好走到数组最后一个成员，所使用的最少步骤数。 要求： 1.第一步必须从第一元素开始，且 1 <= 第一步的步长 < len/2； (说明：len为数组的长度，需要自行解析。) 2.从第二步开始，只能以所在成员的数字走相应的步数，不能多也不能少,如果目标不可达返回-1，只输出最少的步骤数量。 3.只能向数组的尾部走，不能往回走。
输入描述	由正整数组成的数组，以空格分隔，数组长度小于100，请自行解析数据数量。
输出描述	正整数，表示最少的步数，如果不存在输出-1。
补充说明	补充说明
------------------------------------------------------
示例
示例1
输入	7 5 9 4 2 6 8 3 5 4 3 9
输出	2
说明	第一步：第一个选择步长 2，从第一个成员开始走 2 步，到达 9； 第二步：从 9 开始，经过自身数字 9 对应的 9 个成员到最后。
示例2
输入	1 2 3 7 1 5 9 3 2 1
输出	-1
说明	无

---

解读与分析

题目解读：

整形数组的长度为 len，第一步的大小可以是 [1, len/2) 中的任意一个数字，第二步和第二步以后的步数只能为当前成员的数字。

分析与思路：

题目中，第一步是可选的数字，一旦第一步数字固定了，后面的所有步数都是固定的。所以，此题可变的是第一步的步数，我们可以尝试第一步所有的可能的步数，计算所有能到达最后的步数，输出这些步数中的最小值即可。如果第一步尝试了所有可能的步数，全都无法达到最后一步，则输出 -1。

以上方法的时间复杂度为O()。

---

代码实现

Java代码

import java.util.Scanner;/*** 篮球比赛* @since 2023.10.08* @version 0.1* @author Frank**/
public class FindEnd {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {String input = sc.nextLine();String[] numbersStr = input.split( " " );processFindEnd( numbersStr );}}private static void processFindEnd( String numbersStr[] ){int count = numbersStr.length;int[] numbers = new int[count];for( int i = 0; i < count; i ++ ){numbers[i] = Integer.parseInt( numbersStr[i] );}int minSteps = Integer.MAX_VALUE;for( int i = 1; i < count * 1.0 / 2; i ++ ){int steps = 1;int next = i;while( next < count -1 ){steps ++;next = next + numbers[next];if( next == count -1 ){if( steps < minSteps ){minSteps = steps;}					break;}}}if( minSteps == Integer.MAX_VALUE ){minSteps = -1;}System.out.println( minSteps );}}

JavaScript代码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {while (line = await readline()) {var numberArr = line.split(" ");processFindEnd(numberArr);}
}();function processFindEnd(numbersStr) {var count = numbersStr.length;var numbers = new Array();for (var i = 0; i < count; i++) {numbers[i] = parseInt(numbersStr[i]);}var minSteps = Number.MAX_VALUE;for (var i = 1; i < count / 2; i++) {var steps = 1;var next = i;while (next < count - 1) {steps++;next = next + numbers[next];if (next == count - 1) {if (steps < minSteps) {minSteps = steps;}break;}}}if (minSteps == Number.MAX_VALUE) {minSteps = -1;}console.log(minSteps);
}

(完)