【Leetcode 做题学算法周刊】第六期
首发于微信公众号《前端成长记》,写于 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)
下一篇: 用ASP+XML打造留言本(3)