【最新华为OD机试E卷】找终点(100分)

🍭 大家好这里是春秋招笔试突围 ，一枚热爱算法的程序员

💻 ACM金牌🏅️团队 ｜ 大厂实习经历 ｜ 多年算法竞赛经历

✨ 本系列打算持续跟新华为OD-E/D卷的多语言AC题解

🧩 大部分包含 Python / C / Javascript / Java / Cpp 多语言代码

👏 感谢大家的订阅➕ 和 喜欢💗 和手里的小花花🌸

最新华为OD机试E卷全、新、准，题目覆盖率达 95% 以上，其中D卷题目全部支持在线评测，E卷题目正在持续上线中~

最新华为OD机试专栏: https://www.nowcoder.com/creation/manager/columnDetail/MgbyJj

🎀关于华为OD

• ✨华为OD的概念 华为的大部分社会招聘采用了被称为OD（Outsourcing Dispatch）模式，这是一种与德科共同进行的招聘方式。在这种模式下，被招聘的员工通常被定级在13至17级，这些员工被视为华为的储备人才。华为每年会从这些OD项目中选拔表现出色的员工，并将他们转为正式员工。
• ⌚️华为 OD 应聘流程

  • 第一步：投递简历

    • 提供姓名、邮箱、手机号、身份证号，用于锁定，所以投递前需要考虑清楚，投到项目组之后，一般不会转给另一个项目的 HR 了，也就是被锁定。

  • 第二步：机试

    • 3 道算法题，400 分满分，一般 1 个月的准备时间，华为机试必须要 150 分以上，没有过半年之后才能参加下一次考试。

  • 第三步：技术面

    • 2 轮技术面试。

  • 第四步：HR 与主管面试

  • 第五步：录用，发 offer

🍓OJ题目截图

🪴 找终点

问题描述

给定一个正整数数组 ，数组最大长度为 100。你需要从第一个元素开始，计算到达数组最后一个元素所需的最少步数。

移动规则如下：

1. 第一步必须从第一个元素开始，步长范围为 ，其中 为数组长度。
2. 从第二步开始，每一步的步长必须等于当前所在位置的元素值，不能多也不能少。
3. 只能向数组尾部移动，不能往回走。

如果无法到达最后一个元素，则返回 。

输入格式

输入为一行，包含若干个正整数，以空格分隔，表示给定的数组 。数组长度小于 100。

输出格式

输出一个整数，表示最少的步数。如果无法到达最后一个元素，输出 。

样例输入1

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

样例输出1

2

样例输入2

1 2 3 7 1 5 9 3 2 1

样例输出2

-1

样例解释

数据范围

题解

动态规划

这道题目本质上是一个动态规划问题，需要找到从起点到终点的最短路径。一步步来分析这个问题：

1. 首先，需要考虑第一步的特殊性。第一步可以选择的步长范围是 。这意味着我们需要尝试所有可能的第一步，并为每种可能性计算最短路径。

2. 从第二步开始，每一步的步长都是固定的，等于当前位置的元素值。这简化了我们的计算，因为每个位置的下一步是确定的。

3. 我们可以使用一个数组 来存储到达每个位置的最少步数。初始时，除了起点外，所有位置的步数都设为无穷大。

4. 对于第一步，遍历所有可能的步长，更新相应位置的步数为 1。

5. 然后，从前往后遍历数组。对于每个已经可以到达的位置（即 不为无穷大），尝试从这个位置跳到下一个位置。如果能跳到，并且新的步数小于已记录的步数，我们就更新 数组。

6. 最后，检查终点的步数。如果它不是无穷大，说明可以到达，返回这个步数；否则，返回 -1。

参考代码

• Python

def min_steps(nums):
    n = len(nums)
    # 初始化dp数组，除起点外都设为无穷大
    dp = [float('inf')] * n
    dp[0] = 0
    
    # 处理第一步
    for i in range(1, min(n, n // 2)):
        dp[i] = 1
    
    # 动态规划过程
    for i in range(n):
        if dp[i] != float('inf'):
            # 如果当前位置可达，尝试跳到下一个位置
            next_pos = i + nums[i]
            if next_pos < n:
                dp[next_pos] = min(dp[next_pos], dp[i] + 1)
    
    # 返回结果
    return dp[-1] if dp[-1] != float('inf') else -1

# 读取输入
nums = list(map(int, input().split()))

# 计算并输出结果
print(min_steps(nums))

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MIN(a, b) ((a) < (b) ? (a) : (b))

int min_steps(int* nums, int n) {
    // 动态分配dp数组
    int* dp = (int*)malloc(n * sizeof(int));
    // 初始化dp数组，除起点外都设为INT_MAX
    for (int i = 0; i < n; i++) {
        dp[i] = INT_MAX;
    }
    dp[0] = 0;
    
    // 处理第一步
    for (int i = 1; i < n / 2 && i < n; i++) {
        dp[i] = 1;
    }