“

第一篇關(guān)于「棧與隊(duì)列與鏈表篇」 的文章不知道大家有沒有學(xué)習(xí)完哈，在正式進(jìn)入「遞歸與回溯篇」前，我們先來一點(diǎn)熱身題，然后刷一刷前置知識，希望大家跟進(jìn)腳步，一起加油，努力變優(yōu)秀~

”

熱身題

面試題 16.11. 跳水板

「題目描述」

你正在使用一堆木板建造跳水板。有兩種類型的木板，其中長度較短的木板長度為shorter，長度較長的木板長度為longer。

你必須正好使用k塊木板。編寫一個方法，生成跳水板所有可能的長度。

返回的長度需要從小到大排列。

示例 1

輸入：
shorter = 1
longer = 2

k = 3
輸出： [3,4,5,6]
解釋：
可以使用 3 次 shorter，得到結(jié)果 3；使用 2 次 shorter 和 1 次 longer，得到結(jié)果 4 。以此類推，得到最終結(jié)果。

提示：

0 < shorter <= longer
0 <= k <= 100000

「解題思路」

排列組合也算比較簡單，需要 k 個板子，當(dāng)我們短板有 i 個的時候，長板子就是 k-i 個，由于題目要求是將結(jié)果從小到大進(jìn)行排序，那么我們起初就盡可能多的取短板子，最后結(jié)果就是通過 [0,k] 范圍內(nèi)遍歷一遍即可。

對于特殊情況，即短板和長板長度相同時，我們只需要返回 k*len 即可，不然會重復(fù)計(jì)算。

var divingBoard = function(shorter, longer, k) {
    if(k===0) return []
    if(shorter === longer) return [k*shorter]
    let res = []
    for(let i=k;i>=0;i--){
        let shortCnt = i
        let longCnt = k-i
        let cnt = shortCnt*shorter + longCnt*longer
        res.push(cnt)
    }
    return res
};

1291. 順次數(shù)

「題目描述」

我們定義「順次數(shù)」為：每一位上的數(shù)字都比前一位上的數(shù)字大 1 的整數(shù)。

請你返回由 [low, high] 范圍內(nèi)所有順次數(shù)組成的 有序 列表（從小到大排序）。

示例 1：

輸出：low = 100, high = 300
輸出：[123,234]

示例 2：

輸出：low = 1000, high = 13000
輸出：[1234,2345,3456,4567,5678,6789,12345]
 

提示：

10 <= low <= high <= 10^9

「解題思路」

「順次數(shù)」為：每一位上的數(shù)字都比前一位上的數(shù)字大 1 的整數(shù)。

也就是例如 1234這樣的數(shù)字，然后給你一段區(qū)間確定范圍。

官方給了枚舉方式，反正數(shù)據(jù)量也不是很大，但是我覺得還是有很多數(shù)字沒必要枚舉，可以直接剪枝掉。我的做法是先求出最小值和最大值對應(yīng)字符串的長度，即求出我們能枚舉的數(shù)字的長度范圍。

然后我們的起點(diǎn)的最小值從 1 開始，起點(diǎn)的最大值從 10-len 開始。為什么是 10-len？舉例說明，示例1給的是 [100,300]范圍的值，那么可枚舉的長度 len 為 3，起點(diǎn)的最大值就位 10 - 3 = 7。那么此時順次數(shù)為 789 但是不在我們區(qū)間范圍內(nèi)，舍棄。然后8、9開頭的數(shù)字就不需要枚舉了。這樣，我們就能剪掉一部門數(shù)據(jù)了。（雖然暴力是永遠(yuǎn)滴神...）

/**
 * @param {number} low
 * @param {number} high
 * @return {number[]}
 */
