lc732_我的日程安排表 III 宇宙消失？以及它对生命的意义！【TED演讲】 JLP APY预测原理及利率交易套利模式研究 samba nt acl设置
Algorithm
lc732_我的日程安排表 III
思路:
逐步增加时间段，然后输出当前时间段的最大重叠数。只会加400个时间段。
而时间端确实 [0, 1e9] 整数，题目理解起来很简单，但是标的hard，估计是考数据结构，所以感觉需要线段树…
结果看题解，发现 hash+差分数组就可以了，泪目。
但是差分数组需要 O(n^2) 时间复杂度，线段树只需要 O(nlogn) 时间复杂度。
差分数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class MyCalendarThree {
public:
MyCalendarThree() {
}
int book(int start, int end) {
int ans = 0;
int maxBook = 0;
cnt[start]++;
cnt[end]--;
for (auto &[_, freq] : cnt) {
// 差分数组，累加获取每个区间的重叠数，然后更新最大重叠数。
maxBook += freq;
ans = max(maxBook, ans);
}
return ans;
}
private:
map<int, int> cnt;
};
|
线段树
cpp版本
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
|
class MyCalendarThree {
public:
unordered_map<int, pair<int, int>> tree;
MyCalendarThree() {
}
// 线段树更新函数
// start, end: 要更新的区间范围
// l, r: 当前节点表示的区间范围
// idx: 当前节点的编号
void update(int start, int end, int l, int r, int idx) {
// 区间无交集,直接返回
if (r < start || end < l) {
return;
}
// 当前区间被完全包含在要更新的区间内
if (start <= l && r <= end) {
// first和second需要分开存储:
// 1. first表示以当前节点为根的子树中的最大重叠数
// 需要考虑子节点的重叠情况
// 2. second表示当前节点本身的懒标记值
// 仅反映当前节点被更新的次数
// 举例说明重叠计算:
// 1. 假设区间[1,5]和[3,7]重叠,重叠部分是[3,5]
// 2. 对于节点idx表示的区间:
// - tree[idx].second 记录当前区间被预订的次数(懒标记)
// - tree[2*idx].first 记录左子树的最大重叠数
// - tree[2*idx+1].first 记录右子树的最大重叠数
// 3. 当前节点的最大重叠数计算:
// - 当前区间的预订次数(tree[idx].second)需要加到子区间上
// - 取左右子树重叠数的较大值,再加上当前区间的预订次数
// - 体现了区间重叠的累加效果
tree[idx].first++; // first存储当前节点的最大重叠数
tree[idx].second++; // second存储当前节点的懒标记(延迟更新标记)
} else {
int mid = (l + r) >> 1;
// 递归更新左右子树
update(start, end, l, mid, 2 * idx);
update(start, end, mid + 1, r, 2 * idx + 1);
// 更新当前节点的最大重叠数:
// 当前节点的懒标记 + max(左子树最大重叠数,右子树最大重叠数)
tree[idx].first = tree[idx].second + max(tree[2 * idx].first, tree[2 * idx + 1].first);
}
}
int book(int start, int end) {
update(start, end - 1, 0, 1e9, 1);
return tree[1].first;
}
};
|
rust版本
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
|
#[derive(Clone)]
struct Node {
first: i32, // 最大重叠数
second: i32, // 懒标记
}
struct MyCalendarThree {
tree: std::collections::HashMap<usize, Node>,
}
impl MyCalendarThree {
fn new() -> Self {
Self {
tree: std::collections::HashMap::new()
}
}
fn update(&mut self, start: i32, end: i32, l: i32, r: i32, idx: usize) {
// 区间无交集,直接返回
if r < start || end < l {
return;
}
// 当前区间被完全包含
if start <= l && r <= end {
let node = self.tree.entry(idx).or_insert(Node{first:0, second:0});
node.first += 1;
node.second += 1;
} else {
let mid = (l + r) >> 1;
// 递归更新左右子树
self.update(start, end, l, mid, 2 * idx);
self.update(start, end, mid + 1, r, 2 * idx + 1);
// 获取左右子节点的值
let left = self.tree.get(&(2 * idx)).map_or(0, |node| node.first);
let right = self.tree.get(&(2 * idx + 1)).map_or(0, |node| node.first);
let current = self.tree.entry(idx).or_insert(Node{first:0, second:0});
// 更新当前节点的最大重叠数
current.first = current.second + std::cmp::max(left, right);
}
}
fn book(&mut self, start_time: i32, end_time: i32) -> i32 {
self.update(start_time, end_time - 1, 0, 1000000000, 1);
self.tree.get(&1).map_or(0, |node| node.first)
}
}
|
Review
宇宙消失？以及它对生命的意义！【TED演讲】
作为一个渺小的人类，能够去思考宇宙的起源，和可能的消失，本身就是一件很了不起的事情。
而且知道一切都终将消失之后，更让人珍惜当下，尽量去享受自己喜爱的生活。
Tips
JLP APY预测原理及利率交易套利模式研究
Share
samba nt acl设置
根据samba的 Writing a Samba VFS Module 和 NT ACL 相关内容可知，
只要实现了 setxattr 和 getxattr 函数，就可以利用 acl_xattr 模块来支持 NT ACL 了。
并且官方文档示例也写了 vfs objects = acl_xattr my_vfs_obj .
NOTICE: 注意避坑
别把 vfs objects = acl_xattr 写在 [global] 里面，
而[共享名] 里面只写 vfs objects = my_vfs_obj ，这样会导致 acl_xattr 模块被覆盖掉。
因为这里 samba 配置的机制是（假定每个配置都是一个key多个value）:
- 组合
[global] 和 [共享名] 的 key 配置
- 如果存在相同key，则
[共享名] 的 key 配置会覆盖 [global] 的配置，不会相同key组合后面的data