【Leetcode 做題學演算法周刊】第六期-有解無憂

首發于微信公眾號《前端成長記》，寫于 2019.12.15

背景

本文記錄刷題程序中的整個思考程序，以供參考，主要內容涵蓋：

題目分析設想
撰寫代碼驗證
查閱他人解法
思考總結

Easy

110.平衡二叉樹

題目地址

題目描述

給定一個二叉樹，判斷它是否是高度平衡的二叉樹，

本題中，一棵高度平衡二叉樹定義為：

一個二叉樹每個節點的左右兩個子樹的高度差的絕對值不超過1，

示例 1:

給定二叉樹 [3,9,20,null,null,15,7]

回傳 true ，

示例 2:

給定二叉樹 [1,2,2,3,3,null,null,4,4]

回傳 false ，

題目分析設想

我們上一期做過通過遍歷求二叉樹的最大深度的題目，這題最粗暴的一個方案就是計算出每個子樹的最大深度做高度判斷，很明顯，這個效率低下，我們可以通過改成自底而上的方案，當中間程序不符合，則可以跳出計算，

撰寫代碼驗證

Ⅰ.計算子樹最大深度做判斷

代碼：

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
    if (root === null) return true
    function maxDepth (node) {
        if (node === null) return 0
        const l = maxDepth(node.left)
        const r = maxDepth(node.right)
        return Math.max(l, r) + 1
    }

    return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1
    && isBalanced(root.left)
    && isBalanced(root.right)
};

結果：

227/227 cases passed (80 ms)
Your runtime beats 77.66 % of javascript submissions
Your memory usage beats 26.73 % of javascript submissions (37.8 MB)
時間復雜度 O(n^2)

Ⅱ.自底而上

代碼：

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
    function maxDepth (node) {
        if (node === null) return 0
        const l = maxDepth(node.left)
        if (l === -1) return -1
        const r = maxDepth(node.right)
        if (r === -1) return -1
        return Math.abs(l - r) <= 1 ? Math.max(l, r) + 1 : -1
    }

    return maxDepth(root) !== -1
};

結果：

227/227 cases passed (72 ms)
Your runtime beats 95.44 % of javascript submissions
Your memory usage beats 50.5 % of javascript submissions (37.5 MB)
時間復雜度 O(n)

查閱他人解法

思路基本上都是這兩種，未發現方向不同的解法，

思考總結

這里很明顯，大家都是用深度遍歷來解決問題，計算子樹深度會發現，有很多重復運算，所以不妨試試自底而上的方式，直接在計算高度程序中就回傳，也可以叫做“提前阻斷”，所以，這道題建議是使用自底而上的方式來作答，

111.二叉樹的最小深度

題目地址

題目描述

給定一個二叉樹，找出其最小深度，

最小深度是從根節點到最近葉子節點的最短路徑上的節點數量，

說明: 葉子節點是指沒有子節點的節點，

示例：

給定二叉樹 [3,9,20,null,null,15,7],

回傳它的最小深度 2.

題目分析設想

這道題很明顯自頂而下就可以了，判斷每個節點的子節點是否存在，不存在，則該路徑為最短路徑，如果存在，就按深度的方式比較最小值，總體上來說，也可以用之前求最大深度的幾種方式來作答，

撰寫代碼驗證

Ⅰ.遞回

代碼：

/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function(root) {
    if (root === null) return 0
    if (root.left === null && root.right === null) return 1
    let res = Infinity
    if(root.left !== null) {
        res = Math.min(minDepth(root.left), res)
    }
    if(root.right !== null) {
        res = Math.min(minDepth(root.right), res)
    }
    return res + 1
};

結果：

41/41 cases passed (76 ms)
Your runtime beats 69.08 % of javascript submissions
Your memory usage beats 5.55 % of javascript submissions (37.9 MB)
時間復雜度 O(n)

Ⅱ.利用堆疊迭代

代碼：

/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function(root) {
    if (root === null) return 0
    if (root.left === null && root.right === null) return 1
    // 堆疊
    let s = [{
        node: root,
        dep: 1
    }]
    let dep = Infinity
    while(s.length) {
        // 先進后出
        var cur = s.pop()
        if (cur.node !== null) {
            let curDep = cur.dep
            if (cur.node.left === null && cur.node.right === null) {
                dep = Math.min(dep, curDep)
            }
            if (cur.node.left !== null) s.push({node: cur.node.left, dep: curDep + 1})
            if (cur.node.right !== null) s.push({node: cur.node.right, dep: curDep + 1})
        }
    }
    return dep
};

