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 contest 200 5476. 找出数组游戏的赢家 Find the Winner of an Array Game
LeetCode contest 200 5476. 找出数组游戏的赢家 Find the Winner of an Array Game
LeetCode 403. Frog Jump
一只青蛙想要过河。 假定河流被等分为 x 个单元格,并且在每一个单元格内都有可能放有一石子(也有可能没有)。 青蛙可以跳上石头,但是不可以跳入水中。 给定石子的位置列表(用单元格序号升序表示), 请判定青蛙能否成功过河(即能否在最后一步跳至最后一个石子上)。 开始时, 青蛙默认已站在第一个石子上,并可以假定它第一步只能跳跃一个单位(即只能从单元格1跳至单元格2)。 如果青蛙上一步跳跃了 k 个单位,那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1个单位。 另请注意,青蛙只能向前方(终点的方向)跳跃。
79 0
LeetCode 403. Frog Jump
LeetCode 390. Elimination Game
给定一个从1 到 n 排序的整数列表。 首先,从左到右,从第一个数字开始,每隔一个数字进行删除,直到列表的末尾。 第二步,在剩下的数字中,从右到左,从倒数第一个数字开始,每隔一个数字进行删除,直到列表开头。 我们不断重复这两步,从左到右和从右到左交替进行,直到只剩下一个数字。 返回长度为 n 的列表中,最后剩下的数字。
73 0
LeetCode 390. Elimination Game
LeetCode 292. Nim Game
你和你的朋友,两个人一起玩 Nim游戏:桌子上有一堆石头,每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。 你们是聪明人,每一步都是最优解。 编写一个函数,来判断你是否可以在给定石头数量的情况下赢得游戏。
55 0
LeetCode 292. Nim Game
|
存储 算法
LeetCode 289. Game of Life
如果活细胞周围八个位置的活细胞数少于两个,则该位置活细胞死亡; 如果活细胞周围八个位置有两个或三个活细胞,则该位置活细胞仍然存活; 如果活细胞周围八个位置有超过三个活细胞,则该位置活细胞死亡; 如果死细胞周围正好有三个活细胞,则该位置死细胞复活;
49 0
LeetCode 289. Game of Life
|
算法 索引
LeetCode 55. Jump Game
给定一个非负整数数组,您最初定位在数组的第一个索引处。 数组中的每个元素表示该位置的最大跳转长度。 确定您是否能够到达最后一个索引。
72 0
LeetCode 55. Jump Game
|
算法 索引
LeetCode 45. Jump Game II
给定一个非负整数数组,初始位置在索引为0的位置,数组中的每个元素表示该位置的能够跳转的最大部署。目标是以最小跳跃次数到达最后一个位置(索引)。
50 0
LeetCode 45. Jump Game II
|
决策智能
LeetCode之Nim Game
LeetCode之Nim Game
102 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年提出的细胞自动分裂器。
1608 0

热门文章

最新文章