华为OD机试真题——找终点（2025A卷：100分）Java/python/JavaScript/C/C++/GO最佳实现

2025 A卷 100分 题型

本专栏内全部题目均提供Java、python、JavaScript、C、C++、GO六种语言的最佳实现方式；

并且每种语言均涵盖详细的问题分析、解题思路、代码实现、代码详解、3个测试用例以及综合分析；

本文收录于专栏：《2025华为OD真题目录+全流程解析+备考攻略+经验分享》

华为OD机试真题《找终点》：

文章快捷目录

题目描述及说明

Java

python

JavaScript

C

GO

题目名称：找终点

1. 知识点：动态规划、贪心算法
2. 时间限制：1秒
3. 空间限制：256MB
4. 限定语言：不限

题目描述

给定一个正整数数组 nums（长度 ≤100），从第一个元素开始，按照以下规则移动到数组最后一个元素，求最少步数。若无法到达，返回 -1。

规则：

1. 第一步必须从 nums[0] 开始，且步长 k 满足 1 ≤ k < len/2（len 为数组长度）。
2. 从第二步开始，每一步的步长由当前所在位置的元素值决定（即移动到 nums[current_index] 的位置）。
3. 只能向数组尾部移动，不能回头。
4. 若最终恰好到达最后一个元素，则返回步数；否则返回 -1。

输入描述：

• 一行由空格分隔的正整数，表示数组 nums。

输出描述：

• 一个整数，表示最少步数；若无法到达，输出 -1。

示例1：
输入：

7 5 9 4 2 6 8 3 5 4 3 9  

输出：

2  

解释：

• 第一步选择步长 2（7 → 9），第二步从 9 跳 9 步到达终点。

示例2：
输入：

1 2 3 7 1 5 9 3 2 1  

输出：

-1  

解释：

• 无法通过任何第一步步长组合到达终点。

Java

问题分析

我们需要从数组的第一个元素出发，按照特定规则跳跃到最后一个元素。规则要求第一步的步长必须在特定范围内，后续步长由当前元素值决定。目标是找到到达终点的最少步数，若无法到达则返回-1。

解题思路

1. 第一步范围限制：第一步的步长k必须满足 1 ≤ k < len/2，其中 len 是数组长度。
2. 模拟跳跃过程：对每个可能的初始步长k进行模拟，计算是否可达终点及所需步数。
3. 动态更新最优解：记录所有可行路径中的最小步数，若没有可行路径则返回-1。

代码实现

import java.util.Scanner;

public class Main {
   
    public static void main(String[] args) {
   
        Scanner scanner = new Scanner(System.in);
        String[] input = scanner.nextLine().split(" ");
        int[] nums = new int[input.length];
        for (int i = 0; i < input.length; i++) {
   
            nums[i] = Integer.parseInt(input[i]);
        }
        System.out.println(findMinSteps(nums));
    }

    private static int findMinSteps(int[] nums) {
   
        int len = nums.length;
        if (len <= 1) {
    // 数组长度不足，无法跳跃
            return -1;
        }
        int maxK = (len - 1) / 2; // 计算最大初始步长
        if (maxK < 1) {
    // 初始步长范围无效
            return -1;
        }
        int minSteps = Integer.MAX_VALUE; // 记录最小步数

        for (int k = 1; k <= maxK; k++) {
    // 枚举所有可能的初始步长
            int current = k; // 初始位置
            int steps = 1; // 初始步数
            if (current == len - 1) {
    // 直接到达终点
                minSteps = Math.min(minSteps, steps);
                continue;
            }
            boolean reachable = false;
            while (current < len - 1) {
    // 未到达终点时继续跳跃
                int jump = nums[current]; // 获取当前元素的步长
                current += jump; // 跳跃到新位置
                steps++; // 步数增加
                if (current == len - 1) {
    // 到达终点
                    reachable = true;
                    break;
                } else if (current > len - 1) {
    // 越界，无法到达
                    break;
                }
            }
            if (reachable) {
    // 更新最小步数
                minSteps = Math.min(minSteps, steps);
            }
        }

        return (minSteps == Integer.MAX_VALUE) ? -1 : minSteps;
    }
}

代码详解

1. 输入处理：

   • 读取输入字符串并分割为整数数组 nums。

2. 边界条件处理：

   • 数组长度小于等于1时直接返回-1。
   • 计算最大初始步长 maxK = (len - 1) / 2。

3. 枚举初始步长：

   • 遍历所有可能的初始步长 k（1到maxK）。

4. 模拟跳跃过程：

   • 从初始位置 current = k 开始，记录步数 steps = 1。
   • 若初始位置即为终点，直接更新最小步数。
   • 循环中根据当前元素值跳跃，更新位置和步数。
   • 若到达终点，标记为可行路径并更新最小步数；若越界则终止。

5. 返回结果：

   • 若存在可行路径返回最小步数，否则返回-1。

示例测试

示例1：
输入：

7 5 9 4 2 6 8 3 5 4 3 9

输出：

2

解析：

• 初始步长k=2，跳跃到索引2（元素9），再跳9步到达终点，共2步。

示例2：
输入：

1 2 3 7 1 5 9 3 2 1

输出：

-1

解析：

• 所有初始步长的跳跃路径均无法到达终点。

示例3：
输入：

3 1 1

输出：

2

解析：

• 初始步长k=1