Skip to content

Latest commit

 

History

History
157 lines (114 loc) · 6.53 KB

2019-01-08.md

File metadata and controls

157 lines (114 loc) · 6.53 KB

一. Alogrithm

做了一道按层级遍历二叉树的题目 102. Binary Tree Level Order Traversal

一道主要考察的是广度优先遍历的题目,基本思路就是首先遍历能拿到的所有节点的值,作为一个 list 加入到结果中,然后在遍历这些节点的子节点,以此类推,代码如下:

class Solution {

    private List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> levelOrder(TreeNode root) {

        if (root == null) {
            return result;
        }
        List<TreeNode> nodes = new ArrayList<>();
        nodes.add(root);
        this.bfs(nodes);
        return result;

    }

    public void bfs(List<TreeNode> treeNodes) {
        int length = treeNodes.size();
        if (length == 0) {
            return;
        }

        List<TreeNode> nodes = new ArrayList<>();
        List<Integer> nodeVals = new ArrayList<>();

        for (int i = 0; i < length; i ++) {
            TreeNode node = treeNodes.get(i);
            nodeVals.add(node.val);

            if (node.left != null) {
                nodes.add(node.left);
            }
            if (node.right != null) {
                nodes.add(node.right);
            }
        }

        this.result.add(nodeVals);
        this.bfs(nodes);

    }
}

每个节点都要进行一次访问和判空操作,时间复杂度为 O(N)。

与该题相对的是107. Binary Tree Level Order Traversal II。从底部开始按层遍历二叉树,一种比较简单的方式是将上面代码中每层的数据存放顺序倒过来即可。

this.result.add(nodeVals);
=>
this.result.add(0, nodeVals);

二. Review

读了一篇 Medium 上的文章 How to improve your data structures, algorithms, and problem-solving skills

作者分享了自己利用刷题网站提高自己的数据结构和算法、以及应用数据结构和算法解决问题的能力。主要介绍了如下三个网站:

三者的偏重有所不同,作者分别从数据结构、算法、应该知识解决问题三个层面作了推荐:

数据结构

这一模块作者推荐 HackerRank 网站的 数据结构训练模块。 该模块有很多题目,主要是针对数据结构本身特性的练习,通过该模块的练习我们可以熟悉各种数据结构的特点和对其相应的操作。网站内容如下,可以找到众多列表、树、数组、图等相关的题目。有兴趣的同学可以刷一波:

算法

针对算法的训练,作者推荐了我们非常熟悉的 LeetCode 网站了,不同于 HackerRank 网站 主要针对数据结构特性的训练,LeetCode 的题目更侧重于用算法解决问题,比如 Accounts Merge是针对 UFDS 并查集算法的考察。作者非常推荐用 LeetCode 题目来加强对算法的理解和运用,尤其是 top 100 liked questions 这种受欢迎的题目。

解决问题的能力

最后作者推荐了 Kattis 来帮助我们提高解决问题的能力。里面有几百道题目提供练习,不过需要注意的是里面的问题都没有官方解决方案以及讨论,并且测试用例都是私有的,因此在刷题难度上要比上面提到的两个高不少,很容易让人泄气,所以刚开始时还是更建议刷上面两个网站的题目。

以上是文章的主要内容,算是拓展了一下边界吧,除了 LeetCode 还有很多其他的用来提高算法和数据结构的网站,最近自己一直在抽时间刷 LeetCode,同时学习相关的内容,对自己在数据结构与算法方面的掌握还是有一定的提升的。虽然要具体应用到实际工作中还是有一定的难度,毕竟工作当中大部分的轮子都造好了,但是遇到问题时想方案的思路会有所开阔,坚持下去,不断进步。

三. Tips

分享一下通过 logstash 为索引设置模板的方法把。本周工作时遇到一个问题,5.6 版本的 ES 默认不会给字符串类型的字段创建 keyworkd 子字段,这样会影响实际业务中的一部分查询功能,咨询云厂商之后发现没法给尽快的升级于是只能自己解决了。

ES 提供了两种提前设置索引配置的方式:

  • Dynamic Template 动态模板
  • Index Template 索引模板

前者需要在创建索引时指明,后者提前创建好并指明适配的索引。为了实现在 5.6 版本中自动为字符串类型的字段加一个 keyword 子字段的需求,我们需要将两者结合起来,在索引模板中配置动态模板,可以创建索引模板如下:

{
  "my-data_template": { # 指定模板名称
    "order": 0,
    "template": "[my-data*]", # 
    "settings": {},
    "mappings": {
      "doc": {
        "dynamic_templates": [
          {
            "strings": {
              "match_mapping_type": "string",
              "mapping": {
                "type": "text",
                "fields": {
                  "keyword": {
                    "type": "keyword",
                    "ignore_above": 256
                  }
                }
              }
            }
          }
        ]
      }
    },
    "aliases": {}
  }
}

创建完成后当新的以 my-data 开头的索引创建时就会给字符串类型的字段创建 keyword 子字段了。

当然也可以在 logstash 中进行如下配置:

  elasticsearch {
  		hosts => ["1.1.1.3:9200"]
         index => "my-data_%{_event}"
         document_id => "%{id}"
         action => "update"
         doc_as_upsert => true
         document_type => "doc"
         template => "/usr/local/logstash/index_tmplates/qcdata_template.json" # 指定模板文件
         template_name => "qcdata_template" # 指明模板名
         template_overwrite => true # 是否覆盖已有模板
  }

可以预先创建一个索引模板的 json 文件,内容和我们上面创建的模板内容一样,然后在 logstash 中配置就可以了。

四. Share

暂时没想到有好的分享内容,本周 share 先空缺吧。