LeetCodeのjumpgame

2840 ワード

Descrition: Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. For example: A = [2,3,1,1,4], return true. A = [3,2,1,0,4], return false.
注:本シリーズのテーマはすべてローカルVS 2015で実行されます.
タイトルの分析:毎回貪欲なのは現在位置でreachの到達する最大の距離を記録することができて、それからi
//
#include
#include
#include

using namespace std;

class Solution {
public:
    bool jumpgame(const vector<int>& nums) {
        if (nums.size() == 0) return false;
        if (nums.size() == 1) return true;
        int reach = 1;
        for (int i = 0; i < reach && reach < nums.size();++i) {
            reach = max(reach,i +1+nums[i]);
        }
        return reach >= nums.size();
    }
};

int main(int argc,char** argv) {

    vector<int> nums = {3,1,1,1,0,0,0,4};
    Solution test;
    cout << test.jumpgame(nums) << endl;
    system("pause");
    return 0;
}

結果は以下の通りである:入力numsが{3,1,1,1,0,0,4}の場合falseを返す;入力されたnumsが{2,1,1,3,4,0,1,3}の場合、trueが返されます.