华为秋季招聘笔试试题分析
最编程
2024-04-19 18:47:07
...
大家好,我是吴师兄,关注我,每天更新大厂最新笔试题解析。
题目描述
小明和朋友玩跳格子游戏,有 n
个连续格子,每个格子有不同的分数,小朋友可以选择以任意格子起跳,但是不能跳连续的格子,也不能回头跳;
给定一个代表每个格子得分的非负整数数组,计算能够得到的最高分数
输入描述
给定一个数列,如: 1`` ``2 3 1
输出描述
输出能够得到的最高分,如: 4
备注
1 ≤ nums.length ≤ 100
0 <= nums[i] <= 1000
示例一
输入
1 2 3 1
输出
4
说明
选择跳第一个格子和第三个格子
示例二
输入
2 7 9 3 1
输出
12
说明
2`` ``+`` ``9`` ``+`` ``1`` ``=`` ``12
解题思路
注意,本题和LC198. 打家劫舍完全一致。
代码
# 输入分数数组
nums = list(map(int, input().split()))
# 获得格子数
n = len(nums)
# 如果长度为1,那么直接输出nums[0]
if n == 1:
print(nums[0])
# 否则,进行dp过程
else:
# 初始化长度为n的dp数组
# dp[i]表示,考虑第i个格子时,能获得的最高分数
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
# 遍历剩余所有格子,
# 动态转移方程为dp[i] = max(dp[i-1], nums[i] + dp[i-2])
# 表示考虑dp[i]时,
# 可以选择其前一个位置dp[i-1]的分数
# 也可以选择其前两个位置dp[i-2]的分数加上nums[i]的分数
for i in range(2, n):
dp[i] = max(dp[i-1], nums[i] + dp[i-2])
print(dp[-1])
时空复杂度
时间复杂度:O(N)
。
空间复杂度:O(N)
。
推荐阅读
-
华为面试问题 华为笔试试题
-
华为秋季招聘面试经验分享!
-
超级全面!阿里巴巴最新发布23年秋季招聘200道Java面试题(附答案)
-
华为秋季招聘笔试试题分析
-
2023 年秋季招聘华为技术岗在线面试心得体会
-
华为提出了十项数学挑战!解决一个,年薪百万!(1)、2024年最新2024年Python社会招聘面试题精选
-
简单明了的面试分享--华为、YY、阿里春天招聘面试题
-
2021 年秋季招聘面试 - 华为 [Hesi-Chip & Device Engineer] - 面试分享
-
Android大厂面试高频问题分析,工资翻倍(1),华为手机面试题
-
超级全面!阿里巴巴最新发布23年秋季招聘200道Java面试题(附答案)