ARTS 第二十五周（2019.9.16~2019.9.22）

[catcuts]

ARTS 第二十五周（2019.9.16~2019.9.22）

• Algorithm 验证二叉搜索树
• Review Node.js 使用 Elasticsearch 入门（下：实践篇）
• Tip 关于 Symbol 的几个用途
• Share [极客专栏] 26 | 分布式系统的关键技术：流量调度

Algorithm 验证二叉搜索树

题目

验证二叉搜索树

勉强解出，还需深入理解，比如“深度优先”、“广度优先”、“中序遍历”等。

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root, sub/*是否子节点*/) {
    // 无节点，或节点无左右节点，则：
    if (!root) return sub ? { max: -Infinity, min: Infinity } : true;
    if (!root.left && !root.right) return sub ? { max: root.val, min: root.val } : true;

    // 若有节点，且节点有左右节点，则：
    let leftIsValidBST = isValidBST(root.left, true);
    let rightIsValidBST = isValidBST(root.right, true);

    // 若左右节点其中有一个无效，则直接判定为无效
    if (!leftIsValidBST || !rightIsValidBST) return false;
    let isValid = leftIsValidBST.max < root.val && rightIsValidBST.min > root.val;

    return sub ? isValid && {
        max: Math.max(root.val, leftIsValidBST.max, rightIsValidBST.max),
        min: Math.min(root.val, leftIsValidBST.min, rightIsValidBST.min)
    } : isValid;
};

思路：
思路见注释。
每个节点都会遍历到一次，故时间复杂度 = O(n)；不占用额外空间，故空间复杂度 = O(1)。

对比：
与高分对比：
本代码运行 75 个测试用例花费约 72ms，平均一个测试用例约 1ms；
高分代码运行 75 个测试用例花费约 72ms，平均一个测试用例约 1ms。
最高分代码没看懂：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
let pre = null
var isValidBST = function(root, flag) {
    if(!flag) pre = null
    if(root === null) return true
    if(!isValidBST(root.left, true)) return false
    if(pre !== null && (pre.val >= root.val)) return false
    pre = root
    return isValidBST(root.right, true)
};

Review Node.js 使用 Elasticsearch 入门（下：实践篇）

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

点评：
本文对 ElasticSearch 的几个基本操作进行了实践。包括：

• 从 ElasticSearch 官网下载服务端和客户端程序包并运行
• 使用 GET _cat/indices?v 查看已创建的所有索引
• 使用 PUT 索引名称 创建一个索引，并解释其中包含的映射和分析器
• 使用 ElasticSearch Rest API 导入一份莎士比亚文档（大小为 22M）
• 使用 如下请求 获取关键词全文搜索结果：

  GET /shakespeare/_search
  {
    "query" : {
      "match":{
        "text_entry" : "关键词"
      }
    }
  }

• 使用 nodejs 的 request 模块发送上述请求并解析获得结果

扩展阅读：

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

Tip 关于 Symbol 的几个用途

看了 Symbol，发现有几个实用的方面，如：

• 定义实名匿值的常量：

  const DEBUG = Symbol();  // 不用纠结常量的值要设定为什么了，类似于匿名函数不用纠结函数命名

• 定义对象的私有属性：

  // cat.js
  let voice = Symbol('voice');
  class Cat {
      constructor() {
          this[voice] = 'meow';
      }
  };
  module.export = Cat;
  // 以下在另一个文件
  const Cat = require('cat');
  let cat = new Cat();
  // 拿不到 cat[Symbol(voice)]
  // 但打印出来可以看得到
  console.log(cat);  // {[Symbol(voice)]: "meow"}

Share [极客专栏] 26 | 分布式系统的关键技术：流量调度

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