一個(gè)數(shù)組存儲(chǔ)了非負(fù)整型數(shù)據(jù)，數(shù)組中的第i個(gè)元素a[i]，代表了可以從數(shù)組第i個(gè) 位置最多向前跳躍a[i]步;已知數(shù)組各元素的情況下，求是否可以從數(shù)組的第0個(gè)位置跳躍到數(shù)組的最后一個(gè)元素的位置，返回是true或者false判斷是否能夠跳躍到結(jié)尾

例如:
nums = [2, 3, 1, 1, 4] ，可以從nums[0] = 2 跳躍至 nums[4] = 4;
nums = [3, 2, 1, 0, 4] ，不可以從nums[0] = 3 跳躍至 nums[4] = 4

1. 貪心規(guī)律：
   想要判斷最終是否能夠跳躍到終點(diǎn)，最快的辦法即選擇每次跳躍獲取到的跳躍范圍中最大的跳躍點(diǎn)；
   比如：nums = [2 3 1 1 4]
   第一次跳 為2，那么接下來(lái)可以跳一次，跳到nums[1] = 3;或者跳躍2次，nums[2] = 1
   如何選擇第二次跳呢，根據(jù)貪心算法，我們想要更快得完成任務(wù)，優(yōu)先選擇能夠跳的次數(shù)最多的點(diǎn)，即nums[1]，因?yàn)樗軌蛟诘诙翁?次，但是nums[2]只能跳1次

   所以，貪心規(guī)律即為 每次跳躍的落點(diǎn)，為接下來(lái)可跳躍范圍中最大的值；站在巨人的肩膀上可以跳得更遠(yuǎn)。

2. 迭代策略：

   1. 求從第i位置最遠(yuǎn)可跳至第index[i]位置: 根據(jù)從第i位置最遠(yuǎn)可跳nums[i]步: index[i] = nums[i] + i;
   2. 初始化:
      1)設(shè)置變量jump代表當(dāng)前所處的位置，初始化為0;
      2)設(shè)置變量max_index代表從第0位置至第jump位置這個(gè)過(guò)程中，最遠(yuǎn)可到達(dá)的位置，
      初始化為index[0]。
   3. 利用jump掃描index數(shù)組，直到j(luò)ump達(dá)到index數(shù)組尾部或jump超過(guò)max_index，掃描過(guò)程中， 更新max_index。
   4. 若最終jump 為數(shù)組長(zhǎng)度，則返回true，否則返回false。

實(shí)現(xiàn)算法如下:

bool judge_finish(vector<int> &stage) {vector<int> index;/*構(gòu)造最遠(yuǎn)跳至的 index列表*/for (int i = 0; i < stage.size(); ++i) {index.push_back(i + stage[i]);}int max_index = stage[0];int jump = 0;/*篩選條件為要求為jump達(dá)到數(shù)組尾且 jump不能超過(guò)index數(shù)組，否則當(dāng)前道路為不可達(dá)*/while(jump < index.size() && jump <= max_index) {if (max_index < index[jump]) {max_index = index[jump];}jump ++;}/*當(dāng) jump達(dá)到數(shù)組尾，即此時(shí)已經(jīng)能夠走完*/if (jump == index.size()) {return true;}return false;
}

測(cè)試代碼如下:

#include <iostream>
#include <vector>using namespace std;bool judge_finish(vector<int> &stage) {vector<int> index;for (int i = 0; i < stage.size(); ++i) {index.push_back(i + stage[i]);}int max_index = stage[0];int jump = 0;while(jump < index.size() && jump <= max_index) {if (max_index < index[jump]) {max_index = index[jump];}jump ++;}if (jump == index.size()) {return true;}return false;
}int main() {vector<int> s;int tmp;cout << "input arr " <<endl;for (int i =0;i < 5; ++i) {cin >> tmp;s.push_back(tmp);}cout << "the true or false that judge the result is " << judge_finish(s) << endl;return 0;
}

輸出如下:

input arr 
3 2 2 0 5
the true or false that judge the result is 1

總結(jié)

以上是生活随笔為你收集整理的贪心：Jump Game 跳跃游戏的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。