文档章节

403. Frog Jump

cofama
 cofama
发布于 2017/04/17 20:28
字数 711
阅读 9
收藏 0

原题链接

Given a list of stones' positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit. If the frog's last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.

题目大意是青蛙要过河,河上分布着间距不等的石头,青蛙一开始在第一块石头上,它需要每步都跳在石头上才能过河。如果青蛙上一次跳跃的距离为k,那么这次它的跳跃距离只能为k-1、k或k+1。规定第一次跳跃距离为1。给出的数组是排好序的石头坐标,可以理解为与起点的距离。

我最开始的想法是判断下一块石头与当前石头的距离是否是k-1、k、k+1中的一个,如果是的话就更新k,如此重复进行;如果不是的话就返回false。但是这种方法有缺陷,就是青蛙不一定是一个接着一个跳的,可能是隔了几个石头跳的。例如[0,1,3,5,6,8,12,17]这个例子,如果按照我的判断方法,从8不能跳到12,那么就返回false了。而实际上,青蛙可以按0-1-3-5-8-12-17这样跳。

所以,不应只判断下一块石头与当前石头的距离,而是计算通过k-1、k、k+1分别能从当前石头到达哪些位置。另外,当前石头的k值也可能不止一个,因为可以从不同的位置到达当前石头。如果有石头能跳到终点(或者说终点的k值个数大于0),就返回true。因为石头要与它的k值一一对应,所以很自然地想到用map结构。下面是解答代码:

class Solution {
public:
    bool canCross(vector<int>& stones) {
        if(stones[1]!=1) return false;
        unordered_map<int, unordered_set<int>> lastjump;
        lastjump[0].insert(0);
        lastjump[1].insert(1);
        
        for(int i=1; i<stones.size()-1; i++) {
            for(int jump : lastjump[stones[i]]) {
                lastjump[stones[i]+jump].insert(jump);
                lastjump[stones[i]+jump+1].insert(jump+1);
                if(jump-1>0) lastjump[stones[i]+jump-1].insert(jump-1);
            }
        }
        return lastjump[stones.back()].size();
    }
};

lastjump是存储石头位置与其对应的上一步跳跃距离,跳跃距离用一个set保存。值得一提的是,我最初的代码是用map<int, vector<int>>存储的,但是会memory limited exceed。map与unordered_map的区别是,前者基于红黑树,后者基于哈希表。这个代码还有改进的空间,例如lastjump[stones[i]+jump].insert(jump)这一句,stones[i]+jump的位置上不一定有石头,可以增加一个判断,如果不存在石头,就不用insert了。这个算法的时间和空间复杂度应该都是O(n^2)。

官方解答

© 著作权归作者所有

共有 人打赏支持
上一篇: 57. Insert Interval
下一篇: 133. Clone Graph
cofama
粉丝 0
博文 24
码字总数 19162
作品 0
广州
程序员
私信 提问
内容管理程序--Frog CMS

Frog CMS 是一款内容管理程序,它有着十分美观的用户界面、可塑性强的模板化页面、简单的用户和权限管理程序、以及作为CMS所必须的文件管理功能。Frog CMS 诞生于2007年,原名phpRadiant,是...

匿名
2009/08/19
3.1K
0
马克.吐温的青蛙

1865年,马克.吐温30岁。 据说他在那一年,受到一只青蛙的启发,写出了著名的幽默小说《卡拉韦拉斯县驰名的跳蛙》,从此一举成名,开始了大作家生涯。 据有关说法,这只启发马克.吐温灵感的青...

阮一峰
2003/12/04
0
0
web jsp游戏编程

<%@ page language="java" import="java.util.*" pageEncoding="gbk"%> <% String path = request.getContextPath(); String basePath = request.getScheme()+"://"+request.getServerName()......

一个轮回
2014/06/11
129
1
jQuery UI 1.11.3 发布,jQuery 的 UI 框架

jQuery UI 1.11.3 发布,这是一个维护版本,修复了 Core, Position, Resizable, Sortable, Accordion, Datepicker, Selectmenu, Slide, and Tabs 等模块的相关 bug,完整记录请看 changelog.......

oschina
2015/02/13
8.6K
9
jQuery UI 1.11.2 发布

jQuery UI 1.11.2 发布,此版本包括 Mouse, Widget Factory, Draggable, Droppable, Sortable, Accordion, Datepicker, Menu, Selectmenu, Slider, Tabs 和 Tooltips 的 bug 修复,详细更新内......

oschina
2014/10/17
4.8K
4

没有更多内容

加载失败,请刷新页面

加载更多

dockerfile 镜像构建(1)

通用dockerfile 利用已经编译好的.jar 来构建镜像。要构建的目录如下: [root@iZuf61quxhnlk9m2tkx16cZ demo_jar]# docker build -t demo:1 . 运行镜像: [root@iZuf61quxhnlk9m2tkx16cZ de...

Canaan_
20分钟前
0
0
Redis radix tree源码解析

Redis实现了不定长压缩前缀的radix tree,用在集群模式下存储slot对应的的所有key信息。本文将详述在Redis中如何实现radix tree。 核心数据结构 raxNode是radix tree的核心数据结构,其结构体...

阿里云云栖社区
23分钟前
5
0
vue import 传入变量

在做动态添加component的时候,传入变量就会报错,出现以下错误信息: vue-router.esm.js?fe87:1921 Error: Cannot find module '@/components/index'. at eval (eval at ./src/components ......

朝如青丝暮成雪
25分钟前
0
0
Flutter开发 Dio拦截器实现token验证过期的功能

前言: 之前分享过在Android中使用Retrofit实现token失效刷新的处理方案,现在Flutter项目也有“token验证过期”的需求,所以接下来我简单总结一下在Flutter项目中如何实现自动刷新token并重...

EmilyWu
26分钟前
6
0
final Map可以修改内容,final 常量不能修改

1.final Map 可以put元素,但是不可以重新赋值 如: final Map map = new HashMap(); map = new HashMap();//不可以 因为栈中变量map引用地址不能修改 2.final str = “aa”; str = "bb";/......

qimh
29分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部