daily leetcode - Trie

TODO: compared with B+ Tree

字符串可以单射到链表中，比如 "tree" 对应dummy -> t -> r -> e -> e

"treat" 对应 dummy -> t -> r -> e -> a -> t

如果你有很多单词的时候，很自然的发现这样前缀相同的链表可以合并为一棵树

好处：提升检索效率，复用前缀

树形结构还可以理解为一种决策树

从根节点出发，每一步你在问：

"下一个字符是什么？"

每个节点代表一个状态（已经匹配了多少前缀），每条边代表一个字符选择。到达某个节点意味着你已经确认了从根到此处的整个前缀

查找速度与存了多少个单词完全无关，只取决于查询词本身的长度

理解了前缀树的思想，代码需要注意

1. 一个数本身是自己的前缀

class Trie {

    private static class Node {
        Node[] son = new Node[26];
        boolean isEnd = false;
    }

    private Node root;
    public Trie() {
        root = new Node();
    }

    public void insert(String word) {
        // traverse every character in word and add them to the tree
        Node cur = root;
        for (char c: word.toCharArray()){
            if (cur.son[c - 'a'] == null){
                cur.son[c - 'a'] = new Node();
            }
            cur = cur.son[c - 'a'];
        }
        cur.isEnd = true;
    }

    public boolean search(String word) {
        return find(word) == 0;
    }

    public boolean startsWith(String prefix) {
        return find(prefix) != 1;
    }

    public int find(String word) {
        Node cur = root;
        for (char c: word.toCharArray()){
            if (cur.son[c - 'a'] == null){ // 不匹配返回1
                return 1;
            }
            cur = cur.son[c - 'a'];
        }
        // judge whether isEnd = true
        if (cur.isEnd) return 0;
        else return 2;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

随笔

今日看到一个优秀的学妹的帖子

帖子

本人基本情况如下：
学业成绩目前是软工前1％
已经自学了深度学习、视觉感知、体系结构的课程，目前在一个科研组做cv相关的项目。
python、C、C++都学过了（但没有大量刷LeetCode就只是会用）

学习能力还行，态度认真，自我感觉自己是一个有想法知道自己做什么并且执行力比较强的人。不知道大一暑假想出去找实习的话还需要往简历上加些什么，做些什么工作。

目前想做的方向是多模态或者具身智能相关的吧。（不知道这上做一些论文复现。

长期目标是想保研到做我想做方向的强组，目前应该还是想要去试试做科研这条路的。不知道邮有没有相关的强组，或者我想本科直接联系进清北或者中科院的组难度会不会超级大（）

不知道有无热心学长学姐给给建议目前维持绩点还算轻松，感觉学业上比较游刃有余，所以是挺多的hh）
可能上述文字或者想法幼稚的地方，见谅

回想我当初，随大流不肯翘课，然后还妄图深入钻研数学分析和线性代数，结果最后考的一塌糊涂。

1. 第一性原理。这个词有滥用的嫌疑，但是核心思想是从目标倒推，由此分清主次。考试高分- 题型熟练 - 多刷题 ，各种深入理解对于拿一个高绩点的作用很有限

2. 理智和跟风。我是一个很容易受别人影响的人 从csdiy 到 cs50 cs61ab csapp 皆是如此；但是回头看这些课程其实并没有我想的那么好。说到底还是第一性原理

这个周末完成自己的简历，然后照着简历学