LeetCode - 45. Jump Game II

简介: 45. Jump Game II  Problem's Link  ---------------------------------------------------------------------------- Mean:  给定一个数组a,玩家的初始位置在idx=0,玩家需要到达的位置是idx=a.

45. Jump Game II 

Problem's Link

 ----------------------------------------------------------------------------

Mean: 

给定一个数组a,玩家的初始位置在idx=0,玩家需要到达的位置是idx=a.size()-1.

如果玩家在idx处,那么他最多可以向后走a[idx]步,问最少多少步可以走到终点.

analyse:

方法非常巧妙,类似于BFS.

Time complexity: O(N)

 

view code

/**
* -----------------------------------------------------------------
* Copyright (c) 2016 crazyacking.All rights steperved.
* -----------------------------------------------------------------
*       Author: crazyacking
*       Date  : 2016-03-08-14.52
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long( LL);
typedef unsigned long long( ULL);
const double eps( 1e-8);


class Solution
{
public :
    int jump( vector < int >& nums)
    {
        int i( 0 ), j( 1 ), steps( 0 ), N( nums . size());
        while( j < N)
        {
            int endj = min( nums [ i ] + i , N);
            while( j < = endj)
            {
                if( nums [ j ] + j > nums [ i ] + i)
                    i = j;
                j ++;
            }
            steps ++;
        }
        return steps;
    }
};

// this is my TLE code :(
//class Solution
//{
//public:
//    int jump(vector<int>& nums)
//    {
//        queue<pair<int,int>> que; // pos,step
//        int res=INT_MAX;
//        que.push(make_pair(0,0));
//        while(!que.empty())
//        {
//            pair<int,int> top=que.front();
//            que.pop();
//            if(top.first>=nums.size()-1)
//                res=min(res,top.second);
//            for(int i=1;i<=nums[top.first] && i+top.first<=nums.size();++i)
//            {
//                que.push(make_pair(top.first+i,top.second+1));
//            }
//        }
//        return res;
//    }
//};


int main()
{
    int n;
    while( cin >>n)
    {
        vector < int > ve;
        for( int i = 0; i <n; ++ i)
        {
            int tempVal;
            cin >> tempVal;
            ve . push_back( tempVal);
        }
        Solution solution;
        int ans = solution . jump( ve);
        cout << ans << endl;
    }
    return 0;
}
/*

*/
目录
相关文章
LeetCode 403. Frog Jump
一只青蛙想要过河。 假定河流被等分为 x 个单元格,并且在每一个单元格内都有可能放有一石子(也有可能没有)。 青蛙可以跳上石头,但是不可以跳入水中。 给定石子的位置列表(用单元格序号升序表示), 请判定青蛙能否成功过河(即能否在最后一步跳至最后一个石子上)。 开始时, 青蛙默认已站在第一个石子上,并可以假定它第一步只能跳跃一个单位(即只能从单元格1跳至单元格2)。 如果青蛙上一步跳跃了 k 个单位,那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1个单位。 另请注意,青蛙只能向前方(终点的方向)跳跃。
111 0
LeetCode 403. Frog Jump
LeetCode 390. Elimination Game
给定一个从1 到 n 排序的整数列表。 首先,从左到右,从第一个数字开始,每隔一个数字进行删除,直到列表的末尾。 第二步,在剩下的数字中,从右到左,从倒数第一个数字开始,每隔一个数字进行删除,直到列表开头。 我们不断重复这两步,从左到右和从右到左交替进行,直到只剩下一个数字。 返回长度为 n 的列表中,最后剩下的数字。
101 0
LeetCode 390. Elimination Game
LeetCode 292. Nim Game
你和你的朋友,两个人一起玩 Nim游戏:桌子上有一堆石头,每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。 你们是聪明人,每一步都是最优解。 编写一个函数,来判断你是否可以在给定石头数量的情况下赢得游戏。
74 0
LeetCode 292. Nim Game
|
存储 算法
LeetCode 289. Game of Life
如果活细胞周围八个位置的活细胞数少于两个,则该位置活细胞死亡; 如果活细胞周围八个位置有两个或三个活细胞,则该位置活细胞仍然存活; 如果活细胞周围八个位置有超过三个活细胞,则该位置活细胞死亡; 如果死细胞周围正好有三个活细胞,则该位置死细胞复活;
76 0
LeetCode 289. Game of Life
|
算法 索引
LeetCode 55. Jump Game
给定一个非负整数数组,您最初定位在数组的第一个索引处。 数组中的每个元素表示该位置的最大跳转长度。 确定您是否能够到达最后一个索引。
90 0
LeetCode 55. Jump Game
|
算法 索引
LeetCode 45. Jump Game II
给定一个非负整数数组,初始位置在索引为0的位置,数组中的每个元素表示该位置的能够跳转的最大部署。目标是以最小跳跃次数到达最后一个位置(索引)。
80 0
LeetCode 45. Jump Game II
LeetCode contest 200 5476. 找出数组游戏的赢家 Find the Winner of an Array Game
LeetCode contest 200 5476. 找出数组游戏的赢家 Find the Winner of an Array Game
|
决策智能
LeetCode之Nim Game
LeetCode之Nim Game
120 0
|
C++
LeetCode 289 Game of Life(生命游戏)(Array)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/52122735 翻译 根据维基百科的文章介绍:“Game of Life,简称为Life,是一个被英国数学家John Conway在1970年提出的细胞自动分裂器。
1638 0