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

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

首發於微信公眾號《前端成長記》,寫於 2019.12.06 背景 本文記錄刷題過程中的整個思考過程,以供參考。主要內容涵蓋: 題目分析設想 編寫代碼驗證 查閱他人解法 思考總結 目錄 "100.相同的樹" "101.對稱二叉樹" "104.二叉樹的最大深度" "107.二叉樹的層次遍歷II" "10 ...


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

背景

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

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

目錄

Easy

100.相同的樹

題目地址

題目描述

給定兩個二叉樹,編寫一個函數來檢驗它們是否相同。

如果兩個樹在結構上相同,並且節點具有相同的值,則認為它們是相同的。

示例:

輸入:       1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

輸出: true

輸入:      1          1
          /           \
         2             2

        [1,2],     [1,null,2]

輸出: false

輸入:       1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

輸出: false

題目分析設想

題目直接說了是二叉樹,而二叉樹的遍歷方式有兩種:深度優先和廣度優先,我就從這兩個思路來作答。

編寫代碼驗證

Ⅰ.深度優先

代碼:

/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    if (p === null && q === null) return true
    if (p === null || q === null) return false

    if (p.val !== q.val) return false

    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
};

結果:

  • 57/57 cases passed (52 ms)
  • Your runtime beats 98.81 % of javascript submissions
  • Your memory usage beats 16.66 % of javascript submissions (33.8 MB)
  • 時間複雜度 O(n)n 為節點個數

Ⅱ.廣度優先

代碼:

/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    if (p === null && q === null) return true
    if (p === null || q === null) return false

    let pQ =[p] // 左側比較隊列
    let qQ =[q] // 右側比較隊列

    let res = true

    while(true) {
        if (!pQ.length || !qQ.length) {
            res = pQ.length === qQ.length
            break
        }
        // 當前比較節點
        let curP = pQ.shift()
        let curQ = qQ.shift()
        if ((curP && !curQ) || (!curP && curQ) || (curP && curQ && curP.val !== curQ.val)) {
            res = false
            break
        } else {
            let pL = curP ? curP.left : null
            let pR = curP ? curP.right : null
            if (pL || pR) { // 至少一個存在才有意義
                pQ.push(pL, pR) // 依次推入比較數組,實際上就是廣度優先
            }
            let qL = curQ ? curQ.left : null
            let qR = curQ ? curQ.right : null
            if (qL || qR) { // 至少一個存在才有意義
                qQ.push(qL, qR) // 依次推入比較數組,實際上就是廣度優先
            }
        }
    }

    return res
};

結果:

  • 57/57 cases passed (64 ms)
  • Your runtime beats 73.27 % of javascript submissions
  • Your memory usage beats 15.53 % of javascript submissions (33.8 MB)
  • 時間複雜度 O(n)n 為節點個數

查閱他人解法

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

思考總結

一般碰到二叉樹的題,要麼就深度遍歷,要麼就廣度遍歷。深度優先,也叫先序遍歷。

101.對稱二叉樹

題目地址

題目描述

給定一個二叉樹,檢查它是否是鏡像對稱的。

例如,二叉樹 [1,2,2,3,4,4,3] 是對稱的。

示例:

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下麵這個 [1,2,2,null,3,null,3] 則不是鏡像對稱的:

   1
   / \
  2   2
   \   \
   3    3

說明:

如果你可以運用遞歸和迭代兩種方法解決這個問題,會很加分。

題目分析設想

還是一道二叉樹的題,所以常規思路就是遍歷操作,深度優先或廣度優先都可。鏡像對稱可以觀察到很明顯的特點是有相同的根節點值,且每個樹的右子樹與另一個樹的左字數對稱相等。深度優先的方式,其實就是遞歸的思路,符合題目的說明。

編寫代碼驗證

Ⅰ.深度優先

代碼:

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    function isMirror (l, r) {
        if (l === null && r === null) return true
        if (l === null || r === null) return false

        return l.val === r.val && isMirror(l.left, r.right) && isMirror(l.right, r.left)
    }
    return isMirror(root, root)
};

結果:

  • 195/195 cases passed (68 ms)
  • Your runtime beats 87.74 % of javascript submissions
  • Your memory usage beats 41.48 % of javascript submissions (35.5 MB)
  • 時間複雜度 O(n)n 為節點個數

