13 极客大学-算法训练营-覃超-第十三课.pdf

Trie 树

实战题目

  • 实现 Trie (前缀树) （亚马逊、微软、谷歌在半年内面试中考过）
  • 单词搜索 II （亚马逊、微软、苹果在半年内面试中考过）

  • [ ] 分析单词搜索 2 用 Tire 树方式实现的时间复杂度，请同学们提交在学习总结中。

    并查集模板

    1. // JavaScript
    2. class unionFind {
    3. constructor(n) {
    4.   this.count = n;
    5.   this.parent = new Array(n);
    6.   for (let i = 0; i < n; i++) {
    7.     this.parent[i] = i;
    8.   }
    9. }
    10. find(p) {
    11.   let root = p;
    12.   while (parent[root] !== root) {
    13.     root = parent[root];
    14.   } 
    15.   // 压缩路径
    16.   while (parent[p] !== p) {
    17.     let x = p;
    18.     p = this.parent[p];
    19.     this.parent[x] = root;
    20.   }
    21.   return root;
    22. }
    23. union(p, q) {
    24.   let rootP = find(p);
    25.   let rootQ = find(q); 
    26.   if (rootP === rootQ) return; 
    27.   this.parent[rootP] = rootQ;
    28.   this.count--;
    29. }
    30. }

    参考链接

  • 并查集代码模板

    实战题目

  • [ ] 朋友圈（亚马逊、Facebook、字节跳动在半年内面试中考过）

  • 岛屿数量（近半年内，亚马逊在面试中考查此题达到 361 次）
  • 被围绕的区域（亚马逊、eBay、谷歌在半年内面试中考过）