当前位置:网站首页>leetcode:55. 跳跃游戏
leetcode:55. 跳跃游戏
2022-08-09 06:36:00 【uncle_ll】
55.跳跃游戏
来源:力扣(LeetCode)
链接: https://leetcode.cn/problems/jump-game/
给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 1:
输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2:
输入:nums = [3,2,1,0,4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。
提示:
- 1 < = n u m s . l e n g t h < = 3 ∗ 1 0 4 1 <= nums.length <= 3 * 10^4 1<=nums.length<=3∗104
- 0 < = n u m s [ i ] < = 1 0 5 0 <= nums[i] <= 10^5 0<=nums[i]<=105
解法
- 贪心算法:具体就是看当前位置能够跳多远,是否能够涵盖相邻的位置;
- 从左往右:起点边界是0,下一步能跳的最远的距离就是nums[i] + i, 不断更新最大的边界,如果某个下标不能被跳到的话,返回False。遍历完成后最终返回True
- 从右往左:假设我们能够跳到最后,我们从后往前跳;当前到达的下标是len(nums)-1, 我们看前面一个节点跳的距离是否包含该节点,如果能够到达该节点,更新该节点为前一个节点,最终看是否能够跳到0这个下标对应的节点
代码实现
贪心算法
- 从左往右跳
python实现
class Solution:
def canJump(self, nums: List[int]) -> bool:
if len(nums) == 1:
return True
k = 0
for i in range(len(nums)):
if i > k:
return False
k = max(k, nums[i]+i)
return True
c++实现
class Solution {
public:
bool canJump(vector<int>& nums) {
if (nums.size() == 1)
return true;
int k = 0;
for (int i=0; i<nums.size(); i++) {
if (i > k)
return false;
k = max(k, nums[i]+i);
}
return true;
}
};
- 从右往左
python实现
class Solution {
public:
bool canJump(vector<int>& nums) {
if (nums.size() == 1)
return true;
int enableReach = nums.size()-1;
for (int i=nums.size()-2; i>=0; i--) {
if (nums[i] + i >= enableReach)
enableReach = i;
}
return enableReach == 0;
}
};
c++实现
class Solution {
public:
bool canJump(vector<int>& nums) {
if (nums.size() == 1)
return true;
int enableReach = nums.size()-1;
for (int i=nums.size()-2; i>=0; i--) {
if (nums[i] + i >= enableReach)
enableReach = i;
}
return enableReach == 0;
}
};
复杂度分析
- 时间复杂度: O ( N ) O(N) O(N)
- 空间复杂度: O ( 1 ) O(1) O(1)
边栏推荐
- 报错:FSADeprecationWarning: SQLALCHEMY_TRACK_MODIFICATIONS重大开销和将disab补充道
- 2022.8.8DAY628
- 详解C语言中的wait()函数和waitpid()函数
- 推进产教融合 赋能教育创新发展 | 华云数据荣获“企业贡献奖”
- SIGINT, SIGKILL, SIGTERM signal difference, summary of various signals
- IQ Products巨细胞病毒CMV感染检测试剂盒的特征和应用
- DDD 领域驱动设计
- Common Oracle Commands
- AD画PCB板教程 20分钟讲清楚操作流程 铺铜 网络标号
- Built-in macros in C language (define log macros)
猜你喜欢
zip压缩包密码解密
中英文说明书丨TRC 交替醇(Catalogue NumberA575760)
CalBioreagents超全Id 蛋白兔单克隆抗体,助力科研
Teach you how to make the Tanabata meteor shower in C language - elegant and timeless (detailed tutorial)
The working principle of the transformer (illustration, schematic explanation, understand at a glance)
CMake中INSTALL_RPATH与BUILD_RPATH问题
Go lang1.18入门精炼教程——第一章:环境搭建
中英文说明书丨CalBioreagents 山羊抗人白蛋白,IgG组分
锁执行的过程
Leetcode 70 stairs issues (Fibonacci number)
随机推荐
推进产教融合 赋能教育创新发展 | 华云数据荣获“企业贡献奖”
Distributed id generator implementation
Teach you how to make the Tanabata meteor shower in C language - elegant and timeless (detailed tutorial)
抗菌药物丨Toronto Research Chemicals 天冬酰胺D
Excel受保护的工作表怎么操作?
简单使用Lambda表达式
长沙学院2022暑假训练赛(一)六级阅读
Integer 线程安全的
shardingsphere data sharding configuration item description and example
Common Oracle Commands
crc calculation
Xilinx Zynq ZynqMP DNA
Leetcode 70 stairs issues (Fibonacci number)
BeautifulSoup4的介绍与使用
uniapp实现防抖搜索
工控设备的系统如何进行加固
CMake中INSTALL_RPATH与BUILD_RPATH问题
The JVM thread state
The division principle summary within the collection
如何操作数据库