Algorithm
lc1494_并行课程II
思路: 像有依赖的背包贪心，感觉要模拟这个有向无环图__但是不知道咋写–看题解学习一下
震惊发现windows chrome未登录状态下还有两个英文版的tips，而mac chrome就没有tips
看了题解，发现子集和前置条件的逻辑还是挺烧脑子的，尽量结合示例来看
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
|
class Solution {
public:
int minNumberOfSemesters(int n, vector<vector<int>>& relations, int k) {
vector<int> dp(1 << n, INT_MAX);
vector<int> need(1 << n, 0);
for (auto& edge : relations) {
need[(1 << (edge[1] - 1))] |= 1 << (edge[0] - 1);
}
dp[0] = 0;
for (int i = 1; i < (1 << n); ++i) {
need[i] = need[i & (i - 1)] | need[i & (-i)];
if ((need[i] | i) != i) { // i 中有任意一门课程的前置课程没有完成学习
continue;
}
// 下面已经是把前置课程都完成了，所以可以减去前置课程
int valid = i ^ need[i]; // 当前学期可以进行学习的课程集合
if (__builtin_popcount(valid) <= k) { // 如果个数小于 k，则可以全部学习，不再枚举子集
dp[i] = min(dp[i], dp[i ^ valid] + 1);
} else { // 否则枚举当前学期需要进行学习的课程集合
for (int sub = valid; sub; sub = (sub - 1) & valid) {
if (__builtin_popcount(sub) <= k) {
dp[i] = min(dp[i], dp[i ^ sub] + 1);
}
}
}
}
return dp[(1 << n) - 1];
}
};
// 链接：https://leetcode.cn/problems/parallel-courses-ii/solutions/2306009/bing-xing-ke-cheng-ii-by-leetcode-soluti-l0mo/
|
答案太精妙了，建议可以反复学习，锻炼脑子
Review
【TED演讲】你不完美，你注定要奋斗，但你值得爱和归属
这篇文章真的超级适合当听力练习，我居然能不看字幕听懂大部分
无论你怎么追求完美，到最终，你都会发现有些事情你无法搞定。
当你预期太高，而有时候没有达成自己的预期的时候，你就会感到巨大的脆弱感。
因此，唯一能做的就是:
接纳脆弱，接纳自己的不完美，注定要继续努力奋斗，但是我们已经尽力而为了，去爱他人去自我实现了，所以不后悔，所以我们值得爱和归属
Tips
Rocksdb dynamic-level-bytes测试简单记录
这篇文章的测试数据很好的说明了展现了 dynamic-level-bytes 能有效降低写放大
不过其中说到数据要到最后一层才能被清理也不太理解–并不是，具体看下文
- 不过通过读文章知道删除更快是因为有叠加bottom compaction辅助删除
- 里面说是第五层数据减少，而不是第六层，是因为数据compaction到第6层，然后在第6层删除，所以第6层有增有减，大体不变，而第五层就compaction下去了，就减少较为明显
LSM架构下所有更新都是以追加一条新记录写入内存表中，delete记录也是写一条新的记录，只不过是type标记为delete。而具体delete的这条记录何时被彻底删除取决于它对应的value记录所在的位置(memtable/L0/L1..)以及flush/compaction的时间，flush将内存中的数据刷到磁盘中并且过程中会做多版本行的处理包含delete与其相应记录的消除(对应记录在memtable的情况)，记录如果被snapshot引用则不能消除，需要等compaction。如果value记录在0/1/2..层，也就是磁盘上了，需要等待compaction，compaction会将未被snapshot引用的多版本行也包括delete记录消除，新写的sst中将不包含这条delete及相应的value记录，旧的sst文件在没有引用之后由回收线程进行释放。
上面引自: Rocksdb删除一个key会经历哪些流程？
Share-wsl2中docker内部网络的ip转发
指南
wsl 默认为内部网络，外部无法访问，通过配置 nat 转发可以直接访问 docker 的内部网络，无需其他复杂的配置。
首先需要知道 wsl2 的内部 ip 地址和 docker 内部的网络地址。例如我的网络是这样的系统 Ubuntu
wsl2 的 ip 地址
inet 192.168.119.0/20 brd 192.168.127.255 scope global eth0
docker 内部的 ip 地址
inet 172.17.0.1/16 brd 172.17.255.255 scope global docker0
进入 Ubuntu
#允许路由转发
sudo iptables -P FORWARD ACCEPT
以管理员身份运行 cmd
#启用路由转发服务 任务管理器 -> 服务 -> 打开服务 -> Routing and Remote Access 或者执行下面的命令
sc start RemoteAccess
#添加路由表
#注意，这里 172.17.0.1 不行，必须的172.17.0.0
route add -P 172.17.0.0 mask 255.255.0.0 192.168.119.0
#ping docker 内部网关就可以 ping 通了
ping 172.17.0.1
然后就可以直接在 windows 下 ping wsl2 中 docker 的内部网络了 方便调试
实操
wsl2 内的 docker
1
2
3
4
5
6
7
8
9
|
root@69033e222523:/# ip a
1: lo: <LOOPBACK,UP,LOWER_UP> mtu 65536 qdisc noqueue state UNKNOWN group default qlen 1000
link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00
inet 127.0.0.1/8 scope host lo
valid_lft forever preferred_lft forever
5: eth0@if6: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc noqueue state UP group default
link/ether 02:42:ac:13:00:03 brd ff:ff:ff:ff:ff:ff link-netnsid 0
inet 172.19.0.3/16 brd 172.19.255.255 scope global eth0
valid_lft forever preferred_lft forever
|
wsl2
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
|
⚡ 06/14|10:25:19 ~ ip a
1: lo: <LOOPBACK,UP,LOWER_UP> mtu 65536 qdisc noqueue state UNKNOWN group default qlen 1000
link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00
inet 127.0.0.1/8 scope host lo
valid_lft forever preferred_lft forever
inet6 ::1/128 scope host
valid_lft forever preferred_lft forever
2: eth0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc mq state UP group default qlen 1000
link/ether 00:15:5d:ed:bb:c1 brd ff:ff:ff:ff:ff:ff
inet 172.18.170.161/20 brd 172.18.175.255 scope global eth0
valid_lft forever preferred_lft forever
inet6 fe80::215:5dff:feed:bbc1/64 scope link
valid_lft forever preferred_lft forever
3: docker0: <NO-CARRIER,BROADCAST,MULTICAST,UP> mtu 1500 qdisc noqueue state DOWN group default
link/ether 02:42:c8:6b:eb:52 brd ff:ff:ff:ff:ff:ff
inet 172.17.0.1/16 brd 172.17.255.255 scope global docker0
valid_lft forever preferred_lft forever
4: br-7358ad5430e2: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc noqueue state UP group default
link/ether 02:42:6f:37:ea:f3 brd ff:ff:ff:ff:ff:ff
inet 172.19.0.1/16 brd 172.19.255.255 scope global br-7358ad5430e2
valid_lft forever preferred_lft forever
inet6 fe80::42:6fff:fe37:eaf3/64 scope link
valid_lft forever preferred_lft forever
6: veth0545bc9@if5: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc noqueue master br-7358ad5430e2 state UP group default
link/ether 6e:6e:aa:ee:87:8f brd ff:ff:ff:ff:ff:ff link-netnsid 0
inet6 fe80::6c6e:aaff:feee:878f/64 scope link
valid_lft forever preferred_lft forever
⚡ 06/14|10:43:06 ~ iptables -P FORWARD ACCEPT
|
管理员 PowerShell
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
|
PS D:\Users\lm> sc start RemoteAccess
PS D:\Users\lm> route add -P 172.19.0.1 mask 255.255.0.0 172.18.170.161
操作完成!
PS D:\Users\lm> ping 172.19.0.3
正在 Ping 172.19.0.3 具有 32 字节的数据:
请求超时。
请求超时。
172.19.0.3 的 Ping 统计信息:
数据包: 已发送 = 2，已接收 = 0，丢失 = 2 (100% 丢失)，
Control-C
PS D:\Users\lm> route add -P 172.19.0.0 mask 255.255.0.0 172.18.170.161
操作完成!
PS D:\Users\lm> ping 172.19.0.3
正在 Ping 172.19.0.3 具有 32 字节的数据:
来自 172.19.0.3 的回复: 字节=32 时间<1ms TTL=63
来自 172.19.0.3 的回复: 字节=32 时间<1ms TTL=63
来自 172.19.0.3 的回复: 字节=32 时间<1ms TTL=63
172.19.0.3 的 Ping 统计信息:
数据包: 已发送 = 3，已接收 = 3，丢失 = 0 (0% 丢失)，
往返行程的估计时间(以毫秒为单位):
最短 = 0ms，最长 = 0ms，平均 = 0ms
Control-C
PS D:\Users\lm>
|