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:
class Solution {
public:
bool canJump(vector<int>& nums) {
if(nums.empty()){
return false;
}
// keep a indicator for current right most position we can reach
int right_most = ;
// loop to enumrate all elements
for(int ix = ; ix < nums.size(); ix++){
// if current element already exceed the right most position
// return false
if(right_most < ix){
return false;
} else {
// we already could reache the last element
if(ix + nums[ix] >= nums.size() - ){
return true;
} else {
// otherwise, update the right most position
right_most = max(ix + nums[ix], right_most);
}
}
}
return false;
}
};
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.
class Solution {
public:
// dynamic programming solution
bool canJump(vector<int>& nums) {
if (nums.empty()) {
return false;
}
int size = nums.size();
vector<bool> true_table(size, false);
true_table[] = true;
for(int i = ; i < nums.size(); i++){
for(int j = ; j < i; j++){
if(true_table[j] && nums[j] + j >= i){
true_table[i] = true;
break;
}
}
}
return true_table[size - ];
}
};
--------------------------------- 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)
class Solution {
public:
int jump(vector<int>& nums) {
if(nums.empty()){
return ;
}
int size = nums.size();
vector<bool> can_jump(size, false);
vector<int> min_jump(size, INT_MAX);
// initialize start status
can_jump[] = true;
min_jump[] = ;
// dynamic programming
for(int i = ; i < nums.size(); i++){
for(int j = ; j < i; j++){
if(can_jump[j] && nums[j] + j >= i){
can_jump[i] = true;
min_jump[i] = min(min_jump[i], min_jump[j] + );
}
}
}
// return end status
return min_jump[size - ];
}
};
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:
class Solution {
public:
int jump(vector<int>& nums) {
// initialize
if(nums.size() < ){
return ;
}
// variables
int cur_jump_right_most = nums[];
int next_jump_right_most = ;
int min_jump = ;
if(cur_jump_right_most >= nums.size() - ){
return min_jump;
}
// O(n)
for(int ix = ; ix < nums.size(); ix++){
if(ix > cur_jump_right_most){
// at boundary
// update the cur_jump_right_most position before next_jump_right_most
cur_jump_right_most = next_jump_right_most;
min_jump++;
}
next_jump_right_most = max(next_jump_right_most, nums[ix] + ix);
if(next_jump_right_most >= nums.size() - ){
return ++min_jump;
}
}
return min_jump;
}
};
最新文章
- SQL Server的AlwaysOn错误19456和41158
- 一个很全的VTK实例网址
- Linux inode && Fast Directory Travel Method(undone)
- http://10.11.112.12:8000/homePage.jsp?loginMode=JS
- JS闭包文章--(翻译)Callbacks in Loops
- Selenium2学习-000-Selenium2初识
- Poj(1511)，SPFA
- Android BroadcasetReceiver
- __block存储类型
- [推荐]ORACLE PL/SQL编程之四：把游标说透(不怕做不到，只怕想不到)
- 华为HG8245 电信 光猫破解获取超级密码
- Qt创建任务栏进度条
- Unity之显示fps功能
- ES6模块化操作
- Android Studio 修改Logcat的颜色
- caffe 中base_lr、weight_decay、lr_mult、decay_mult代表什么意思？
- Ajax请求：本地跨域的问题
- OpenLDAP搭建部署
- 用Drupal快速实现mobile平台服务端【转】
- 【ASP.NET Core】ASP.NET Core API 版本控制