var sequentialDigits = function(low, high) {
    let res = []
    let lowLen = low.toString().length
    let highLen = high.toString().length
    for(let i=lowLen;i<=highLen;i++){
        for(let j=1;j<=10-i;j++){
            let str = ''
            let num = j
            str += num
            let k = i-1
            while(k--){
                num++
                str += num
            }
            let ans = parseInt(str)
            if(ans>=low && ans<=high){
                res.push(ans)
            }
        }
    }
    return res    
};

矩陣

73. 矩陣置零

「題目描述」

給定一個 m x n 的矩陣，如果一個元素為 0，則將其所在行和列的所有元素都設(shè)為 0。請使用原地算法。

示例 1:

輸入: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
輸出: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

示例 2:

輸入: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
輸出: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

進(jìn)階:

一個直接的解決方案是使用  O(mn) 的額外空間，但這并不是一個好的解決方案。
一個簡單的改進(jìn)方案是使用 O(m + n) 的額外空間，但這仍然不是最好的解決方案。
你能想出一個常數(shù)空間的解決方案嗎？

「解題思路」

用 O(n) 空間復(fù)雜度來做，先遍歷矩陣，找到等于0的坐標(biāo)，然后遍歷坐標(biāo)，將對應(yīng)行和列置為 0 即可

時間復(fù)雜度 O(m * n)

var setZeroes = function(matrix) {
    let n = matrix.length
    let m = matrix[0].length
    let arr = []
    for(let i=0;i<n;i++){
        for(let j=0;j<m;j++){
            if(matrix[i][j] == 0){
                arr.push([i,j])
            }
        }
    }
    while(arr.length){
        let [x,y] = arr.pop()
        for(let i=0;i<n;i++) matrix[i][y] = 0
        for(let j=0;j<m;j++) matrix[x][j] = 0
    }
    return matrix
};

另外一種，「原地算法」，空間復(fù)雜度 O(1)，我們無需借助外部空間。找到下標(biāo)為 0 的坐標(biāo)，然后直接對該行和該列不等于 0 的數(shù)字設(shè)置為 -0 即可。這里巧妙運(yùn)用了 JS 中的 Object.is()方法，此時 0 和-0 不相等，但是最終返回的矩陣還是為 0

var setZeroes = function(matrix) {
    for(let i=0;i<matrix.length;i++){
        for(let j=0;j<matrix[0].length;j++){
            if(Object.is(matrix[i][j],0)){
                // 對行進(jìn)行操作
                for(let k=0;k<matrix.length;k++)
                    if(!Object.is(matrix[k][j],0) && k!==i) matrix[k][j] = -0
                // 對列進(jìn)行操作
                for(let k=0;k<matrix[0].length;k++)
                    if(!Object.is(matrix[i][k],0) && k!==j) matrix[i][k] = -0
            }
        }
    }
    return matrix
};

54. 螺旋矩陣

「題目描述」

給定一個包含 m x n 個元素的矩陣（m 行, n 列），請按照順時針螺旋順序，返回矩陣中的所有元素。

示例 1:

輸入:
[
 [1,2,3],
 [4,5,6],
 [7,8,9]
]
輸出: [1,2,3,6,9,8,7,4,5]

示例 1:

輸入:
[
 [1,2,3,4],
 [5,6,7,8],
 [9,10,11,12]
]
輸出: [1,2,3,4,8,12,11,10,9,5,6,7]

「解題思路」

和「上一期」 螺旋矩陣差不多，這個是讓我么輸出，而上次是讓我們構(gòu)造，還是按照螺旋矩陣模擬即可，先從左到右，在從上到下，再從右到左，再從下到上。

不過這里的矩陣行和列不相同了，可能會出現(xiàn)不成環(huán)的情況，那么最后會留一列或一行出來，這里借用「大佬」一張圖：

