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

目录

题目部分

解读与分析

代码实现

---

题目部分

---

解读与分析

题目解读：

整形数组的长度为 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);
}

(完)