Ⅱ.廣度優先

代碼:

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if (root === null) return true
    // 初始隊列
    let q = [root.left, root.right]
    // 依次將同級push進隊列,每次取兩個對稱節點進行判斷
    while(q.length) {
        let l = q.shift()
        let r = q.shift()
        if (l === null && r === null) continue
        if (l === null || r === null) return false
        if (l.val !== r.val) return false

        q.push(l.left, r.right, l.right, r.left)
    }
    return true
};

結果:

  • 195/195 cases passed (64 ms)
  • Your runtime beats 94.88 % of javascript submissions
  • Your memory usage beats 28.3 % of javascript submissions (35.6 MB)
  • 時間複雜度 O(n)n 為節點個數

查閱他人解法

看到一個有意思的思路,將樹按照左中右的順序輸入到數組,加上層數,該數組也是對稱的。

Ⅰ.左中右順序輸出數組

代碼:

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if (root === null) return true
    // 輸出數組
    let arr = []
    search(arr, root, 1);
    // 入參分別為輸出,節點和層級
    function search(output, n, k) {
        if (n.left !== null) {
            search(output, n.left, k+1)
        }

        if (n.right !== null) {
            search(output, n.right, k + 1);
        }
    }
     //判斷是否對稱
     let i = 0, j = arr.length - 1
     while (i < j) {
         if (arr[i] != arr[j]) {
             return false
         }
         i++
         j--
     }
     return true
};

結果:

  • 195/195 cases passed (72 ms)
  • Your runtime beats 76.3 % of javascript submissions
  • Your memory usage beats 6.11 % of javascript submissions (36.3 MB)
  • 時間複雜度 O(n)n 為節點個數

思考總結

這道題的大致解法都是遍歷節點或者利用隊列,只是在遞歸的細節上會有些差異。左中右輸出數組的思路很清奇,雖然效率明顯會更低下,但是不失為一種思路。

104.二叉樹的最大深度

題目地址

題目描述

給定一個二叉樹,找出其最大深度。

二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。

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

示例:

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

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

題目分析設想

這道題最基本的思路就是計算出每條子節點的深度,再進行比較。為了提升效率,可以增加同級比對,去除不可能是最長節點的葉節點計算。

所以這裡我就用以下幾種思路來實現深度優先演算法。

  • 遞歸,直接獲取子樹最大高度加 1
  • 利用隊列,求深度轉化為求有多少層

編寫代碼驗證

Ⅰ.遞歸

代碼:

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if (root === null) return 0
    // 左側子樹的最大高度
    let l = maxDepth(root.left)
    // 右側子樹的最大高度
    let r = maxDepth(root.right)
    return Math.max(l, r) + 1
};

結果:

  • 39/39 cases passed (60 ms)
  • Your runtime beats 99 % of javascript submissions
  • Your memory usage beats 45.77 % of javascript submissions (37.1 MB)
  • 時間複雜度 O(n)n 為節點個數

Ⅱ.利用隊列

代碼:

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if (root === null) return 0
    // 隊列
    let q = [root]
    let dep = 0
    while(q.length) {
        let size = q.length
        dep++
        while(size > 0) {
            let node = q.shift()
            if (node.left !== null) q.push(node.left)
            if (node.right !== null) q.push(node.right)
            size--
        }
    }
    return dep
};

結果:

  • 39/39 cases passed (68 ms)
  • Your runtime beats 91.33 % of javascript submissions
  • Your memory usage beats 30.1 % of javascript submissions (37.2 MB)
  • 時間複雜度 O(n)n 為節點個數

查閱他人解法

這裡看到一個用棧的角度來實現的,取棧高度的最大值,其他的基本都是迴圈的細節差異,大體思路一致。

Ⅰ.利用棧