然后我們需要提前跳出去一下，就是避免重復(fù)計(jì)算，總數(shù)夠了直接跳出去。注意下面代碼 break。只能放在那里，因?yàn)楸闅v順序，如果最后留下一行的話，需要從左到右遍歷，此時 top > bottom  。如果最后留下一列的話，需要從上到下遍歷，此時 left > right。

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
    if(!matrix.length) return []
    let n = matrix.length
    let m = matrix[0].length
    let total = n*m
    let top = 0,bottom = n-1
    let left = 0,right = m-1
    let res = []
    while(res.length < total){
        for(let i=left;i<=right;i++) res.push(matrix[top][i]) // 從左到右
        top++
        for(let i=top;i<=bottom;i++) res.push(matrix[i][right]) // 從上到下
        right--
        /* 因?yàn)閚 和 m 不相同的時候，最后可能會留一列或一行，避免重復(fù)計(jì)算，總數(shù)夠了直接跳出去 */
        if(res.length === total) break
        for(let i=right;i>=left;i--) res.push(matrix[bottom][i]) // 從右到左
        bottom--
        for(let i=bottom;i>=top;i--) res.push(matrix[i][left]) // 從下到上
        left++
    }
    return res
};

59. 螺旋矩陣 II

「題目描述」

給定一個正整數(shù) n，生成一個包含 1 到 n2 所有元素，且元素按順時針順序螺旋排列的正方形矩陣。

示例:

「解題思路」

按照螺旋矩陣模擬即可，先從左到右，在從上到下，再從右到左，再從下到上。

每次進(jìn)行cur++操作，直到累加到total為止。最后返回二維數(shù)組即可（沒想到 js二維數(shù)組也是這樣方便...）

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
    let top = 0, bottom =n-1
    let left = 0, right = n-1
    let res = []
    for(let i=0;i<n;i++) res[i] = []
    let cur = 1, total = n*n
    while(cur<=total){
        for(let i=left;i<=right;i++) res[top][i] = cur++  // 從左到右
        top++
        for(let i=top;i<=bottom;i++) res[i][right] = cur++ // 從上到下
        right--
        for(let i=right;i>=left;i--) res[bottom][i] = cur++ // 從右到左
        bottom--
        for(let i=bottom;i>=top;i--) res[i][left] = cur++ // 從下到上
        left++
    }
    return res
};

子集

46. 全排列

「題目描述」

給定一個 沒有重復(fù) 數(shù)字的序列，返回其所有可能的全排列。

示例:

輸入: [1,2,3]
輸出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

「解題思路」

序列不重復(fù)就很簡單了，維護(hù)一個 vis數(shù)組，不重復(fù)取就好了。

var permute = function (nums) {
  let res = [];
  let vis = {};
  let dfs = (t) => {
    if (t.length == nums.length) {
      res.push(t);
    }
    for (let i = 0; i < nums.length; i++) {
      if (vis[i]) continue;
      vis[i] = true;
      t.push(nums[i]);
      dfs(t.slice());
      t.pop();
      vis[i] = false;
    }
  }
  dfs([]);
  return res;
};

47. 全排列 II

「題目描述」

給定一個可包含重復(fù)數(shù)字的序列，返回所有不重復(fù)的全排列。

示例:

輸入: [1,1,2]
輸出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

「解題思路」

本題是求全排列，并且排列不能重復(fù)。我們用一個 vis數(shù)組維護(hù)一下，讓每一條路線保證不重復(fù)選取元素，而對于每一層而言，需要判斷相鄰元素是否相同，相同的就沒必要走了，例如下圖中紅色三角形部分。

果當(dāng)前的選項(xiàng) nums[i] ，與同一層的上一個選項(xiàng) nums[i - 1] 相同，且 nums[i - 1]有意義（即索引 >= 0），且沒有被使用過，那就跳過該選項(xiàng)。

因?yàn)?nums[i - 1]如果被使用過，它會被修剪掉，不是一個選項(xiàng)了，即便它和 nums[i]重復(fù)，nums[i]還是可以選的。

「參考xiao_ben_zhu大佬題解」

