ARST打卡第180周[180/521]

发表于 分类于 阅读次数：
lc886_可能的二分法_并查集 【TED演讲】有多少工作要求导致你无法完成工作 钱包赛道复盘和Web3钱包推演 对于LOCK_GAP防止幻读的个人理解

Algorithm

lc886_可能的二分法_并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

/* 
看题意应该是个并查集.
好久没有写了，有点忘了并查集怎么写了...看下题解吧.
看了一下题解，是并查集忘了用递归了...以及并查集一套的连接操作也忘了...汗颜...还是孰能生巧

然后还有染色的BFS，DFS两种做法，都可以看看

链接：https://leetcode.cn/problems/possible-bipartition/solutions/1893341/ke-neng-de-er-fen-fa-by-leetcode-solutio-guo7/
*/
class Solution {
    unordered_map<int, int> fa_map;
public:
    // int findFa(int node) {
    //     if (fa_map.find(node) == fa_map.end()) {
    //         return fa_map[node] = node;
    //     }
    //     fa_map[node] = fa
    //     return 
    // }
    int findFa(int x, vector<int>& fa) {
        return fa[x] < 0 ? x : fa[x] = findFa(fa[x], fa);
    }

    void unit(int x, int y, vector<int>& fa) {
        x = findFa(x, fa);
        y = findFa(y, fa);
        if (x == y) {
            return ;
        }
        if (fa[x] < fa[y]) {
            swap(x, y);
        }
        fa[x] += fa[y];
        fa[y] = x;
    }

    bool isconnect(int x, int y, vector<int>& fa) {
        x = findFa(x, fa);
        y = findFa(y, fa);
        return x == y;
    }

    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        vector<int> fa(n + 1, -1);
        vector<vector<int>> g(n + 1);
        for (auto& p : dislikes) {
            g[p[0]].push_back(p[1]);
            g[p[1]].push_back(p[0]);
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < g[i].size(); ++j) {
                unit(g[i][0], g[i][j], fa);
                if (isconnect(i, g[i][j], fa)) {
                    return false;
                }
            }
        }
        return true;
    }
};

int main(){ 
    return 0;
}

Review

【TED演讲】有多少工作要求导致你无法完成工作

在一种合作性事情中，如果把人们之间所负责的事情区分得越清楚，问责成本越低，就会越降低整体的生产效率，因为人们都只想着把自己分内的事情做好，而不是如何把整个事情变得更好，所以有时候模糊化一些中间的过程，反而能激发团队合作的作用，增加生产力，把事情做得更好。

Tips

钱包赛道复盘和Web3钱包推演

Share-对于LOCK_GAP防止幻读的个人理解

再次推荐阅读《从根儿上理解mysql》

文中说LOCK_GAP锁锁一个区间就能防止幻读，但是我之前对于幻读的理解是只要后面事务操作导致读出了更多的值，那么就算是幻读了，但是这里的LOCK_GAP只锁了很小的一部分，万一我插入其他地方呢？所以我想到应该是把第一次读的gap给锁住了，所以就解决了幻读。

查了一下百度，果然如此:

1
2
3
4
5
6
7
8
9
10
11
事务A读取与搜索条件相匹配的若干行。事务B以插入或删除行等方式来修改事务A的结果集，然后再提交。

幻读是指当事务不是独立执行时发生的一种现象，例如第一个事务对一个表中的数据进行了修改，比如这种修改涉及到表中的“全部数据行”。
同时，第二个事务也修改这个表中的数据，这种修改是向表中插入“一行新数据”。
那么，以后就会发生操作第一个事务的用户发现表中还存在没有修改的数据行，就好象发生了幻觉一样.
一般解决幻读的方法是增加范围锁RangeS，锁定检索范围为只读，这样就避免了幻读。

在数据库定义的四种隔离级别中
最高隔离级别SERIALIZABLE_READ可以保证不出现幻读的问题。
**Repeatable Read (RR)**
针对当前读，**RR隔离级别保证对读取到的记录加锁 (记录锁)，同时保证对读取的范围加锁，新的满足查询条件的记录不能够插入 (间隙锁)**，不存在幻读现象。