代碼:

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if (root === null) return 0
    // 棧
    let s = [{
        node: root,
        dep: 1
    }]
    let dep = 0

    while(s.length) {
        // 先進後出
        var cur = s.pop()
        if (cur.node !== null) {
            let curDep = cur.dep
            dep = Math.max(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
};

結果:

  • 39/39 cases passed (72 ms)
  • Your runtime beats 81.41 % of javascript submissions
  • Your memory usage beats 66.6 % of javascript submissions (37 MB)
  • 時間複雜度 O(n)n 為節點個數

思考總結

二叉樹的操作,一般就是深度優先和廣度優先,所以基本上就朝這兩個方向上去解,然後進行優化就可以了。

107.二叉樹的層次遍歷II

題目地址

題目描述

給定一個二叉樹,返回其節點值自底向上的層次遍歷。 (即按從葉子節點所在層到根節點所在的層,逐層從左向右遍歷)

例如:

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

    3
   / \
  9  20
    /  \
   15   7

返回其自底向上的層次遍歷為:

[
  [15,7],
  [9,20],
  [3]
]

題目分析設想

這道題在我看來還是兩種方式,深度優先和廣度優先。

  • 深度優先,記錄下每個節點對應的層數後,按層數反向輸出即可
  • 廣度優先,記錄下每層的節點後反向輸出

編寫代碼驗證

Ⅰ.深度優先

代碼:

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
    // 當前層級標識
    let idx = 0
    let res = []

    function levelOrder(node, floor, arr) {
        if (node === null) return arr
        if(arr[floor]) {
            arr[floor].push(node.val)
        } else {
            arr[floor] = [node.val]
        }
        levelOrder(node.left, floor + 1, arr)
        levelOrder(node.right, floor + 1, arr)
        return arr
    }

    return levelOrder(root, idx, res).reverse()
};

結果:

  • 34/34 cases passed (68 ms)
  • Your runtime beats 77.01 % of javascript submissions
  • Your memory usage beats 34.78 % of javascript submissions (34.7 MB)
  • 時間複雜度 O(n)n 為節點個數

Ⅱ.廣度優先

代碼:

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
    if (root === null) return []
    // 初始隊列
    let q = [root]
    let res = []

    while(q.length) {
        // 當前層節點數量
        const count = q.length
        let curArr = []
        for(let i = 0; i < count;i++) {
            const node = q.shift()
            curArr.push(node.val)
            // 將子節點依次推入隊列
            if (node.left) q.push(node.left)
            if (node.right ) q.push(node.right )
        }
        res.push(curArr)
    }
    return res.reverse()
};

結果:

  • 34/34 cases passed (64 ms)
  • Your runtime beats 89.2 % of javascript submissions
  • Your memory usage beats 32.3 % of javascript submissions (34.7 MB)
  • 時間複雜度 O(n)n 為節點個數

查閱他人解法

沒有看到什麼特別的解法,主要都是按 BFS 和 DFS 來處理,要麼迭代,要麼遞歸等等。

這裡就介紹下別的吧,在第一種解法中我們使用的是前序優先,當然用中序優先或後序優先也可以,下麵代碼可以說明區別:

// 先序,順序為 根 -> 左 -> 右
function levelOrder(node, floor, arr) {
    if(arr[floor]) {
        arr[floor].push(node.val)
    } else {
        arr[floor] = [node.val]
    }

    levelOrder(node.left, floor + 1, arr)
    levelOrder(node.right, floor + 1, arr)
    return arr
}
// 中序,順序為 左 -> 根 -> 右
function levelOrder(node, floor, arr) {
    levelOrder(node.left, floor + 1, arr)

   if(arr[floor]) {
       arr[floor].push(node.val)
   } else {
       arr[floor] = [node.val]
   }

    levelOrder(node.right, floor + 1, arr)
    return arr
}
// 後序,順序為 左 -> 右 -> 根
function levelOrder(node, floor, arr) {
    levelOrder(node.left, floor + 1, arr)
    levelOrder(node.right, floor + 1, arr)

    if(arr[floor]) {
        arr[floor].push(node.val)
    } else {
        arr[floor] = [node.val]
    }
    return arr
}

思考總結

二叉樹的題目就根據情況在深度優先和廣度優先中擇優選擇即可,基本不會有太大的問題。

108.將有序數組轉換為二叉搜索樹

題目地址

題目描述

將一個按照升序排列的有序數組,轉換為一棵高度平衡二叉搜索樹。

本題中,一個高度平衡二叉樹是指一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 1。

示例:

給定有序數組: [-10,-3,0,5,9],

一個可能的答案是:[0,-3,9,-10,null,5],它可以表示下麵這個高度平衡二叉搜索樹:

      0
     / \
   -3   9
   /   /
 -10  5

題目分析設想

