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

来源:https://www.cnblogs.com/McChen/archive/2019/12/15/12044632.html
-Advertisement-
Play Games

首發於微信公眾號《前端成長記》，寫於 2019.12.15 背景 本文記錄刷題過程中的整個思考過程，以供參考。主要內容涵蓋： 題目分析設想 編寫代碼驗證 查閱他人解法 思考總結 目錄 "110.平衡二叉樹" "111.二叉樹的最小深度" "112.路徑總和" "118.楊輝三角" "119.楊輝三角 ...


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

背景

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

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

目錄

Easy

110.平衡二叉樹

題目地址

題目描述

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

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

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

示例 1:

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

    3
   / \
  9  20
    /  \
   15   7

返回 true 。

示例 2:

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

       1
      / \
     2   2
    / \
   3   3
  / \
 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],

    3
   / \
  9  20
    /  \
   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)


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Oracle：row_number()、rank()、dense_rank()
    語法：ROW_NUMBER() OVER()； row_number的用途非常廣泛，排序最好用它，它會為查詢出來的每一行記錄生成一個序號，依次排序且不會重覆，註意使用row_number函數時必須要用over子句選擇對某一列進行排序才能生成序號。 rank函數用於返回結果集的分區內每行的排名，行的排 ...
  • 淺談Mysql重置密碼
    新手剛開始用MySQL的時候可能會很容易忘記登錄密碼，下麵說一下如何重置和修改密碼 第一種方法：直接在命令行視窗操作停止伺服器mysql（這是重點：直接停止）打開CMD 在命令行視窗輸入MySQL安裝的磁碟接著輸入mysql安裝目錄下的bin路徑,比如E>cd amp\mysql5.5\bin，回車 ...
  • MySql安裝配置
    一、準備工作： 1、MySql； 下載地址：https://pan.baidu.com/s/1_jGonvoX8E7JMw1fgA9nZg 提取碼：rx9a 二、安裝MySql： 1、點擊程式運行，選擇“自定義”，點擊“下一步” 2、選擇對應MySql版本，點擊“下一步” 3、點擊“Execute” ...
  • react-native run-ios “Could not find iPhone X simulator”
    react-native run-ios “Could not find iPhone X simulator” ...
  • JS 輪播圖
    JS輪播圖 ...
  • wx-all
    學習這部分時也學了不少代碼，一段一段往這上面寫實在有點~~~ 直接把代碼部署到代碼該在的地方吧，哈哈哈 "這是網址" 把代碼放這上面就好多了，不怕代碼丟，還可保證代碼完整，嘻嘻嘻~~~~~~ ...
  • wx-一個簡單頁面
    一個具有頂部，底部和中間的html頁面，但沒有js 可以改一下頁面的固定樣式部分 ``` ...
  • wx-icon和progress
    基本內容 index.wxml index.js 這一串在這沒有什麼用，是創建時自帶的，下麵這個也是 index.css ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類