首页 > 代码库 > 55 Jump Game i && 45 Jump Game ii
55 Jump Game i && 45 Jump Game ii
Jump Game
Problem statement:
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.
Analysis:
There are two solutions for this problem, one is greedy, another is dynamic programming. The main difference is the direction.
Solution one:
Greedy is the best solution for this problem, it is always forwarding(AC) O(n).
- Loop the whole array
- Keep a right most position where I can get, update it at each index.
- if right most position is always greater than current index or it is already exceed the last position of array, return true since we can get the last position
- Once current index is greater than right most position, return false, since there is already no way to get there.
The code is as following:
1 class Solution { 2 public: 3 bool canJump(vector<int>& nums) { 4 if(nums.empty()){ 5 return false; 6 } 7 8 // keep a indicator for current right most position we can reach 9 int right_most = 0;10 11 // loop to enumrate all elements12 for(int ix = 0; ix < nums.size(); ix++){ 13 // if current element already exceed the right most position14 // return false15 if(right_most < ix){16 return false;17 } else {18 // we already could reache the last element19 if(ix + nums[ix] >= nums.size() - 1){20 return true;21 } else {22 // otherwise, update the right most position23 right_most = max(ix + nums[ix], right_most);24 }25 }26 }27 return false;28 }29 };
Solution two(NOT AC):
Dynamic programming O(n*n)
For dynamic programming, we looks back, for each element, we enumerate all the element whose index is lower than it, and check if it is reachable.
1 class Solution { 2 public: 3 // dynamic programming solution 4 bool canJump(vector<int>& nums) { 5 if (nums.empty()) { 6 return false; 7 } 8 int size = nums.size(); 9 vector<bool> true_table(size, false);10 true_table[0] = true;11 for(int i = 1; i < nums.size(); i++){12 for(int j = 0; j < i; j++){13 if(true_table[j] && nums[j] + j >= i){14 true_table[i] = true;15 break;16 }17 }18 }19 return true_table[size - 1];20 }21 };
--------------------------------- divide line --------------------------------------------
Jump Game ii
Problem Statement:
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.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
Note: You can assume that you can always reach the last index.
Analysis:
The main difference between jump game i && ii is that we should keep a minimum jump array for each element and update it for each element.
Solution one: Greedy
This is the accepted solution.
Solution two: Dynamic programming(NOT AC)
1 class Solution { 2 public: 3 int jump(vector<int>& nums) { 4 if(nums.empty()){ 5 return 0; 6 } 7 int size = nums.size(); 8 vector<bool> can_jump(size, false); 9 vector<int> min_jump(size, INT_MAX);10 // initialize start status11 can_jump[0] = true;12 min_jump[0] = 0;13 // dynamic programming14 for(int i = 1; i < nums.size(); i++){15 for(int j = 0; j < i; j++){16 if(can_jump[j] && nums[j] + j >= i){17 can_jump[i] = true;18 min_jump[i] = min(min_jump[i], min_jump[j] + 1);19 }20 }21 }22 // return end status23 return min_jump[size - 1];24 }25 };
Solution two: Greedy(AC)
we keep two variables, the first one is the most right position in current jump, the second one is the right most position in next jump.
Just one loop to get the final solution:
1 class Solution { 2 public: 3 int jump(vector<int>& nums) { 4 // initialize 5 if(nums.size() < 2){ 6 return 0; 7 } 8 // variables 9 int cur_jump_right_most = nums[0];10 int next_jump_right_most = 0;11 int min_jump = 1;12 if(cur_jump_right_most >= nums.size() - 1){13 return min_jump;14 }15 // O(n)16 for(int ix = 1; ix < nums.size(); ix++){17 if(ix > cur_jump_right_most){18 // at boundary 19 // update the cur_jump_right_most position before next_jump_right_most20 cur_jump_right_most = next_jump_right_most;21 min_jump++;22 }23 next_jump_right_most = max(next_jump_right_most, nums[ix] + ix);24 if(next_jump_right_most >= nums.size() - 1){25 return ++min_jump;26 }27 }28 return min_jump;29 }30 };
55 Jump Game i && 45 Jump Game ii