一起刷算法 # 动态 # 01
2021/12/24 17:08:43
本文主要是介绍一起刷算法 # 动态 # 01,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
给你一个非负整数数组 nums ,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
解题思路
这道题比较简单,因为有这个条件:假设你总是可以到达数组的最后一个位置。
那么我们只需要每次都尽量的多跳,最后一定会到达终点
那么如何每次尽量多跳呢?
在每个位置能跳到的范围内,去找能跳的最远距离。
最远距离max = j + nums[j + i];其中 j 是跳的距离,nums[i + j]是跳到的位置能跳的距离。即预期最大收益化往后跳的距离。
例如 2 3 1 1 4,对于nums[0] = 2 ,他能跳到 3 和 1.
- 跳到3,预期就能前进 1 + 3 = 4.
- 跳到1,预期就能前进 2 + 1 = 3.
所以我们选择3.
代码
class Solution { public int jump(int[] nums) { if(nums.length <= 1)return 0; int[] dp = new int[nums.length]; int max = 0; int ans = 0; for(int i = 0; i < nums.length; i++){ int j = 0; int nextStep = 0; max = 0; if(i + nums[i] >= nums.length - 1){ ans++; break; } for(; j <= nums[i];j++){ if(j + nums[j + i] > max) { nextStep = j; max = j + nums[i + j]; } } ans++; i = nextStep + i - 1; } return ans; } }
这篇关于一起刷算法 # 动态 # 01的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)