55 jump game
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.
测试用例：
Example 1:
Input:[2,3,1,1,4]
Output:true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input:[3,2,1,0,4]
Output:false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
经典算法分类：这道题目可以分类到动态规划中，当然还有贪心和回溯的解法。
题目思考：给定一个非负数组，难点在于记录从上一点到下一点的跳跃能力转换。
动态规划的思路：建立一个dp数组，建立上一个元素和下一个元素的关系（类似阶跃函数）。找到最远的那个位置，并记录下来。
想清楚怎么转换就可以直接写了。
代码：
public boolean canJump(int[] nums) {
int len = nums.length;
int dp[] = new int[len];
dp[0] = nums[0];
for(int i = 1; i < len; i ++){
if(i <= dp[i-1]){
dp[i] = Math.max(dp[i-1],i + nums[i]);
}
else{
dp[i] = dp[i-1] + nums[i];
/*update the value of the array dp*/
}
}
return dp[len-1]>=len-1;
}
}
问题：跑不过[3,2,1,0,4]这个测试用例。哪里出了问题？
贪心版本：
思路：记录现在能跳到的最远距离。
public boolean canJump(int[] nums) {
int len = nums.length;
int dp[] = new int [len];
int max = nums[0];
for(int i = 1;i < len; i++){
if(i > max || max >= len-1){
return max >= len -1;
}
max = Math.max(max, i + nums[i]);
}
return max >= len -1;
}
}
Runtime: 8 ms, faster than 65.15% of Java online submissions for Jump Game.
Time complexity: O(n). We are doing a single pass through the nums array, hence nn steps, where n is the length of array nums.
Space complexity: O(1). We are not using any extra memory.
45 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.
Example:
Input: [2,3,1,1,4]
Output: 2
Explanation: 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.
思路：
动态规划的时间复杂度是O(n^2 ）或者O( n^3)（没想清楚具体是哪个）。过大。
class Solution {
public int jump(int[] nums) {
int len = nums.length;
int dp[] = new int[len];
dp[0] = 0;
int currMax = 0;
int currIndex = 0;
int max =nums[0];
for(int i = 1; i < len; i++){
currMax = Math.max(currMax, i + nums[i]);
if(i< max){
dp[i] = dp[currIndex] +1;
}else{
dp[i] = dp[currIndex] +1;
max = currMax;
currIndex = i;
}
}
return dp[nums.length-1];
}
}
修改版，没有建立额外的数组。保持空间复杂度为O(1)。
class Solution {
public int jump(int[] nums) {
int len = nums.length;
int dp[] = new int[len];
dp[0] = 0;
int step = 0;
int max =nums[0];
int currMax = max;
if(len == 1) return 0;
if(max >= len && len > 1){
step++;
return step;
}
for(int i = 0; i < len; i++){
currMax = Math.max(currMax, i + nums[i]);
if(i < max){
}else{
max = currMax;
step ++;
}
}
return step;
}
}
测试[1,2,3] 有问题。
贪心版本：
贪心思路：
记录能走到的最远距离farest, 现在的位置curr以及步数step。
来自leeetcode讨论区：
class Solution {
public int jump(int[] nums) {
int len = nums.length;
int step = 0;
int farest = 0;
int curr = 0;
for (int i = 0; i < len; i++) {
if (i > farest) {
farest = curr;
step++;
}
curr = Math.max(curr, i+nums[i]);
}
return step;
}
}
只扫描一遍，直接判断。
51. N-Queens
经典的回溯问题，同时涉及到分枝限界。
回溯的套路：构造解空间（状态空间树（state space tree）），用回溯法搜索解空间，并使用分枝限界舍去无效分枝。
大致思路：
1.更新行与列的参数，从给定棋盘第一行，第一列开始。
2.判断当前位置是否在前后两角共四个方向中，都不存在另一个皇后棋子。
3.如果满足：
在当前位置放一个皇后，若当前行是最后一行，记录一个解；
若当前行不是最后一行，当前行设为下一行, 当前列设为当前行的第一个待测位置；
若当前行是最后一行，当前列不是最后一列，当前列设为下一列；
若当前行是最后一行，当前列是最后一列，回溯，即清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置。
以上返回到第2步
4.在当前位置上不满足条件的情形：
若当前列不是最后一列，当前列设为下一列，返回到第2步;
若当前列是最后一列了，回溯，即，若当前行已经是第一行了，算法退出，否则，清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置，返回到第2步;
我发现这种类型的题目我在去年夏天写过。当时刚学递归，完成了一个类似思路的走迷宫问题。迭代或者递归都可以处理。
网友评论