ARTS 第十一周（2019.9.9~2019.9.15）

[catcuts]

ARTS 第十一周（2019.9.9~2019.9.15）

• Algorithm 二叉树的最大深度
• Review Node.js 使用 Elasticsearch 入门（上）
• Tip 中止数组的 map、forEach、every、some 过程
• Share [极客专栏] 25 | 分布式系统的关键技术：服务调度

Algorithm 二叉树的最大深度

题目

二叉树的最大深度

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if (!root) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};

思路：
对于某个节点，其最大深度为自身 1 加上 其左节点和右节点二者的深度最大值。
而左节点或右节点也可以作为某节点，故形成递归，如上代码所示。
每个节点都会遍历到一次，故时间复杂度 = O(n)；不占用额外空间，故空间复杂度 = O(1)。

对比：
与高分对比：
本代码运行 39 个测试用例花费约 92ms，平均一个测试用例约 2.4ms；
高分代码运行 39 个测试用例花费约 92ms，平均一个测试用例约 2.4ms。
递归思路一致代码略。
官方还提供了迭代思路和代码。
详见LeetCode 题解 | 104. 二叉树的最大深度。

Review Node.js 使用 Elasticsearch 入门（上）

阅读：
Introduction to Elasticsearch Using Node.js—Part 1

点评：
本文介绍了 ElasticSearch 的几个核心概念：

• 集群（Cluster）：一群节点的集合，其中一个节点为主节点，负责管控各节点
• 节点（Node）：存储数据的服务器。特点是：
  • 可加入指定名称的集群，接受索引或查询
  • 默认加入名为 “elasticsearch” 的集群
  • 可向所在集群中其它节点发起索引或查询
• 索引（Index）：一群具有相似特性的文档的集合（类似于表）
• 文档（Document）：一条包含多个字段及其值的 JSON 格式数据
• 分片（Shard）：一个较大的索引可以拆分为多个分片，分布到各个节点存储。作用是：
  • 避免因单个索引太大导致节点不能承受
  • 分布式存储，有助于并行索引提高性能
• 副本（Replica）：分片的冗余复制，全称 “Replica Shards”
• 映射（Mapping）：定义文档字段的类型等元数据
• 分析器（Analyzer）：将原始文本最终转化为一个或多个词元（Token）。它由三部分组成：
  • 字符过滤器（Character Filter）：原始文本转为一个或多个字符串
  • 分词器（Tokenizer）：一个或多个字符串转为一个或多个词元
  • 词元过滤器（Token Filter）：一个或多个词元转为另一种形式的词元
    （文末有图文示例）
• 倒排索引（Inverted Index）：一种索引结构

扩展阅读：

• Elasticsearch中文文档
• Elasticsearch权威指南

Tip 中止数组的 map、forEach、every、some 过程

数组遍历的方法除了使用 for 循环，还可以使用函数式编程的 map、forEach、every、some 等
除了 for 循环，其它都不能使用 break 来中止遍历，使用 throw Error 的方法又差强人意

map 和 forEach 中止遍历的方法：修改数组

var array = [1, 2, 3, 4, 5];

array.map(function(item, index) {
    if (item === 2) {
        array = array.concat(array.splice(index, array.length - index));
    }
    console.log(item); //只输出1,2
});

array.forEach(function(item, index) {
    if (item === 2) {
        array = array.concat(array.splice(index, array.length - index));
    }
    console.log(item); //只输出1,2
});

every 和 some 中止遍历的方法：every false、some true

every 碰到 return false 的时候，遍历中止
some 碰到 return ture 的时候，遍历中止

var a = [1, 2, 3, 4, 5];

a.every(function(item, index, arry) {
    console.log(item); //返回1,2
    if (item === 2) {
        return false
    } else {
        return true
    }
})

a.some(function(item, index, arry) {
    console.log(item); //返回1,2
    if (item === 2) {
        return true
    } else {
        return false
    }
})

参考：如何在Array.forEach的循环里break

Share [极客专栏] 25 | 分布式系统的关键技术：服务调度

分享一篇极客“左耳听风”专栏文章（据说可限10位免费阅读哦）
25 | 分布式系统的关键技术：服务调度