結果：

41/41 cases passed (68 ms)
Your runtime beats 93.82 % of javascript submissions
Your memory usage beats 75.31 % of javascript submissions (37 MB)
時間復雜度 O(n)

Ⅲ.利用佇列

代碼：

/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function(root) {
    if (root === null) return 0
    if (root.left === null && root.right === null) return 1
    // 佇列
    let s = [{
        node: root,
        dep: 1
    }]
    let dep = 0
    while(s.length) {
        // 先進先出
        var cur = s.shift()
        var node = cur.node
        dep = cur.dep
        if (node.left === null && node.right === null) break;
        if (node.left !== null) s.push({node: node.left, dep: dep + 1})
        if (node.right !== null) s.push({node: node.right, dep: dep + 1})
    }
    return dep
};

結果：

41/41 cases passed (76 ms)
Your runtime beats 69.08 % of javascript submissions
Your memory usage beats 6.79 % of javascript submissions (37.7 MB)
時間復雜度 O(n)

查閱他人解法

總體上而言分成深度優先和廣度優先，最基本的就是遞回和迭代了，沒有發現二叉樹相關題目的一些新奇解法，

思考總結

很明顯可以看出遞回和利用堆疊迭代是深度優先，利用佇列是廣度優先，這里自頂而下比較合適，只要找到葉子節點，直接就是最小深度了，可以省去不少運算，

112.路徑總和

題目地址

題目描述

給定一個二叉樹和一個目標和，判斷該樹中是否存在根節點到葉子節點的路徑，這條路徑上所有節點值相加等于目標和，

說明: 葉子節點是指沒有子節點的節點，

示例:

給定如下二叉樹，以及目標和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

回傳 true, 因為存在目標和為 22 的根節點到葉子節點的路徑 5->4->11->2，

題目分析設想

這道題我的想法是因為要找到葉子節點，所以深度優先更為合適，這里就使用前文的兩種方法：

遞回
利用堆疊迭代

撰寫代碼驗證

Ⅰ.遞回

代碼：

/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {boolean}
 */
var hasPathSum = function(root, sum) {
    if (root === null) return false
    // 剩余需要的值
    sum -= root.val
    if (root.left === null && root.right === null) {
        return sum === 0
    } else {
        return hasPathSum(root.left, sum) || hasPathSum(root.right, sum)
    }
};

結果：

114/114 cases passed (80 ms)
Your runtime beats 62.09 % of javascript submissions
Your memory usage beats 56.9 % of javascript submissions (37.1 MB)
時間復雜度 O(n)

Ⅱ.迭代

代碼：

/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {boolean}
 */
var hasPathSum = function(root, sum) {
    if (root === null) return false
    // 堆疊
    let stack = [{
        node: root,
        remain: sum - root.val
    }]
    while(stack.length) {
        // 先進后出
        var cur = stack.pop()
        var node = cur.node
        if (node.left === null && node.right === null && cur.remain === 0) return true
        if (node.left !== null) {
            stack.push({
                node: node.left,
                remain: cur.remain - node.left.val
            })
        }
        if (node.right !== null) {
            stack.push({
                node: node.right,
                remain: cur.remain - node.right.val
            })
        }
    }
    return false
};

結果：

114/114 cases passed (72 ms)
Your runtime beats 88.51 % of javascript submissions
Your memory usage beats 33.33 % of javascript submissions (37.2 MB)
時間復雜度 O(n)

查閱他人解法

這里看到一個方案是采用后序遍歷，路徑長度由之前的堆疊改成變數保存，但是這個在我看來沒有中序遍歷合適，感興趣的可以點此查閱，另外還是有選擇使用廣度優先，利用佇列來解的，這里也算一個不同思路，就當做補充吧，

Ⅰ.利用佇列

代碼：

/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {boolean}
 */
