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.
經(jīng)典算法分類：這道題目可以分類到動態(tài)規(guī)劃中，當(dāng)然還有貪心和回溯的解法捅厂。
題目思考：給定一個非負(fù)數(shù)組探橱，難點(diǎn)在于記錄從上一點(diǎn)到下一點(diǎn)的跳躍能力轉(zhuǎn)換。
動態(tài)規(guī)劃的思路：建立一個dp數(shù)組蛮放，建立上一個元素和下一個元素的關(guān)系（類似階躍函數(shù)）缩抡。找到最遠(yuǎn)的那個位置，并記錄下來包颁。
想清楚怎么轉(zhuǎn)換就可以直接寫了瞻想。
代碼：
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]這個測試用例挎塌。哪里出了問題？
貪心版本：
思路：記錄現(xiàn)在能跳到的最遠(yuǎn)距離内边。
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.
思路：
動態(tài)規(guī)劃的時間復(fù)雜度是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];
}
}
修改版漠其，沒有建立額外的數(shù)組。保持空間復(fù)雜度為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] 有問題和屎。
貪心版本：
貪心思路：
記錄能走到的最遠(yuǎn)距離farest, 現(xiàn)在的位置curr以及步數(shù)step。
來自leeetcode討論區(qū)：
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
經(jīng)典的回溯問題，同時涉及到分枝限界宽气。
回溯的套路：構(gòu)造解空間（狀態(tài)空間樹（state space tree））随常，用回溯法搜索解空間，并使用分枝限界舍去無效分枝萄涯。
大致思路：
1.更新行與列的參數(shù)绪氛，從給定棋盤第一行，第一列開始涝影。
2.判斷當(dāng)前位置是否在前后兩角共四個方向中枣察，都不存在另一個皇后棋子。
3.如果滿足：
在當(dāng)前位置放一個皇后燃逻，若當(dāng)前行是最后一行序目，記錄一個解；
若當(dāng)前行不是最后一行伯襟，當(dāng)前行設(shè)為下一行, 當(dāng)前列設(shè)為當(dāng)前行的第一個待測位置猿涨；
若當(dāng)前行是最后一行，當(dāng)前列不是最后一列姆怪，當(dāng)前列設(shè)為下一列嘿辟；
若當(dāng)前行是最后一行，當(dāng)前列是最后一列片效，回溯红伦，即清空當(dāng)前行及以下各行的棋盤，然后淀衣，當(dāng)前行設(shè)為上一行昙读，當(dāng)前列設(shè)為當(dāng)前行的下一個待測位置。
以上返回到第2步
4.在當(dāng)前位置上不滿足條件的情形：
若當(dāng)前列不是最后一列膨桥，當(dāng)前列設(shè)為下一列蛮浑，返回到第2步;
若當(dāng)前列是最后一列了唠叛，回溯，即沮稚，若當(dāng)前行已經(jīng)是第一行了艺沼，算法退出，否則蕴掏，清空當(dāng)前行及以下各行的棋盤障般，然后，當(dāng)前行設(shè)為上一行盛杰，當(dāng)前列設(shè)為當(dāng)前行的下一個待測位置挽荡，返回到第2步;
我發(fā)現(xiàn)這種類型的題目我在去年夏天寫過。當(dāng)時剛學(xué)遞歸即供，完成了一個類似思路的走迷宮問題定拟。迭代或者遞歸都可以處理。
