新闻详情

新闻详情

首页 / 资讯中心 / 详情

跳跃游戏系列

发布时间:2026/11/18 1:53:47来源:尧图网络
跳跃游戏系列
引言这两道题属于贪心经典题型核心都是基于数组元素代表最大跳跃长度两道题题干相近但目标不同一题判断是否可达终点一题求到达终点的最小跳跃次数。基础篇跳跃游戏 I约束起始在下标 0nums [i] 代表当前位置向后最大跳跃距离判断是否能够到达最后一个下标。思路 1正向贪心方法维护max_reach记录当前能跳到的最远下标。遍历数组不断更新最远可达位置若遍历到某个位置i max_reach说明无法到达该位置直接返回 false若max_reach n-1可提前返回 true。复杂度时间 (O(n))空间 (O(1))class Solution { public: bool canJump(vectorint nums) { int max_reach 0; int n nums.size(); for(int i 0; i n; i){ if(i max_reach) return false; // 当前位置不可达 max_reach max(max_reach, i nums[i]); if(max_reach n-1) return true; } return true; } };思路 2动态规划方法dp[i]表示下标i是否可达。初始化dp[0]true遍历每个位置如果当前位置可达则标记它后续能跳到的位置全部可达。复杂度时间 (O(n^2))空间 (O(n))大数据会超时仅理解用。bool canJump(vectorint nums) { int n nums.size(); vectorbool dp(n, false); dp[0] true; for(int i0;in;i){ if(!dp[i]) continue; for(int j1;jnums[i];j){ if(ij n-1) return true; dp[ij] true; } } return dp[n-1]; }进阶篇跳跃游戏 II约束起始在下标 0nums [i] 代表当前位置向后最大跳跃距离保证一定可以到达终点求到达最后下标的最小跳跃次数。思路 1区间贪心方法维护 3 个变量当前区间边界end、全局最远可达位置max_reach、跳跃次数step。遍历到区间边界end时代表必须起跳一次更新边界为全局最远位置。复杂度时间 (O(n))空间 (O(1))class Solution { public: int jump(vectorint nums) { int n nums.size(); if(n 1) return 0; int step 0; int end 0; int max_reach 0; for(int i 0; i n-1; i){ max_reach max(max_reach, i nums[i]); if(i end){ // 走到区间边界必须起跳 step; end max_reach; } } return step; } };思路 2反向贪心方法从终点向前搜索找到最靠左的、能够跳到当前终点的位置更新终点为此位置跳跃次数 1直到终点回到下标 0。复杂度时间 (O(n^2))空间 (O(1))int jump(vectorint nums) { int pos nums.size()-1; int step 0; while(pos 0){ // 从左往右找第一个能跳到pos的下标 for(int i0; ipos; i){ if(i nums[i] pos){ pos i; step; break; } } } return step; }总结题号题目约束最优解法核心变量55跳跃游戏 I判断能否到达终点正向贪心max_reach45跳跃游戏 II求最小跳跃次数保证可达区间贪心end、max_reach、stepI只关心能不能到达 → 贪心维护最远可达下标II求最少跳跃次数 → 区间贪心到达区间边界才计数
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

【外设】之大彩串口显示屏 2026/11/17 7:04:08

【外设】之大彩串口显示屏

大彩串口屏初步使用 1 .官网下载 STM32 屏幕 GUI 设计资料 http://www.gz-dc.com/category/typeid/4112 找到 STM32 Keil 工程,移植相关代码因项目而异进行移植,由于项目简单,本人只对用到的指令接口进行修改。 比如:注意事项&…

阅读更多 →
无法下载Windows系统iso文件 2026/11/17 5:42:44

无法下载Windows系统iso文件

当我遇到这个问题的时候,我打开了一个网站: 登录 然后我打算下载的时候: 突然那个官方的连接就可以下载了:

阅读更多 →
【清华代码熊】DeepSeek V4.1 Flash 后训练详解 2026/11/17 19:43:34

【清华代码熊】DeepSeek V4.1 Flash 后训练详解

📌 上期解析了 DeepSeek V4.1 Flash 模型架构改进,本期解析 DeepSeek V4.1 Flash 预训练/后训练技术: 🌟 预训练:45T 文本 多模态混合语料、直接训练 sparse attention(取消 DeepSeek V4 的 dense 冷启动&…

阅读更多 →
Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ... 2026/11/17 6:55:04

Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ...

文章主要内容和创新点 主要内容 本文聚焦于多模态大语言模型(MLLM)强化学习(RL)训练中的效率问题,提出了一个名为Shuffle-R1的框架。研究发现,当前RL训练存在两个关键缺陷: 优势值坍缩(Advantage Collapsing):批次中大多数优势值集中在零附近,导致有效梯度信号被淹…

阅读更多 →
PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction 2026/11/17 5:57:47

PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction

一、文章主要内容总结 本文聚焦于利用大型语言模型(LLMs)实现个人身份信息(PII)脱敏的研究,旨在解决传统脱敏方法(如基于规则的系统、领域特定命名实体识别(NER)模型)泛化能力差、跨格式/跨语境适应性弱的问题。 研究通过全面评估多种LLM架构(包括密集型LLM(D-LLM…

阅读更多 →
LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model 2026/11/17 19:43:32

LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model

文章主要内容和创新点 主要内容 本文聚焦于二进制图像-文本相关性评估任务(判断图像与文本“相关”或“不相关”),针对该任务中文本格式多样、相关性定义随场景变化等挑战,提出了基于多模态大语言模型(MLLM)的解决方案LLaVA-RE。 模型设计:LLaVA-RE基于LLaVA 1.5架构,…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