【最新华为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。你需要从第一个元素开始,计算到达数组最后一个元素所需的最少步数。
移动规则如下:
- 第一步必须从第一个元素开始,步长范围为 ,其中 为数组长度。
- 从第二步开始,每一步的步长必须等于当前所在位置的元素值,不能多也不能少。
- 只能向数组尾部移动,不能往回走。
如果无法到达最后一个元素,则返回 。
输入格式
输入为一行,包含若干个正整数,以空格分隔,表示给定的数组 。数组长度小于 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 | 第一步:从第一个元素 7 开始,选择步长为 2,到达元素 9; 第二步:从 9 开始,经过 9 个元素到达数组末尾。总共用了 2 步。 |
样例2 | 无法到达数组末尾,因此输出 -1。 |
数据范围
题解
动态规划
这道题目本质上是一个动态规划问题,需要找到从起点到终点的最短路径。一步步来分析这个问题:
-
首先,需要考虑第一步的特殊性。第一步可以选择的步长范围是 。这意味着我们需要尝试所有可能的第一步,并为每种可能性计算最短路径。
-
从第二步开始,每一步的步长都是固定的,等于当前位置的元素值。这简化了我们的计算,因为每个位置的下一步是确定的。
-
我们可以使用一个数组 来存储到达每个位置的最少步数。初始时,除了起点外,所有位置的步数都设为无穷大。
-
对于第一步,遍历所有可能的步长,更新相应位置的步数为 1。
-
然后,从前往后遍历数组。对于每个已经可以到达的位置(即 不为无穷大),尝试从这个位置跳到下一个位置。如果能跳到,并且新的步数小于已记录的步数,我们就更新 数组。
-
最后,检查终点的步数。如果它不是无穷大,说明可以到达,返回这个步数;否则,返回 -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;
}
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
本专栏给大家提供了华为2024最新华为OD-E/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 部分题目提供OJ在线评测