跳跃游戏(力扣55)

news/2025/2/25 17:25:15/

题目问是否可以跳到数组最后一个下标,有的同学可能会思考如何模拟跳跃这个操作,但这是比较困难的,很容易把自己绕进去。可以换一种思路,我们不需要知道具体是如何跳到最后一个下标的,而是找到最大的跳跃范围。如果该跳跃范围可以覆盖最后一个下标,就说明我们一定可以通过某种跳跃策略到达最后一个下标。更具体来说,不一定非要明确一次究竟跳几步,而是每次取最大的跳跃步数,这个就是可以跳跃的覆盖范围。这个范围内,别管是怎么跳的,反正一定可以跳过来。所谓的贪心也就是体现在:局部最优:每次取最大跳跃步数(取最大覆盖范围);整体最优: 最后得到整体最大覆盖范围,看是否能到终点。为了实现这个想法,代码的书写上还是有一定的技巧性。大家可以结合下面的代码及详细注释理解此题。

代码及详细注释如下:

class Solution {
public:bool canJump(vector<int>& nums) {//数组长度为1,进行剪枝if(nums.size() == 1){return true;}int cover = 0;//用cover变量控制for循环的遍历范围//每遍历到一个元素,如果该元素的跳跃范围更大,//cover 就得到该元素数值(新的覆盖范围)的补充,让 i 继续移动下去。for(int i = 0;i <= cover;i++){cover = max(cover,i + nums[i]);if(cover >= nums.size() - 1){return true;}}return false;}
};


 


http://www.ppmy.cn/news/1574875.html

相关文章

14.8 Auto-GPT 自主智能体设计解密:构建具备长期记忆的智能决策系统

Auto-GPT 自主智能体设计解密:构建具备长期记忆的智能决策系统 关键词:Auto-GPT 架构设计、自主智能体开发、LangChain Agents、长期记忆系统、工具链编排 1. 自主智能体的核心架构设计 Auto-GPT 系统架构图解: #mermaid-svg-NuDU1eo6sXqhA6Ve {font-family:"trebuch…

智能证件照处理器(深度学习)

功能说明:支持常见证件照尺寸(一寸、二寸、护照等) 智能背景去除(使用深度学习模型)自定义背景颜色选择自动调整尺寸并保持比例实时预览处理效果注意:整合rembg进行抠图,使用Pillow处理图像缩放和背景替换,定义常见证件照尺寸,并提供用户交互选项。首次运行时会自动下…

【算法通关村 Day10】快速排序与归并排序

快速排序与归并排序青铜挑战 快速排序的原理和实现 快速排序&#xff08;Quick Sort&#xff09;是一种分治法&#xff08;Divide and Conquer&#xff09;策略的排序算法&#xff0c;它通过选择一个“基准”元素&#xff0c;将数组分成两个部分&#xff0c;左边部分小于基准元…

【Golang 面试题】每日 3 题(六十三)

✍个人博客&#xff1a;Pandaconda-CSDN博客 &#x1f4e3;专栏地址&#xff1a;http://t.csdnimg.cn/UWz06 &#x1f4da;专栏简介&#xff1a;在这个专栏中&#xff0c;我将会分享 Golang 面试中常见的面试题给大家~ ❤️如果有收获的话&#xff0c;欢迎点赞&#x1f44d;收藏…

【odoo18-文件管理】在uniapp上访问odoo系统上的图片

在uniapp上访问odoo系统上的图片 1、以url的形式访问 a&#xff1a;以odoo本身的域名&#xff0c;比如http://127.0.0.1:8069/web/image/product.template/3/image_128?unique1740380422000&#xff0c;这种方式需要解决跨域的问题。 b&#xff1a;以文件服务器的形式&…

每日学习Java之一万个为什么

文章目录 16.前后端分离是怎么实现的&#xff1f;17.Servlet 和 Socket 区别18.为什么对于特别复杂的需求Servlet很难处理,怎么提前创建19.什么是JavaWeb中特别复杂的需求&#xff1f;20.为什么WebServlet可以代替配置文件&#xff1f;21.Tomcat 处理servlet流程22.web.xml的映…

计算机网络之路由协议(自治系统)

一、自治系统&#xff08;AS&#xff09; 自治系统是由同一个技术管理机构管理、使用统一选路策略的一些路由器的集合。它是网络的基本构成单位&#xff0c;每个自治系统是一个独立运营并自主决定与谁交换流量的实体。自治系统内部运行内部网关协议&#xff08;IGP&#xff09…

React Router v5 vs v6 路由配置对比

React Router v5 vs v6 路由配置对比 React Router 是 React 中最常用的路由库&#xff0c;从 v5 到 v6 版本&#xff0c;发生了较大变化。本文对比 React Router v5 和 React Router v6 的配置方式&#xff0c;帮助开发者顺利迁移。 1. 安装依赖 React Router v5 npm inst…