学习记录贴

2024.04.16
LC: 复习了一下二叉树前序遍历（recursive, iterative, Morris-traversal)

Rust: https://www.youtube.com/watch?v=o2ob8zkeq2s&t=1s  看了前44分钟

今天决定早睡早起！（10-6）明天早上6点起床！

2024.04.17

LC: 中序和后序遍历二叉树复习，每日一题+premium每日一题，都是easy不说了

SD: Grokking 的 Back-of-the-envelope Calculations 看完了

JG的 decrust tokio又往后看了40分钟~

2024.04.18~2024.04.24
LC: 二叉树的探索专题还剩下最后两题
oncall week
这周可能不学习了，工作好忙，反正就也没想到在海外还能每天干9+小时活

2024.04.25~2024.04.28
LC：二叉树的探索专题剩下的两题做完了，还有 几道 Array 的 Easy
周日做了两题挺好的：
1. Number of Islands II -> 考并查集的
2. Sum of Distances in Tree -> 这题如果看不懂美版的题解，可以看这一篇： https://leetcode.cn/problems/sum ... g-huan-gen-dp-6bgb/

因为做了考并查集的题，所以开了 Graph 的探索专题（下周会复习Graph）

2024.04.29~04.30
下班之后直接睡大觉了。

2024.05.01
LC 2easy+1medium
复习了并查集

来列一下并查集的板子：
1. 朴素版-1

1. class UnionFind {
   
2. public:
   
3.     UnionFind(int sz) : root(sz) {
   
4.         for (int i = 0; i < sz; i++) {
   
5.             root[i] = i;
   
6.         }
   
7.     }
   
8. 
   
9.     int find(int x) {
   
10.         return root[x];
    
11.     }
    
12. 
    
13.     void unionSet(int x, int y) {
    
14.         int rootX = find(x);
    
15.         int rootY = find(y);
    
16.         if (rootX != rootY) {
    
17.             for (int i = 0; i < root.size(); i++) {
    
18.                 if (root[i] == rootY) {
    
19.                     root[i] = rootX;
    
20.                 }
    
21.             }
    
22.         }
    
23.     }
    
24. 
    
25.     bool connected(int x, int y) {
    
26.         return find(x) == find(y);
    
27.     }
    
28. 
    
29. private:
    
30.     vector<int> root;
    
31. };

复制代码

2. 朴素版-2

1. class UnionFind {
   
2. public:
   
3.     UnionFind(int sz) : root(sz) {
   
4.         for (int i = 0; i < sz; i++) {
   
5.             root[i] = i;
   
6.         }
   
7.     }
   
8. 
   
9.     int find(int x) {
   
10.         while (x != root[x]) {
    
11.             x = root[x];
    
12.         }
    
13.         return x;
    
14.     }
    
15. 
    
16.     void unionSet(int x, int y) {
    
17.         int rootX = find(x);
    
18.         int rootY = find(y);
    
19.         if (rootX != rootY) {
    
20.             root[rootY] = rootX;
    
21.         }
    
22.     }
    
23. 
    
24.     bool connected(int x, int y) {
    
25.         return find(x) == find(y);
    
26.     }
    
27. 
    
28. private:
    
29.     vector<int> root;
    
30. };

复制代码

3. 进阶版-1： 带rank权重

1. class UnionFind {
   
2. public:
   
3.     UnionFind(int sz) : root(sz), rank(sz) {
   
4.         for (int i = 0; i < sz; i++) {
   
5.             root[i] = i;
   
6.             rank[i] = 1;
   
7.         }
   
8.     }
   
9. 
   
10.     int find(int x) {
    
11.         while (x != root[x]) {
    
12.             x = root[x];
    
13.         }
    
14.         return x;
    
15.     }
    
16. 
    
17.     void unionSet(int x, int y) {
    
18.         int rootX = find(x);
    
19.         int rootY = find(y);
    
20.         if (rootX != rootY) {
    
21.             if (rank[rootX] > rank[rootY]) {
    
22.                 root[rootY] = rootX;
    
23.             } else if (rank[rootX] < rank[rootY]) {
    
24.                 root[rootX] = rootY;
    
25.             } else {
    
26.                 root[rootY] = rootX;
    
27.                 rank[rootX] += 1;
    
28.             }
    
29.         }
    
30.     }
    
31. 
    
32.     bool connected(int x, int y) {
    
33.         return find(x) == find(y);
    
34.     }
    
35. 
    
36. private:
    
37.     vector<int> root;
    
38.     vector<int> rank;
    
39. };

复制代码

4. 进阶版-2： 状态压缩（把deep tree压成flat的呸呸呸我在说些啥）

