Arts 第八十六周（6/21 ～ 6/27）-一一网

ARTS是什么？
Algorithm：每周至少做一个leetcode的算法题；
Review：阅读并点评至少一篇英文技术文章；
Tip：学习至少一个技术技巧；
Share：分享一篇有观点和思考的技术文章。

Algorithm

题目解析：

在二叉搜索树中找到第 K 小的结点，注意这里的 K 是从 1 起始的。因为是二叉搜索树，我们可以利用它的基本性质来进行思考，也就是右边位置的元素均比左边元素来的大。一提到二叉搜索树基本上都会想到中序遍历，通过中序遍历二叉搜索树得到的顺序是从小到大排列的。于是很容易得到下面的解法：

public int kthSmallest(TreeNode root, int k) {
    List<TreeNode> nodes = new ArrayList<>();

    helper(root, nodes);

    return nodes.get(k - 1).val;
}

private void helper(TreeNode root, List<TreeNode> nodes) {
    if (root == null) {
        return;
    }

    helper(root.left, nodes);
    nodes.add(root);
    helper(root.right, nodes);
}
复制代码

这个解法的时间复杂度是 O(n)，空间复杂度是 O(h + n) 其中 h 是树的高度，如果树是平衡的，那么 h == lgn，最差的情况是 h == n，忽略常数项，空间复杂度也是 O(n)。

题目最后的一个追加问题是问，如果二叉树会被频繁的修改（删除以及插入），那么该怎么优化。我一开始以为题目的意思是对空间或者时间作进一步的优化，于是写出了一个迭代的解法，这个解法通过计数，只要找到第 K 小的结点就直接返回，无需再遍历。这样一来，虽然说最差的时空复杂度还和之前一样，但是会略有优化，如果二叉树是平衡的，空间复杂度可以到 O(lgn)，时间复杂度需要根据 K 来定，平均也是 O(lgn)。

但看了答案才发现这个追加的问题并不是要优化复杂度，而是需要在设计上面进行优化。这样的设计不仅可以对搜索第 K 小的元素有优化，还可以对插入和删除进行优化。这需要在二叉树底部维护一个链表（类似 LRU 的结构），这个优化也是常数级别的，具体的就不细说了。

参考代码：

public int kthSmallest(TreeNode root, int k) {
    TreeNode pointer = root;
    Stack<TreeNode> stack = new Stack<>();

    int count = 0;
    while (pointer != null || !stack.isEmpty()) {
        while (pointer != null) {
            stack.push(pointer);
            pointer = pointer.left;
        }

        pointer = stack.pop();
        if (++count == k) {
            return pointer.val;
        }

        pointer = pointer.right;
    }

    return -1;
}
复制代码

Review

The Weekend Experiment That Will Change Your Life

3 Adventures to Plan for a Better Week

两篇文章出自同一个作者，主题是如何让时间过的更加有效率，如何利用有限的时间享受更多。文章中提到了一个记录时间的方法，其实就是记录下你自己每天都干了什么事，你的时间主要花在哪些地方。因为，想要知道如何提高效率，首先需要知道当下的时间利用有哪些地方存在浪费。

很多时候，我们都会觉得好像平时工作时间的效率还算可以，做了很多事情。但是一到周末，就好像没做什么事情很快就过去了。这是因为工作时间都被任务填充的满满的，你也很清楚自己需要做哪些事情，每天都能看到这些任务的进展。而周末我们并没有很好的计划，我们会认为周末就应该是放松的，啥都不想是最好的。放松并没有错，但是问题是你得清楚具体做什么来放松自己，以及做这个事情所需要的时间。只有做到心中有数，才能更大程度上利用自己的时间，不会现实和自己期望的不一样。

追踪时间和制定一些计划会很耗费时间吗？其实并不是，每天可能只需要和漱口洗脸相同的时间就够了。之所以不去做是因为我们还不想走出自己的舒适区，不想去思考这些问题。但作者也说了，一旦开始追踪并记录自己的时间，你会发现其实你的时间是很多的，只是在不经意间流逝了。另外就是，定一些在周末可以用来放松的计划可以增加你的期望度，让你平时的日子都有个盼头，不会因为眼前的苟且而过于失落或焦虑。具体制定什么样的放松计划就要看个人了，总的来说是可以给你身心带来放松的事情，而且你觉得自己能够从中得到享受。最好能有些变化，因为尝试新的，不一样的东西总能调动人的好奇心，让人更有期待。

Tip

最近由于项目需要，查看了一下关于 Elastic Search 以及 Solr。这两个都是近实时的搜索引擎，那么到底该选择哪一个就成了问题？

首先我们先来看一下它们的共同点，不管是 Elastic Search 还是 Solr，它们底层都是基于一个叫做 Lucene 的 Apache 开源项目。并且这两个技术都是开源的。另外就是，它们设计出来都是为了解决相同的问题，也就是实时搜索以及数据的存储。可能很多人会问，不是有 MySql 以及 Mongo 这样的数据库吗，为什么还需要它们呢？这就要提到一个搜索效率的问题，思考一下这样一个场景，就好比淘宝这样的电商网站，用户在搜索栏输入了 “iphone” 这么一个词。传统的数据库肯定会用这个词和当前数据库中所有的产品信息进行比对来挑选出，假如说数据库中有 10 亿个产品信息，那么这样的比对的代价肯定是非常高昂的。想要更好地解决这个问题，就需要用到 “倒排索引” 这样一个技术，而 Elastic Search 和 Solr 做的就是这个事情。

