LeetCode—55.ジャンプゲーム(Jump Game)——分析とコード(C++)

LeetCode—55.ジャンプゲーム[Jump Game]——分析とコード[C++]

一、テーマ

二、分析及びコード

1. 欲張り

(1)考え方

(2)コード(簡潔)

(3)コード(高効率)

(4)結果

三、その他

一、テーマ
非負の整数配列を指定すると、最初に配列の最初の位置に位置します.
配列内の各要素は、その位置でジャンプできる最大長を表します.
あなたが最後の位置に着くかどうかを判断します.
例1:

  : [2,3,1,1,4]
  : true
  :        1  ，    0       1,        1   3          。

例2:

  : [3,2,1,0,4]
  : false
  :     ，         3    。             0 ，                 。

ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/jump-game著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
二、分析及びコード
1.欲張り
(1)考え方
この問題の構想は非常に直観的で、1つの明らかな特性に基づいて:もし1つの位置が到着することができるならば、それではこの位置の左側のすべての位置はすべて到着することができます.解法を得ることができます:遍歴の過程の中で、1つの数で現在到達できる最も遠い位置を記録すればいいです.
(2)コード(簡潔)

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

(3)コード(効率)

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxPosi = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (maxPosi < i)
                return false;
            if (maxPosi < i + nums[i])
                maxPosi = i + nums[i];
        }
        return true;
    }
};

(4)結果
(簡潔版)実行用時間:12 ms、すべてのC++コミットで84.28%のユーザーを破った.メモリ消費量:9.9 MB;(効率版)実行用時間:8 ms、すべてのC++コミットで97.90%のユーザーを破った.メモリ消費量:9.8 MBで、すべてのC++コミットで85.15%のユーザーを破った.
三、その他
しばらくありません.