var hasPathSum = function(root, sum) {
    if (root === null) return false
    // 佇列
    let q = [{
        node: root,
        sum: root.val
    }]
    while(q.length) {
        // 當前層元素的個數
        for(let i = 0; i < q.length; i++) {
            let cur = q.shift()
            let node = cur.node
            if (node.left === null && node.right === null && cur.sum === sum) return true

            if (node.left !== null) {
                q.push({ node: node.left, sum: cur.sum + node.left.val})
            }
            if (node.right !== null) {
                q.push({ node: node.right, sum: cur.sum + node.right.val})
            }
        }
    }
    return false
};

結果：

114/114 cases passed (72 ms)
Your runtime beats 88.51 % of javascript submissions
Your memory usage beats 56.32 % of javascript submissions (37.1 MB)
時間復雜度 O(n)

118.楊輝三角

題目地址

題目描述

給定一個非負整數 numRows，生成楊輝三角的前 numRows 行，

楊輝三角

在楊輝三角中，每個數是它左上方和右上方的數的和，

示例:

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

題目分析設想

這道題最笨的方案就是雙重回圈，首尾為1，其他位為 S(l)[n] = S(l-1)[n-1] + S(l-1)[n] ，當然這里很明顯也可以當做一個動態規劃問題來解答，

這里有個坑，給的是索引，不是第 n 行

撰寫代碼驗證

Ⅰ.動態規劃

代碼：

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function(numRows) {
    let res = []
    for(let i = 0; i < numRows; i++) {
        // 所有默認都填了1，可以節省不少運算
        res.push(new Array(i+1).fill(1))
        // 第三行開始才需要修改
        for(j = 1; j < i; j++) {
            res[i][j] = res[i-1][j] + res[i-1][j-1]
        }
    }
    return res
};

結果：

15/15 cases passed (60 ms)
Your runtime beats 85.2 % of javascript submissions
Your memory usage beats 55.52 % of javascript submissions (33.6 MB)
時間復雜度 O(n^2)

查閱他人解法

這里看到兩個不同方向的，一個是遞回，因為這題在遞回卡片中，一個是二項式定理，

Ⅰ.遞回

代碼：

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function (numRows) {
    let res = []

    function sub(row, numRows, arr) {
        let temp = []
        if (row < numRows) {
            for (let i = 0; i <= row; i++) {
                if (row === 0) {
                    temp.push(1)
                } else {
                    let left = i - 1 >= 0 ? arr[row - 1][i - 1] : 0
                    let right = i < arr[row - 1].length ? arr[row - 1][i] : 0
                    temp.push(left + right)
                }
            }
            arr.push(temp)
            sub(++row, numRows, arr)
            return arr
        } else {
            return arr
        }
    }
    return sub(0, numRows, res)
};

結果：

15/15 cases passed (64 ms)
Your runtime beats 68.27 % of javascript submissions
Your memory usage beats 56.86 % of javascript submissions (33.6 MB)
時間復雜度 O(n^2)

Ⅱ.二項式定理

優勢在于可以直接計算第n行，用二項式定理公式計算， (a+b)^n 一共有n+1項，每一項的系數對應楊輝三角的第 n 行，第 r 項的系數等于組合數 C(n,r) ，

代碼：

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function(numRows) {
    var res = [];

    /**
     * 組合數
     * @param n
     * @param r
     * @returns {number}
     * @constructor
     */
    function C(n, r) {
        if(n == 0) return 1;
        return F(n) / F(r) / F(n - r);
    }
    /**
     * 階乘
     * @param n
     * @returns {number}
     * @constructor
     */
    function F(n) {
        var s = 1;
        for(var i = 1;i <= n;i++) {
            s *= i;
        }
        return s;
    }

    for (var i = 0;i < numRows;i++){
        res[i] = [];
        for (var j = 0;j < i + 1;j++){
            res[i].push(C(i, j));
        }
    }
    return res;
};

結果：

15/15 cases passed (64 ms)
Your runtime beats 68.27 % of javascript submissions
Your memory usage beats 5.02 % of javascript submissions (34.3 MB)
時間復雜度 O(n^2)

思考總結

對于數學敏感的開發者，很容易就想到使用二項式定理，但是在我看來，找到了一個計算規則，就很容易想到使用動態規劃來解決問題，我也推薦使用動態規劃來生成楊輝三角，

119.楊輝三角Ⅱ

題目地址

