ARTS 第二十八周（2019.10.7~2019.10.13）

[catcuts]

ARTS 第二十八周（2019.10.7~2019.10.13）

• Algorithm 对称二叉树
• Review 软件设计模式之“命令模式”
• Tip 尾调用优化
• Share [极客专栏] 96 | 高效学习：源头、原理和知识地图

Algorithm 对称二叉树

题目

对称二叉树

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if (!root) return true;
    return _isSymmetric(root.left, root.right);
};

function _isSymmetric(left, right) {
    // `left` 节点 和 `right` 节点有一个为 `null` 且另一个不为 `null`
    if ((!left && right) || (left && !right)) return false;
    // `left` 节点 和 `right` 节点都为 `null`
    if (!left && !right) return true;
    // `left` 节点 和 `right` 节点都不为 `null`，且其 `val` 值不相等
    if (left.val !== right.val) return false;
    // 递归判断
    return _isSymmetric(left.left, right.right) && _isSymmetric(left.right, right.left);
}

执行结果：通过
执行用时：68 ms, 在所有 javascript 提交中击败了 96.62% 的用户
内存消耗：35.5 MB, 在所有 javascript 提交中击败了 32.48% 的用户

思路：
递归地判断 left 节点和 right 节点是否是彼此对称的（_isSymmetric）。
递归结束条件是：

• left 节点 和 right 节点有一个为 null 且另一个不为 null——返回 false；或
• left 节点 和 right 节点都为 null——返回 true；或
• left 节点 和 right 节点都不为 null，且其 val 值不相等——返回 false

（看起来用不了尾递归优化）

对比：
与高分对比：
本代码运行 195 个测试用例花费约 68ms，平均一个测试用例约 0.35ms；
高分代码运行 195 个测试用例花费约 68ms，平均一个测试用例约 0.35ms。
思路一致代码略。

Review 软件设计模式之“命令模式”

阅读：
Design Patterns: Command

点评：
本文介绍并实践了软件设计中的命令模式（Command Pattern）。

命令模式的主要思想是：

• 使用抽象对象代表某个行为并执行，
• 而非直接调用实现该行为的具体方法。
• （该对象即为执行该“行为”的“命令”）

适用于：需要对行为进行记录、撤销、重做、事务等应用场景。
原因：

• 使用对象代表行为，对象能被记录在自定义的数据结构中（如数组或堆栈等）
• 采用合适的数据结构和应用逻辑即可方便实现撤销、重做、事务等复杂应用
• 如果直接调用行为的具体方法，不仅会使行为发起者和实现者产生紧密耦合，也不方便实现上述功能

另外，它也体现了“依赖倒置原则”：

• 高层（行为发起者）不依赖于低层（行为实现者）实现
• 两者都应该依赖于其抽象（对命令的抽象，即为命令对象）

依赖倒置原则中，依赖抽象的思想是源于，抽象的事物会比具体的事物对外更不容易发生变化。

下图是命令模式的基本结构：

文中对此举了一个股票买卖的例子作为实现：

自己看完后也学着画了一下 UML 图（不是很规范的，主要是固化自己的理解）：

文中还举了一个星球大战机器人 R2D2 的例子，也很有趣。

阅读参考：
命令模式 - 维基百科，自由的百科全书
命令模式 - 菜鸟教程
深入浅出UML类图 - uml.org.cn

Tip 尾调用优化

尾调用优化是指：函数中调用函数时，如果被调用函数是调用函数的最后一步，则调用堆栈中只会保存被调用函数的信息，从而达到内存占用优化的效果。

尾调用优化特别适用于优化递归，被称为尾递归。因为递归往往要保存很多函数调用堆栈，所以不注意就会发生栈溢出，此时可以考虑使用尾递归来优化。

例如：

不使用尾递归优化的阶乘函数：最多需要保存 n 个调用记录，堆栈空间复杂度 O(n)

function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}

factorial(5) // 120

使用尾递归优化后：此时调用记录总是只有最后一个，堆栈空间复杂度 O(1)

function factorial(n, total = 1/*提供使用者调用时的默认参数*/) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

factorial(5) // 120

还需要注意的是：

• ES6 明确规定，所有 ES 实现都必须部署尾调用优化
• ES6 的尾调用优化只在严格模式下开启，正常模式是无效的
  因为：正常模式下，函数内部有一下两个变量，用于跟踪函数的调用栈：
  • arguments：返回调用时函数的参数。
  • func.caller：返回调用当前函数的那个函数。

参考：尾调用优化 - 阮一峰的网络日志

Share [极客专栏] 96 | 高效学习：源头、原理和知识地图

分享一篇极客“左耳听风”专栏文章（据说可限10位免费阅读哦）
96 | 高效学习：源头、原理和知识地图

这是一篇关于如何高效学习的方法论和实践指导的系列文章（之二），

注意是“高效学习”而非“高速学习”。

本文强调了挑选知识和信息源、注重基础和原理和使用知识地图的重要性。

优质的信息源包含如下特质：

• 一手的
  （因为这样才能真正锻炼自己，养成独立发掘和思考的能力）
• 有佐证、有数据、有引用或是有权威人士或大公司生产系统背书的
  （因为这意味着材料是小心求证的，或是经时间和实践检验过的）
• 有注入经验和思考的，可以引人深思的，信息密集的

优质信息源推荐：Medium
因为很多文章都 Google 到了 Medium 上。

基础和原理在信息爆炸时代尤为重要的理由：

• 基础和原理不到位，会影响我们对事物的理解，甚至不能理解为什么是这样
  （因此如果我们对事物有不理解时，通常是我们基础没跟上，要先补基础）
• 基础和原理都是经过长期时间和实践考验的，
  蕴涵很多人类智慧结晶，会给我们带来很多启示和帮助

知识地图带来的好处：

• 绘制知识地图是对学习内容脉络的梳理，顺藤摸瓜便于记住关键的知识点并帮助找到关键答案
• 当出现一些我们还未了解的知识点时，可以随时往知识地图上挂，从而使学习更为系统和全面

补充：关于练好英文的重要性：
英文对于我们来说至关重要，尤其对于计算机知识。

• 如果我们平时用百度搜中文关键字就能找到自己想要的知识，
  那么我们一定远远落后于这个时代了。
• 如果我们平时用谷歌搜英文关键字可以找到自己想要的知识，
  那么我们算是能跟上这个时代。←
• 如果我们能在社区里跟社区里的大牛交流得到答案，
  那么我们就算是领先于这个时代了。