A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

背景本文记录刷题过程中的整个思考过程,以供参考。主要内容涵盖:
题目分析设想编写代码验证查阅他人解法思考总结目录110.平衡二叉树111.二叉树的最小深度112.路径总和118.杨辉三角119.杨辉三角ⅡEasy110.平衡二叉树题目地址
题目描述给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过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 submissionsYour 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 submissionsYour 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 submissionsYour 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 submissionsYour 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 submissionsYour 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 submissionsYour 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 submissionsYour 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 submissionsYour 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[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 submissionsYour 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] : 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 submissionsYour 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 = [];        for (var j = 0;j < i + 1;j++){            res.push(C(i, j));        }    }    return res;};结果:
15/15 cases passed (64 ms)Your runtime beats 68.27 % of javascript submissionsYour 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 submissionsYour 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 submissionsYour 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 submissionsYour memory usage beats 60.78 % of javascript submissions (33.7 MB)时间复杂度 O(n^2)

1 个回复

倒序浏览
有问题联系学姐
DKA-2018
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马