var permuteUnique = function(nums) {
    let res = [];
    nums.sort((a,b) => a-b);
    let vis = {};
    let dfs = (t) => {
      if(t.length === nums.length){
        res.push(t);
      }
      for(let i=0;i<nums.length;i++){
        if(i-1>=0 && nums[i] == nums[i-1] && !vis[i-1]) continue;
        if(vis[i]) continue;
        vis[i] = true;
        t.push(nums[i]);
        dfs(t.slice(),i+1);
        t.pop();
        vis[i] = false;
      }
    }
    dfs([],0);
    return res;
};

78. 子集

「題目描述」

給定一組不含重復(fù)元素的整數(shù)數(shù)組 nums，返回該數(shù)組所有可能的子集（冪集）。

說明：解集不能包含重復(fù)的子集。

示例:

輸入: nums = [1,2,3]
輸出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

「解題思路」

一道組合相關(guān)的題目，采用回溯來做即可，題目說明不包含重復(fù)元素，于是我們也無需排序然后判斷相鄰元素是否相等來去重了。

var subsets = function(nums) {
  let res = [];
  let dfs = (t,start) => {
    res.push(t);
    for(let i=start;i<nums.length;i++){
      t.push(nums[i]);
      dfs(t.slice(),i+1);
      t.pop();
    }
  }
  dfs([],0);
  return res;
};

90. 子集 II

「題目描述」

給定一個可能包含重復(fù)元素的整數(shù)數(shù)組 nums，返回該數(shù)組所有可能的子集（冪集）。

說明：解集不能包含重復(fù)的子集。

示例:

輸入: [1,2,2]
輸出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

「解題思路」

本題還是挺有意思的，我們要求的是子集，但是子集要進(jìn)行去重操作，采用的做法是先對原數(shù)組進(jìn)行排序，那么排序后的數(shù)組重復(fù)的元素必定是相鄰的，然后在遍歷解空間樹的時候，要做一個去重的操作，當(dāng)遇到重復(fù)出現(xiàn)，也就是和前面相鄰元素相同的時候，直接跳過該節(jié)點(diǎn)，不讓它向下遞歸。具體示意圖如下：

「參考大佬題解」

dfs的話，一條路會一直走下去，然后回溯回來，在走之前，start是當(dāng)前層第一個元素，只有當(dāng)前元素下標(biāo)大于 start才會有重復(fù)元素，而對于不同層的重復(fù)元素，我們不應(yīng)該切斷，應(yīng)該繼續(xù)走，不然就不會有 [1,2,2]這樣的子集出現(xiàn)了。

var subsetsWithDup = function(nums) {
  let res = [];
  nums.sort((a,b)=>a-b);
  let dfs = (t,start) => {
    res.push(t);
    for(let i=start;i<nums.length;i++){
      // 同層重復(fù)，跳過
      if(i>start && nums[i-1] == nums[i]) continue;
      t.push(nums[i]);
      dfs(t.slice(),i+1);
      t.pop();
    }
  }
  dfs([],0);
  return res;
};

本文參考

• 「前端該如何準(zhǔn)備數(shù)據(jù)結(jié)構(gòu)和算法？」
• 「寫給前端的算法進(jìn)階指南，我是如何兩個月零基礎(chǔ)刷200題」
• 「(1.8w字)負(fù)重前行，前端工程師如何系統(tǒng)練習(xí)數(shù)據(jù)結(jié)構(gòu)和算法？【上】」

參考鏈接：

結(jié)語

??關(guān)注+點(diǎn)贊+收藏+評論+轉(zhuǎn)發(fā)??，原創(chuàng)不易，您的支持將會是我最大的動力~

祝愿在準(zhǔn)備春秋招の你，能夠早點(diǎn)結(jié)束，offer 拿到手軟，希望我的文章能夠幫助到你，我們很快會在下期相遇，給個贊及時催更呀~

學(xué)如逆水行舟，不進(jìn)則退