這裡有兩點要註意的:高度平衡二叉樹要求每個節點的左右兩個子樹的高度差的絕對值不超過 1;而二叉搜索樹要求左子樹上所有節點值小於根節點,右子樹上所有節點值大於根節點。

而題目給出的是一個有序的數組,所以可以直接考慮二分後進行處理,我這就直接遞歸作答:找到根節點,遞歸生成左右子樹。

編寫代碼驗證

Ⅰ.遞歸

代碼:

/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
    if (!nums.length) return null
    // 中位數,用偏移避免溢出
    const mid = nums.length >>> 1
    const root = new TreeNode(nums[mid])
    root.left = sortedArrayToBST(nums.slice(0, mid))
    root.right = sortedArrayToBST(nums.slice(mid + 1))
    return root
};

結果:

  • 32/32 cases passed (80 ms)
  • Your runtime beats 70.72 % of javascript submissions
  • Your memory usage beats 29.79 % of javascript submissions (37.8 MB)
  • 時間複雜度 O(n)

查閱他人解法

這裡看到另外一種解法,先創建一個平衡二叉樹,然後中序遍歷樹同時遍曆數組即可,因為中序遍歷出來的剛好是有序數組。

Ⅰ.創建樹後中序遍曆數組賦值

代碼:

/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
    if (!nums.length) return null

    // 節點總數
    let len = nums.length
    let root = new TreeNode(-1);
    let q = [root]
    // 已經創建了根節點
    len--
    while(len) {
        const node = q.shift()
        // 左子樹
        const l = new TreeNode(-1)
        q.push(l)
        node.left = l
        len--
        if (len) {
            // 右子樹
            const r = new TreeNode(-1)
            q.push(r)
            node.right = r
            len--
        }
    }

    let i = 0
    inorder(root)
    function inorder(node) {
        if (node === null) return
        inorder(node.left)
        node.val = nums[i++]
        inorder(node.right)
    }

    return root
};

結果:

  • 32/32 cases passed (72 ms)
  • Your runtime beats 93.4 % of javascript submissions
  • Your memory usage beats 24.12 % of javascript submissions (37.8 MB)
  • 時間複雜度 O(n)

思考總結

這裡其實是個逆向思維,之前是二叉樹輸出數組,現在變成數組轉成二叉樹。剛好可以翻一下前序中序和後序的區別,這裡中序就可以了。不過這道題我還是更推薦遞歸二分求解。

(完)


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


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