1. class UnionFind {
   
2. public:
   
3.     UnionFind(int sz) : root(sz) {
   
4.         for (int i = 0; i < sz; i++) {
   
5.             root[i] = i;
   
6.         }
   
7.     }
   
8. 
   
9.     int find(int x) {
   
10.         if (x == root[x]) {
    
11.             return x;
    
12.         }
    
13.         return root[x] = find(root[x]);
    
14.     }
    
15. 
    
16.     void unionSet(int x, int y) {
    
17.         int rootX = find(x);
    
18.         int rootY = find(y);
    
19.         if (rootX != rootY) {
    
20.             root[rootY] = rootX;
    
21.         }
    
22.     }
    
23. 
    
24.     bool connected(int x, int y) {
    
25.         return find(x) == find(y);
    
26.     }
    
27. 
    
28. private:
    
29.     vector<int> root;
    
30. };

复制代码

5. 进阶版-3： 状态压缩+rank

1. class UnionFind {
   
2. public:
   
3.     UnionFind(int sz) : root(sz), rank(sz) {
   
4.         for (int i = 0; i < sz; i++) {
   
5.             root[i] = i;
   
6.             rank[i] = 1;
   
7.         }
   
8.     }
   
9. 
   
10.     int find(int x) {
    
11.         if (x == root[x]) {
    
12.             return x;
    
13.         }
    
14.         // Some ranks may become obsolete so they are not updated
    
15.         return root[x] = find(root[x]);
    
16.     }
    
17. 
    
18.     void unionSet(int x, int y) {
    
19.         int rootX = find(x);
    
20.         int rootY = find(y);
    
21.         if (rootX != rootY) {
    
22.             if (rank[rootX] > rank[rootY]) {
    
23.                 root[rootY] = rootX;
    
24.             } else if (rank[rootX] < rank[rootY]) {
    
25.                 root[rootX] = rootY;
    
26.             } else {
    
27.                 root[rootY] = rootX;
    
28.                 rank[rootX] += 1;
    
29.             }
    
30.         }
    
31.     }
    
32. 
    
33.     bool connected(int x, int y) {
    
34.         return find(x) == find(y);
    
35.     }
    
36. 
    
37. private:
    
38.     vector<int> root;
    
39.     vector<int> rank;
    
40. };

复制代码

以上内容来自Leetcode美国区的Explore Graph~
贴在这里防止忘了2333但是并查集挺经典的...感觉也不怎么会忘记
话说一亩三分地的编辑器有朝一日可不可以支持Markdown。。。代码格式全都乱了。。。
洗洗睡了~

2024.05.02~05.03
划水，追动画片《虹猫蓝兔七侠传》

2024.05.04
超超超超级努力的一天！！！！
先刷了三个长达1小时的broadcast，然后刷题（今天真的刷了好多题。。。好累）
打了一下周赛，好久没打周赛了（上一次还是在21年），我以为晚上8点半周赛结束，结果打开LC发现还有半小时，就水了前三题，最后一题没来及也没想做。。。

补充内容 (2024-05-05 14:03 +08:00):

补充：我昨天发现这帖子居然有人收藏了emmmm


所以我在想要不以后更新一些真的很有意思的东西，比如说我在看的某些技术博客

2024.05.06
三道LC
1. 每日一题：Double a Number Represented as a Linked List
2. 并查集：Number of Connected Components in an Undirected Graph
3. 数组：        Increasing Triplet Subsequence

Grokking System design 看到 Load balancer

累了，休息了

2024.05.07-2024.05.08
记不太清了，但应该是刷题了/doge
就算没刷题我应该也看了几篇系统设计，这周的educative.io 是每天签到的

2024.05.09
加班，我花了好长时间跑一个loadtest 但是跑出来的结果根本没办法用我目前的知识储备解释，用了好多办法来mitigate impact 但没有完全mitigate(两三百微秒的延迟）不知道发生了啥/裂开🤯
工作到10点也没搞出来，沮丧地睡觉了

2024.05.10
无，看极光！极光超好看！
约了本科的同学，结果他带来了更多他研究生的同学，于是在晚上十点半，一大伙人浩浩荡荡地走山里的trail ，有说有笑特别开心🥳
极光在11点达到峰值，真是太好看了。
想想这还是一件非常神奇的事情：虽然大家互不认识，甚至在不同地方，但是此时此刻我们看到了同一片奇景。

2024.05.11
请已经离职的前辈吃烤鸭……温哥华全聚德的烤鸭真的好一般，好想回国去吃烤鸭……

正题：
1. LC周赛，三题，被第二题坑了，奇耻大辱WA了7次心态直接崩掉……安慰下自己，毕竟好久没做dp 了
好久没打周赛了，我意识到cout 会TLE ……

2. Grokking sd 看了key-value store, 还有一个youtube 但是讲一致性哈希的时候不够深入，一致性哈希还是看Alex xu 的sd 书第一卷比较好。

Update：
从05/24开始我会在小红书上争取每天发布一篇tech blog的中文概要，欢迎follow~
some links:  http://xhslink.com/hTFoHK

05/24 tech blog: https://medium.com/pinterest-eng ... terest-30bad30dabff

但是个人觉得还是看一些system相关的blog长进比较大。