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)然還有貪心和回溯的解法。
題目思考：給定一個(gè)非負(fù)數(shù)組，難點(diǎn)在于記錄從上一點(diǎn)到下一點(diǎn)的跳躍能力轉(zhuǎn)換。
動態(tài)規(guī)劃的思路：建立一個(gè)dp數(shù)組，建立上一個(gè)元素和下一個(gè)元素的關(guān)系（類似階躍函數(shù)）。找到最遠(yuǎn)的那個(gè)位置，并記錄下來。
想清楚怎么轉(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]這個(gè)測試用例。哪里出了問題？
貪心版本：
思路：記錄現(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ī)劃的時(shí)間復(fù)雜度是O(n^2 ）或者O( n^3)（沒想清楚具體是哪個(gè)）。過大。
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)典的回溯問題，同時(shí)涉及到分枝限界。
回溯的套路：構(gòu)造解空間（狀態(tài)空間樹（state space tree）），用回溯法搜索解空間，并使用分枝限界舍去無效分枝。
大致思路：
1.更新行與列的參數(shù)，從給定棋盤第一行，第一列開始。
2.判斷當(dāng)前位置是否在前后兩角共四個(gè)方向中，都不存在另一個(gè)皇后棋子。
3.如果滿足：
在當(dāng)前位置放一個(gè)皇后，若當(dāng)前行是最后一行，記錄一個(gè)解；
若當(dāng)前行不是最后一行，當(dāng)前行設(shè)為下一行, 當(dāng)前列設(shè)為當(dāng)前行的第一個(gè)待測位置；
若當(dāng)前行是最后一行，當(dāng)前列不是最后一列，當(dāng)前列設(shè)為下一列；
若當(dāng)前行是最后一行，當(dāng)前列是最后一列，回溯，即清空當(dāng)前行及以下各行的棋盤，然后，當(dāng)前行設(shè)為上一行，當(dāng)前列設(shè)為當(dāng)前行的下一個(gè)待測位置。
以上返回到第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)前行的下一個(gè)待測位置，返回到第2步;
我發(fā)現(xiàn)這種類型的題目我在去年夏天寫過。當(dāng)時(shí)剛學(xué)遞歸，完成了一個(gè)類似思路的走迷宮問題。迭代或者遞歸都可以處理。
