这个题事实上非常easy的,我一開始想复杂了,它没要求记录路径,事实上仅仅要看一下每一步之后所能延伸到的最远的位置就能够了,在这一个最远位置前面的那些位置,都是能够到达的,假设扫到了某个i,它大于当前能延伸到到的最远位置,说明这个i不可达。终于的位置能不能到达,就看终于延伸到的位置能不能大于等于它。
class Solution {
public:
bool canJump(int A[], int n) {
if(n == 0)
return false;
if(n == 1)
return true;
int mmax = 0;
for(int i=0;i<n-1&&i<=mmax;i++){
if(i+A[i]>mmax)
mmax = i+A[i];
if(mmax>=n-1)
return true;
}
return false;
}
};
leetcode第一刷_Jump Game的更多相关文章
-
leetcode第一刷_Jump Game II
要求最小的步数,是不是非常easy想到用dp啊? 我一開始的做法是,当找到了一个可以从它延伸到更远的位置,就把这个位置和最远位置的步数都更新一下,结果超时了. 事实上这样不仅是超时的,并且是错误的.由 ...
-
leetcode第一刷_Set Matrix Zeroes
这个题乍一看非常easy,实际上还挺有技巧的.我最開始的想法是找一个特殊值标记.遇到一个0,把他所相应的行列中非零的元素标记成这个特殊值.0值保持不变,然后再从头遍历一次,碰到特殊值就转化成0. 问题 ...
-
leetcode第一刷_Permutations II
当有反复元素的时候呢? 不用拍脑袋都会想到一种方法,也是全部有反复元素时的通用处理方法,维护一个set,假设这个元素没增加过就增加,增加过了的忽略掉.可是,在这道题上这个通用方法竟然超时了! 怎么办? ...
-
leetcode第一刷_Populating Next Right Pointers in Each Node II
很自然的推广,假设去掉全然二叉树的条件呢?由于这个条件不是关键,因此不会影响整体的思路.做法依旧是每次找到一层的起点,然后一层一层的走. 假设是全然二叉树的话,每层的起点就是上一层起点的左孩子,兄弟之 ...
-
leetcode第一刷_Merge Intervals
看到这个题我就伤心啊,去微软面试的时候,第一个面试官让我做的题目就是实现集合的交操作,这个集合中的元素就像这里的interval一样.是一段一段的.当时写的那叫一个慘不忍睹.最后果然被拒掉了. .好好 ...
-
leetcode第一刷_N-Queens
八皇后问题应该是回溯法的教学典范.在本科的时候,有一门课叫面向对象.最后的附录有这个问题的源码.当时根本不懂编程,照抄下来,执行一下出了结果都非常开心,哎. 皇后们的限制条件是不能同行同列,也不能同对 ...
-
leetcode第一刷_Gray Code
说到格雷码,应该没人不知道,详细它有什么用,我还真不是非常清楚,我室友应该是专家.生成的规律不是非常明显,之前看到帖子讲的,这会儿找找不到了.. 思想是这种,假设有n位,在第2^(n-1)个编码以下画 ...
-
leetcode第一刷_Combination Sum Combination Sum II
啊啊啊啊.好怀念这样的用递归保存路径然后打印出来的题目啊.好久没遇到了. 分了两种,一种是能够反复使用数组中数字的,一种是每一个数字仅仅能用一次的.事实上没有多大差别,第一种每次进入递归的时候都要从头 ...
-
leetcode第一刷_Count and Say
水题. 描写叙述的还挺麻烦的,实际上就是纸老虎,用两个string,一个存上一轮的结果,一个用来更新出这一轮的结果,每次扫描上一轮,统计一个字符出现的次数,然后把这个次数和字符增加到这一轮的字符串中就 ...
随机推荐
-
Python Day10
进程 在python中multiprocess模块提供了Process类,实现进程相关的功能.但是,由于它是基于fork机制的,因此不被windows平台支持.想要在windows中运行,必须使用if ...
-
Linux下Gcc生成和使用静态库和动态库详解(转)
一.基本概念 1.1什么是库 在windows平台和linux平台下都大量存在着库. 本质上来说库是一种可执行代码的二进制形式,可以被操作系统载入内存执行. 由于windows和linux的平台不同( ...
-
JS实现日程安排 日程安排插件
代码: <%@ Page Language="C#" AutoEventWireup="true" CodeBehind="EmpWeekPla ...
-
windows 程序的本体与操作系统之间的关系
WinMain(hInst,hPrev,……) { MSG msg; RegisterClass(……); CreateWindow(……); ShowWindow(……); UpdateWindow ...
-
(二)再议MII、RMII、GMII接口
概述: MII (Media Independent Interface(介质无关接口)或称为媒体独立接口,它是IEEE-802.3定义的以太网行业标准.它包括一个数据接口和一个MAC ...
-
C语言程序设计第五次作业——循环结构
(一)改错题 1.题目:输出华氏摄氏温度转换表:输入两个整数lower和upper,输出一张华氏摄氏温度转换表,华氏温度的取值范围是{lower,upper},每次增加2℉.计算公式如下: c = 5 ...
-
OAuth2实现单点登录SSO
1. 前言 技术这东西吧,看别人写的好像很简单似的,到自己去写的时候就各种问题,“一看就会,一做就错”.网上关于实现SSO的文章一大堆,但是当你真的照着写的时候就会发现根本不是那么回事儿,简直让人抓 ...
-
Neural Network Programming - Deep Learning with PyTorch - YouTube
百度云链接: 链接:https://pan.baidu.com/s/1xU-CxXGCvV6o5Sksryj3fA 提取码:gawn
-
Java接口的幂等性设计
转载:https://www.cnblogs.com/jack87224088/p/8688948.html 在微服务架构下,我们在完成一个订单流程时经常遇到下面的场景: 一个订单创建接口,第一次调用 ...
-
delphi 控制音量 静音的类
delphi 控制音量 静音的类 unit ttSound; interface uses winapi.windows, winapi.Messages; type SimpleSoundContr ...