贪心算法_程序人生

贪心算法

admin

2023-07-30 19:54:18

0次

思路：尽可能到达最远位置（贪心）
如果能到达某个位置，那一定能到达它前面的所有位置。
方法：初始化最远位置为 0，然后遍历数组，如果当前位置能到达，并且当前位置+跳数>最远位置，就更新最远位置。如果当前位置比最远位置还要远，直接返回False。

复杂度分析：
时间复杂度 $O (n)$ ，空间复杂度 $O (1)$ 。

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # 最远到达位置
        reach = 0
        for i in range(len(nums)):
            if i > reach: return False
            reach = max(reach, i + nums[i])
        return True

上一篇：python–shutil模块（拷贝和压缩）

下一篇：python Romber求积

热门资讯

Mobi、epub格式电子书如... 在wps里全局设置里有一个文件关联，打开，勾选电子书文件选项就可以了。

定时清理删除C:\Progra... C:\Program Files (x86)下面很多scoped_dir开头的文件夹写个批处理定...

scoped_dir32_70... 一台虚拟机C盘总是莫名奇妙的空间用完，导致很多软件没法再运行。经过仔细检查发现是C:\Program...

小程序支付时提示：appid和... [Q]小程序支付时提示：appid和mch_id不匹配 [A]小程序和微信支付没有进行关联，访问“小...

500 行 Python 代码... 语法分析器描述了一个句子的语法结构，用来帮助其他的应用进行推理。自然语言引入了很多意外的歧义，以我们...

pycparser 是一个用... `pycparser` 是一个用 Python 编写的 C 语言解析器。它可以用来解析 C 代码并构...

微信小程序使用slider实现... 众所周知哈，微信小程序里面的音频播放是没有进度条的，但最近有个项目呢，客户要求音频要有进度条控制，所...

65536是2的几次方计算2... 65536是2的16次方：65536=2⁶ 65536是256的2次方：65536=256 6553...

Apache Doris 2.... 亲爱的社区小伙伴们，我们很高兴地向大家宣布，Apache Doris 2.0.0 版本已于...

项目管理和工程管理的区别项目管理项目管理，顾名思义就是专注于开发和完成项目的管理，以实现目标并满足成功标准和项目要求。工...

贪心算法

相关内容

热门资讯