[LeetCode] Jump Game II
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.)
f[i,j]表示 从i 到j 的步骤,
f[i,j] = min{ f[i,k] + 1, if(A[k] > j-k)}
我们可以用f[j] 表示上述的f[0,j ] ,所以状态转移为:f[j] = min{ f[k] + 1, if(A[k] > j-k)}
第一次的版本,居然 Status:Runtime Error,后来查看,由于内存泄露引起的,f申请的堆内存没有释放。
class Solution { public: int jump(int A[], int n) { int* f = new int(n); f[0] = 0; for(int i = 1; i < n; i++) f[i] = INT_MAX; for(int i = 1; i < n; i++) { for(int j = 0; j < i; j++) { if(A[j] >= (i-j))// can jump from j to i f[i] = min(f[i], f[j] + 1); } } //printArray(f, n); return f[n-1]; } };
第二版本:用vecotr 代替 堆申请内存, 但是 Submission Result: Time Limit Exceeded
Submission Result: Time Limit ExceededMore Details
class Solution { public: int jump(int A[], int n) { vector<int> f; f.resize(n); f[0] = 0; for(int i = 1; i < n; i++) f[i] = INT_MAX; for(int i = 1; i < n; i++) { for(int j = 0; j < i; j++) { if(A[j] >= (i-j))// can jump from j to i f[i] = min(f[i], f[j] + 1); } } return f[n-1]; } };
方法3,贪心法 copy from https://github.com/haoel/leetcode/blob/master/src/jumpGame/jumpGame.II.cpp
比如第一步能走2, 那么久从A[1] +1 和 A[2] + 2 中选取最大的,这样持续下去,
不如array A = [2,3,1,1,4],A[1]+1 = 4, A[2]+2 = 3 所以选择1,因为从A[1]出发覆盖的范围更大,下次从A[1]出发,A[1]覆盖的范围是3, 那么就是A[2]+2,A[3]+3,A[4]+4 中选大的,迭代下去。。
class Solution { public: //Acutally, using the Greedy algorithm can have the answer int jump(int A[], int n) { if (n<=1) return 0; int steps = 0; int coverPos = 0; for (int i=0; i<=coverPos&& i<n; ){ if (A[i]==0) return -1; if(coverPos < A[i]+i){ coverPos = A[i]+i; steps++; } if (coverPos >= n-1){ return steps; } //Greedy: find the next place which can have biggest distance int nextPos=0; int maxDistance=0; for(int j=i+1; j<=coverPos; j++){ if ( A[j]+j > maxDistance ) { maxDistance = A[j]+j; nextPos = j; } } i = nextPos; } return steps; } };
贪心2,好理解点的算法
class Solution { public: int jump(int A[], int n) { if(n == 1) return 0; //只有一个元素,只需啊0步骤 int maxReach = 0;// the most rigth we can reach int steps = 0; for(int i = 0; i <= maxReach ; /* i++ */)//i means current position { steps ++; int newMaxReach = 0; for(int j = i; j <= maxReach && j < n; j++ )// count i { if(A[j] + j > newMaxReach) { newMaxReach = A[j] + j; i = j + 1; // begin with j+1 } } if(newMaxReach >= n-1) { return steps; } else if(newMaxReach > maxReach) { // update the maxReach maxReach = newMaxReach; } } return 0; } };
相关文章
- Leetcode: Wiggle Sort II
- Leetcode: Trapping Rain Water II
- Leetcode: Ugly Number II
- Leetcode: Strobogrammatic Number II
- Leetcode: Reverse Linked List II
- LeetCode 221. 最大正方形
- 186、【栈与队列】leetcode ——503. 下一个更大元素 II(C++版本)
- 【LeetCode】219. Contains Duplicate II
- [LeetCode] 1339. Maximum Product of Splitted Binary Tree 分裂二叉树的最大乘积
- [LeetCode] 1057. Campus Bikes 校园自行车
- [LeetCode] 932. Beautiful Array 漂亮数组
- [LeetCode] 881. Boats to Save People 渡人的船
- [LeetCode] 770. Basic Calculator IV 基本计算器之四
- [LeetCode] Employee Free Time 职员的空闲时间
- [LeetCode] 723. Candy Crush 糖果消消乐
- [LeetCode] 92. Reverse Linked List II 倒置链表之二
- [LeetCode] 142. Linked List Cycle II 单链表中的环之二
- [LeetCode] 107. Binary Tree Level Order Traversal II 二叉树层序遍历之二