題目描述

給定一個非負索引 k，其中 k ≤ 33，回傳楊輝三角的第 k 行，

在楊輝三角中，每個數是它左上方和右上方的數的和，

示例:

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

進階：

你可以優化你的演算法到 O(k) 空間復雜度嗎？

題目分析設想

上面從他人解法中發現了二項式定理可以直接求第 n 行，另外我們也可以發現個規律，第幾行實際上就有幾個數，且首尾為1，當然也可以使用動態規劃來作答，

撰寫代碼驗證

Ⅰ.動態規劃

代碼：

/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function(rowIndex) {
    // rowIndex 是索引，0相當于第1行
    if (rowIndex === 0) return [1]
    let res = []
    for(let i = 0; i < rowIndex + 1; i++) {
        let temp = new Array(i+1).fill(1)
        // 第三行開始才需要修改
        for(let j = 1; j < i; j++) {
            temp[j] = res[j - 1] + res[j]
        }
        res = temp
    }
    return res
};

結果：

34/34 cases passed (64 ms)
Your runtime beats 75.77 % of javascript submissions
Your memory usage beats 54.9 % of javascript submissions (33.8 MB)
時間復雜度 O(n^2)

Ⅱ.二項式定理

代碼：

/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function(rowIndex) {
    /**
     * 組合數
     * @param n
     * @param r
     * @returns {number}
     * @constructor
     */
    function C(n, r) {
        if(n == 0) return 1;
        return F(n) / F(r) / F(n - r);
    }
    /**
     * 階乘
     * @param n
     * @returns {number}
     * @constructor
     */
    function F(n) {
        var s = 1;
        for(var i = 1;i <= n;i++) {
            s *= i;
        }
        return s;
    }
    let res = []
    // 因為是通過上一項計算，所以第1項的 n 為0
    for (var i = 0;i < rowIndex + 1;i++){
        res.push(C(rowIndex, i));
    }
    return res;
};

結果：

34/34 cases passed (52 ms)
Your runtime beats 99.12 % of javascript submissions
Your memory usage beats 41.18 % of javascript submissions (34.5 MB)
時間復雜度 O(n)

查閱他人解法

因為發現每行的對稱性，所以也可以求一半后反轉復制即可，

Ⅰ.反轉復制

代碼：

/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function(rowIndex) {
    // rowIndex 是索引，0相當于第1行
    if (rowIndex === 0) return [1]
    let res = []
    for(let i = 0; i < rowIndex + 1; i++) {
        let temp = new Array(i+1).fill(1)
        // 第三行開始才需要修改
        const mid = i >>> 1
        for(let j = 1; j < i; j++) {
            if (j > mid) {
                temp[j] = temp[i - j]
            } else {
                temp[j] = res[j - 1] + res[j]
            }
        }
        res = temp
    }
    return res
};

結果：

34/34 cases passed (60 ms)
Your runtime beats 88.47 % of javascript submissions
Your memory usage beats 60.78 % of javascript submissions (33.7 MB)
時間復雜度 O(n^2)

思考總結

其實更像一個數學問題，不斷地找出規律來節省運算，真是“學好數理化，走遍天下都不怕”，

（完）

本文為原創文章，可能會更新知識點及修正錯誤，因此轉載請保留原出處，方便溯源，避免陳舊錯誤知識的誤導，同時有更好的閱讀體驗
如果能給您帶去些許幫助，歡迎 ??star 或 ?? fork
(轉載請注明出處：https://chenjiahao.xyz)

轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/162499.html

標籤：JavaScript

上一篇：vue-practice

下一篇：JS 輪播圖

【Leetcode 做題學演算法周刊】第六期

背景

目錄

Easy

110.平衡二叉樹

題目描述

題目分析設想

撰寫代碼驗證

查閱他人解法

思考總結

111.二叉樹的最小深度

題目描述

題目分析設想

撰寫代碼驗證

查閱他人解法

思考總結

112.路徑總和

題目描述

題目分析設想

撰寫代碼驗證

查閱他人解法

118.楊輝三角

題目描述

題目分析設想

撰寫代碼驗證

查閱他人解法

思考總結

119.楊輝三角Ⅱ

題目描述

題目分析設想

撰寫代碼驗證

查閱他人解法

思考總結