Leetcode No.55(Jump Game) 心得(Medium)

題目:
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.

想法:
這是我的第一題 Medium 題目,果然難度有往上提升。
這題第一個想法就是 BackTracking,也就是用 recursive 的方法去遍巡每個 index 的所有可能,可以用像是 DFS 的方法先從跳到最後的地方開始找。這個時間複雜度很高放棄。

再來我就想到假設 k 能跳到終點,那所有能跳到 k 的 index 也都能跳到終點。所以從後面往前面找,並且有個 table 記錄這個 index 可否跳到下個記錄成功的 index。第一個記錄成功的 index 就是 vec.size()-1。

後來我參考網路上的答案,再寫出第二份解答。
這個方法是貪婪法。也就是一個個 index 往下找,搜尋範圍到目前能跳到最遠的 index。因為你能跳到最遠的 index,代表這之前的 index 都能跳到,搜尋這之中能不能跳到更遠的 index。能跳到最尾端或者超過就算成功。
時間複雜度: O(n²)

解法一:

class Solution {
public:
 bool canJump(vector<int>& nums) {
 int size = nums.size();
 if (size == 1)
 return true;
 
 std::vector<int> vec(nums.size(), 0);
 vec[size — 1] = 1;
 for (int i = nums.size() — 2; i > 0; i — ) {
 int depth = nums[i];
 while (depth != 0) {
 if (i + depth >= size — 1 || vec[i + depth] == 1) {
 vec[i] = 1;
 break;
 }
 depth — ;
 }
 }
 for (int i = 1; i <= nums[0]; i++) {
 if (vec[i] == 1)
 return true;
 }
 return false;
 }
};

解法二:

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

網路上解答:
網路上有另一個版本的貪婪法,而且比較好。
他的概念是我的解法二的改良,因為每個 index 都會去尋找他能跳得點是不是成功的點,如果index 5 他能跳到 index 10,假設 index 8 是成功的點,那可以得知 index 5 也是成功的點。也就是本來要一個 table 記錄每個 index 是不是成功的點,現在只要用一個變數記錄目前找到最左邊成功的點,因為你只要能跳 ≥ 這個成功點,就代表你是成功點。

public class Solution {
public boolean canJump(int[] nums) {
int lastPos = nums.length - 1;
for (int i = nums.length - 1; i >= 0; i--) {
if (i + nums[i] >= lastPos) {
lastPos = i;
}
}
return lastPos == 0;
}
}

值得一提的是:
BackTracking的複雜度是 O(2^n). 這個很難想,我下面就貼程式。
證明的連結: https://leetcode.com/problems/jump-game/solution/​​

簡單描述一下證明:
假設 T(x) 是 x position 的所有搜尋次數。 Ex: T(n) = 1;
T(x) = T(x+1) + T(x+2) + …. + T(n);
T(x+1) = T(x+2) + …. + T(n);
T(x) = T(x+1) +[T(x+2) + …. + T(n)];
T(x) = T(x+1) + T(x+1);
T(x) = 2 * T(x+1);
.
.
.
T(x) = 2^(n-x-1)

T(1) 大約等於 2^n * T(n) = O(2^n)

public class Solution {
public boolean canJumpFromPosition(int position, int[] nums) {
if (position == nums.length - 1) {
return true;
}

int furthestJump = Math.min(position + nums[position], nums.length - 1);
for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {
if (canJumpFromPosition(nextPosition, nums)) {
return true;
}
}

return false;
}

public boolean canJump(int[] nums) {
return canJumpFromPosition(0, nums);
}
}