【Leetcode 做题学算法周刊】第六期 #49

ChenJiaH · 2019-12-15T08:31:09Z

首发于微信公众号《前端成长记》，写于 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)

The text was updated successfully, but these errors were encountered:

ChenJiaH added the leetcode leetcode做题学算法 label Dec 15, 2019

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

【Leetcode 做题学算法周刊】第六期 #49

【Leetcode 做题学算法周刊】第六期 #49

ChenJiaH commented Dec 15, 2019

【Leetcode 做题学算法周刊】第六期 #49

【Leetcode 做题学算法周刊】第六期 #49

Comments

ChenJiaH commented Dec 15, 2019

背景

目录

Easy

110.平衡二叉树

题目描述

题目分析设想

编写代码验证

查阅他人解法

思考总结

111.二叉树的最小深度

题目描述

题目分析设想

编写代码验证

查阅他人解法

思考总结

112.路径总和

题目描述

题目分析设想

编写代码验证

查阅他人解法

118.杨辉三角

题目描述

题目分析设想

编写代码验证

查阅他人解法

思考总结

119.杨辉三角Ⅱ

题目描述

题目分析设想

编写代码验证

查阅他人解法

思考总结