接下来我们重点说说这两个东西的不同之处，当然我的这些信息也都是参照网上的一些帖子，自己实际用过 Solr，没怎么用过 Elastic Search。

Solr 是一个完全开源的 Apache 项目，也就是说任何人都可以自由提交代码，整个项目是由非盈利的社区来维护的。而 Elastic Search 的背后是 Elastic 公司，虽然说代码也是开源的，但是整个项目的维护是由该公司主导的。

使用方面的话，Elastic Search 会更容易上手，基本上就是拆箱即用，它更像是一个产品。而 Solr 在使用之前就需要搭建一些环境，比如搭建 zooKeeper，还有一些初始化的配置之类的。

如果是针对动态索引的话，ES 会更胜一筹。这里说的动态索引是指实时的更新和建立索引。Solr 因为过高的 IO，不太适用于动态的索引更新。但如果是基于静态索引的话，Solr 会更加的有优势，相比于 ES，它的搜索效率会更高。到底是选择 Solr 还是 ES 可能就得结合实际情况了。

因为 ES 毕竟是一个产品，与它配套的一些工具就会比较齐全。ES 仅仅是 ELK 中的一个负责存储和计算的解决方案。ELK 中还有 LogStash 以及 Beat 来负责数据采集，Kibana 来负责可视化的监控，以及 X-Pack 中的诸多类库。可以说围绕着 ES 的是一个生态圈，应用的场景不仅仅限于实时搜索，还有日志分析、指标分析、安全分析、全文检索 等等。这也是为什么这些年，相比于 Solr，ES 的使用率在不断地增高。

最近也是在学习 Elastic Search，感觉这是一门非常实用的技术，毕竟搜索在大部分业务中都是不可或缺的。

人的一生两个最大的财富是：你的才华和你的时间

李开复写的一个短文。总结下来就是，学会记录自己的时间，用最有效的时间做最重要的事，专注于你真正感兴趣、与你自己的人生目标一致的事情。

文章中触动我的是下面这句话：

要在工作上奋发图强，身体健康固然重要，但是真正能改变你的状态的关键是心理而不是生理上的问题。真正地投入到你的工作中，你需要的是一种态度、一种渴望、一种意志。

重点在最后面那句话上，态度、渴望 以及 意志 究竟指的是什么？每个人的理解可能会有所不同，这里说说自己的理解。

首先是 态度，做任何事情，如果仅仅只是抱着完成任务的态度，那么在做这件事的过程中我们就会把自己的注意力放在如何完成这件事情上，这样其实会错过很多很精彩的发现。我们对一些事物感兴趣的真正原因，往往并不是这件事能够给我们带来什么样的好处。就比如，工作能够给你带来物质基础，但你真的因为这一点对自己的工作感兴趣吗？再比如，加强锻炼合理饮食可以给你一个健康的身体，那你真的为此对这些事情感兴趣吗？反观玩游戏、追剧、刷抖音这些并不能带来任何实质好处的事情，却得到很大一部分人的追捧。这究竟是为什么呢？因为这些东西经过了精心的设计，我们很容易发现其中的精彩和吸引我们兴趣的地方。其实很多事情都有吸引我们兴趣的地方，只是说对于有些事情，这里面的兴趣点需要我们一点点地去发现。回到开头，当你不在以完成任务为导向地去做一件事情的时候，你才有机会发现这件事情中的美和好。这也是我们做事该有的态度。

再来是 渴望。每个人的经历和背景都不尽相同，内心向往的事物也不完全一样。但是话说回来，我们可以问自己一个问题：“我的内心最向往的东西是什么，是什么支撑着我一直走下去？”。小的时候，我们都有梦想，在那个纯真的年代，我们也会毫无保留地告诉周围的人自己心中的梦想是什么。随着自己慢慢长大，我们不在和别人谈论自己的梦想，久而久之，我们甚至忘记了自己的梦想。可能是因为现实，也可能是因为自己的内心发生了变化，我们貌似对梦想不再那么执着。但是不论如何，还是要找到自己真正渴望的东西，这个东西不会因为外界的看法而改变，是你真心想得到的。我相信每个人内心深处都有自己真正渴望得到东西，找到了它你也就找到了你的人生目标和方向。

最后是 意志，这可以解释为坚持或者克制。坚持自己所选择的，克制住自己的欲望，把专注力放在自己坚持的事情上。这个可以说是成事的必要因素，因为做任何事情怕的都是半途而废。既然已经找到了方向，也知道坚持下去会有结果，那何不坚定不移地走下去呢。磕磕绊绊总会有，但你始终清楚这不是最终的结果，不是吗？

文章版权归作者所有，未经允许请勿转载。

THE END

阅读