LeetCode – Jump Game

LeetCode – Jump Game

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

一開始想DP一步步迭代更新,求出跳到最后一个的最小步数,可是时间复杂度O(nk),会超时。

再一想,发现该题仅仅须要返回是否能到达最后一个,不须要最小步数,所以迭代时候仅仅须要保留当前可以走到的最远距离tmpMax,时间复杂度降到O(n)。

class Solution {
public:
	const int MAXVALUE = 1 << 30;
	bool canJump(int A[], int n) {

		int tmpMax = 0;

		if (n == 1)
			return true;

		for (int i = 0; i < n - 1; i++)
		{
			if (i > tmpMax)return false;

			if (tmpMax < i + A[i])
				tmpMax = i + A[i];
			if (tmpMax >= n - 1)
				return true;
		}

		return false;
	}
};

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118467.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • ubuntu上docker卸载重装[通俗易懂]

    ubuntu上docker卸载重装[通俗易懂]清理docker并重装1、删除容器1)首先需要停止所有的容器dockerstop$(dockerps-a-q)2)删除所有的容器(只删除单个时把后面的变量改为imageid即可)dockerrm$(dockerps-a-q)2、删除镜像1)查看host中的镜像dockerimages2)删除指定id的镜像dockerrmiimageid想要删除untaggedimages,也就是那些id为的image的话可以用dockerrmi$(dockeri

  • pki 体系_基于PKI体系的认证方式进行论述

    pki 体系_基于PKI体系的认证方式进行论述首先,PKI(PublicKeyInfrastructure)是一个体系。公钥基础设施是一个包括硬件、软件、人员、策略和规程的集合,用来实现基于公钥密码体制的密钥和证书的产生、管理、存储、分发和撤销等功能。PKI体系是计算机软硬件、权威机构及应用系统的结合。它为实施电子商务、电子政务、办公自动化等提供了基本的安全服务,从而使那些彼此不认识或距离很远的用户能通过信任链安全地交流。—百度百科说白了,PKI还是提供了彼此身份确认的服务,确保通信的安全。…

  • pycharm 2021 2.3 激活码【中文破解版】

    (pycharm 2021 2.3 激活码)这是一篇idea技术相关文章,由全栈君为大家提供,主要知识点是关于2021JetBrains全家桶永久激活码的内容IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html00OE5RWT28-eyJsa…

  • Unity 协程

    Unity 协程协程前言调用方式停止方式yiledreturn语句执行时机WaitForSeconds(floatTime)WaitForSecondsRealtime(floattime)WaitForEndOfFrame()WaitForFixedUpdate()WaitUntil(Funcpredicate)WaitWhile(Funcpredicate)实现自定义函数实际开发中使用建议前言协程是unity提供的一个特殊的机制,他的特点就是可以方便的实现流程化的东西。但是就他的效率而言个人感觉并不乐观,

  • 硬件资料和软件资料_电脑硬件检测工具哪个好

    硬件资料和软件资料_电脑硬件检测工具哪个好一些常用的资料_硬件/系统/等标题前数字代表专题所在楼层数2. BIOS报警声意义3. BIOS自检与开机故障相关问题5. 计算机几个常见指标的意义6. 显卡GPU参数7. 显示卡常见故障全面解决8. 集成声卡常见故障及解决9. 显示器经典故障以及处理办法10. AMI主板代码大全(BIOS-ID)12. AWARD主板代码大全(BIOS-ID)16. 黑屏故障17. WindowsX

    2022年10月20日
  • [MicroPython]TurniBit开发板DIY自动窗帘模拟系统

    [MicroPython]TurniBit开发板DIY自动窗帘模拟系统一、准备工作üTurnipBit开发板一块ü下载数据线一条ü微型步进电机(28BYJ-48)一个ü步进电机驱动板(ULN2003APG)一块ü光敏传感器一个üTurnipBit扩展板一块ü接入网络的电脑一台ü在线可视化编程器<http://turnipbit.com/PythonEditor/edit…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号