-Advertisement-
Play Games
更多相關文章
  • 這裡我就不給大家詳細說明瞭直接附圖: js代碼: layui.use(['layer', 'form','xform','layer'], function () { var element = layui.element; var form = layui.form; var layer = la ...
  • // 用n的階乘來演示 保存上一步計算的數據,進行下一次計算時候先判斷是否有上次執行過的,如果有直接獲取保存的值然後再進行下一步計算 // n! n*(n-1)*....*2*1 // 0! = 1 // n! = n*(n-1)! // 實現記憶前 var count = 0 // 執行的次數 f ...
  • 運算符 賦值運算符 用於給變數賦值。 y=5;/z=2; 算術運算符 即算數符號,是基本算數運算。+ 加 / - 減/ * 乘/ / 除/ % 取餘數/ ++ 自增(y++先賦值再自增/++y先自增再賦值)/ -- 自減,和自增同理/ 複合運算符 += 加等 x+=y等同於 x=x+y 其它的原理相 ...
  • JavaScript的組成 ·ECMAScript 描述了語言的語法和基本對象/ ·DOM 文檔對象模型,描述處理網頁內容/ BOM 瀏覽器對象模型 描述與瀏覽器進行交互的方法和介面 引入方式/ head標簽內/body標簽內 一般在</body>結束標簽錢插入script的標簽 <script> ...
  • 一、iView(View UI) 1、簡介 官網:https://www.iviewui.com/ 倉庫:https://github.com/view-design/ViewUI iView 與 View UI 本質上是一個東西,隨著版本的升級,iView (4.0)改名為 View UI。是一套 ...
  • 這個博客寫了好多前端的知識,有如下內容 "鏈接" ( ^▽^ )( ^▽^ )( ^▽^ ) "html" "css" "JavaScript" "jQuery" "ajax" "canvas" "nodejs" "mysql" "mongodb" "angular" 還有一些數據結構的知識和pyt ...
  • 作者:個人微信公眾號:程式猿的月光寶盒 項目中使用了Mybatis的PageHelper分頁插件後的js文件 js / 初始化首頁數據 / function initData(pageNo) { //清空原來的數據,找到第一個以外的tr,並移除,用 :gt() $("tr:gt(0)").remov ...
  • 1.Ajax非同步按下回車提交表單;2.isEmpty()判斷input框是否為空 ...
一周排行
    -Advertisement-
    Play Games
  • Timer是什麼 Timer 是一種用於創建定期粒度行為的機制。 與標準的 .NET System.Threading.Timer 類相似,Orleans 的 Timer 允許在一段時間後執行特定的操作,或者在特定的時間間隔內重覆執行操作。 它在分散式系統中具有重要作用,特別是在處理需要周期性執行的 ...
  • 前言 相信很多做WPF開發的小伙伴都遇到過表格類的需求,雖然現有的Grid控制項也能實現,但是使用起來的體驗感並不好,比如要實現一個Excel中的表格效果,估計你能想到的第一個方法就是套Border控制項,用這種方法你需要控制每個Border的邊框,並且在一堆Bordr中找到Grid.Row,Grid. ...
  • .NET C#程式啟動閃退,目錄導致的問題 這是第2次踩這個坑了,很小的編程細節,容易忽略,所以寫個博客,分享給大家。 1.第一次坑:是windows 系統把程式運行成服務,找不到配置文件,原因是以服務運行它的工作目錄是在C:\Windows\System32 2.本次坑:WPF桌面程式通過註冊表設 ...
  • 在分散式系統中,數據的持久化是至關重要的一環。 Orleans 7 引入了強大的持久化功能,使得在分散式環境下管理數據變得更加輕鬆和可靠。 本文將介紹什麼是 Orleans 7 的持久化,如何設置它以及相應的代碼示例。 什麼是 Orleans 7 的持久化? Orleans 7 的持久化是指將 Or ...
  • 前言 .NET Feature Management 是一個用於管理應用程式功能的庫,它可以幫助開發人員在應用程式中輕鬆地添加、移除和管理功能。使用 Feature Management,開發人員可以根據不同用戶、環境或其他條件來動態地控制應用程式中的功能。這使得開發人員可以更靈活地管理應用程式的功 ...
  • 在 WPF 應用程式中,拖放操作是實現用戶交互的重要組成部分。通過拖放操作,用戶可以輕鬆地將數據從一個位置移動到另一個位置,或者將控制項從一個容器移動到另一個容器。然而,WPF 中預設的拖放操作可能並不是那麼好用。為瞭解決這個問題,我們可以自定義一個 Panel 來實現更簡單的拖拽操作。 自定義 Pa ...
  • 在實際使用中,由於涉及到不同編程語言之間互相調用,導致C++ 中的OpenCV與C#中的OpenCvSharp 圖像數據在不同編程語言之間難以有效傳遞。在本文中我們將結合OpenCvSharp源碼實現原理,探究兩種數據之間的通信方式。 ...
  • 一、前言 這是一篇搭建許可權管理系統的系列文章。 隨著網路的發展,信息安全對應任何企業來說都越發的重要,而本系列文章將和大家一起一步一步搭建一個全新的許可權管理系統。 說明:由於搭建一個全新的項目過於繁瑣,所有作者將挑選核心代碼和核心思路進行分享。 二、技術選擇 三、開始設計 1、自主搭建vue前端和. ...
  • Csharper中的表達式樹 這節課來瞭解一下表示式樹是什麼? 在C#中,表達式樹是一種數據結構,它可以表示一些代碼塊,如Lambda表達式或查詢表達式。表達式樹使你能夠查看和操作數據,就像你可以查看和操作代碼一樣。它們通常用於創建動態查詢和解析表達式。 一、認識表達式樹 為什麼要這樣說?它和委托有 ...
  • 在使用Django等框架來操作MySQL時,實際上底層還是通過Python來操作的,首先需要安裝一個驅動程式,在Python3中,驅動程式有多種選擇,比如有pymysql以及mysqlclient等。使用pip命令安裝mysqlclient失敗應如何解決? 安裝的python版本說明 機器同時安裝了 ...