ARST打卡第218周[218/521]

Algorithm

lc15_三数之和

思路:
这个三个数字不能相同,很显然可以用双指针,然后组合成0,显然可以排序后查找。
因此思路就是先排序,然后再双指针+二分查找。时间复杂度就是O(nlogn)

写了一下,发现不能遍历完,所以还是去看了一下数据范围,发现可以到O(n*nlogn),所以外层还是可以双重遍历。

发现使用 lower_bound 来获取二分查找,就无法获取下标的灵活性了,所以还是使用自定义函数二分比较好

发现没有好好看题目,导致一开始重复元组没有判断

写出来还TLE了…很奇怪,看下答案…

超出时间限制 312 / 312 个通过的测试用例

看了题解,发现是在第一层循环后开始双指针…一开始明明有点想到了,但是没有坚持想正确…被二分查找带偏了
而且答案更巧妙的地方在于重复的判断。学习吧。

丢人啊,2020.6.12 三年前也是看了题解的…真丢人…加油努力吧…多多学习吧。

自己的代码

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
class Solution {
public:
struct VectorHash {
size_t operator()(const std::vector<int>& v) const {
std::hash<int> hasher;
size_t seed = 0;
for (int i : v) {
seed ^= hasher(i) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
return seed;
}
};
using MySet = std::unordered_set<std::vector<int>, VectorHash>;

int binary_search(const vector<int>& arr, int start, int end, int val) {
int ret = -1; // 未搜索到数据返回-1下标

int mid;
while (start <= end) {
mid = start + (end - start) / 2;
if (arr[mid] < val)
start = mid + 1;
else if (arr[mid] > val)
end = mid - 1;
else {
ret = mid;
break;
}
}

return ret;
}

vector<vector<int>> threeSum(vector<int>& nums) {
int sz = nums.size();
vector<vector<int>> ans;
int find = 0;
sort(nums.begin(), nums.end());
int lt = 0;
int rt = sz - 1;
MySet ans_set;
for (; nums[lt] <= 0 && lt < sz - 2; lt++) {
rt = sz - 1;
// 中间间隔一个
for (; nums[rt] >= 0 && lt < rt - 1; rt--) {
find = 0 - (nums[lt] + nums[rt]);
// 不能把 lt, rt 算入(否则实例一中漏了[-1,-1,2])
// int find_iter = binary_search(nums, lt, rt, find);
int find_iter = binary_search(nums, lt + 1, rt - 1, find);
if (find_iter != -1 && find_iter != lt && find_iter != rt) {
vector<int> tmp{nums[lt], find, nums[rt]};
ans_set.insert(tmp);
}
}
}
for (auto x : ans_set) {
ans.emplace_back(x);
}
return ans;
}
};

题解

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
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
// 枚举 a
for (int first = 0; first < n; ++first) {
// 需要和上一次枚举的数不相同
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
// c 对应的指针初始指向数组的最右端
int third = n - 1;
int target = -nums[first];
// 枚举 b
for (int second = first + 1; second < n; ++second) {
// 需要和上一次枚举的数不相同
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
// 需要保证 b 的指针在 c 的指针的左侧
while (second < third && nums[second] + nums[third] > target) {
--third;
}
// 如果指针重合,随着 b 后续的增加
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了,可以退出循环
if (second == third) {
break;
}
if (nums[second] + nums[third] == target) {
ans.push_back({nums[first], nums[second], nums[third]});
}
}
}
return ans;
}
};
// 链接:https://leetcode.cn/problems/3sum/solutions/284681/san-shu-zhi-he-by-leetcode-solution/

Review

【TED演讲】才华可以人人都有,但机会不是

视频主人公也知道自己是幸运的人。

不是每个人都能得到命运的馈赠,所以不要在失败后过度失望,为而不争,自我实现不成的话,就斯多葛主义获取内心平静也挺好

Tips

深入探讨LSM Compaction机制

Share

思考大佬对于remote-compaction的思考。Rocksdb还是的存算分离一起做。

觉得Remote-Compaction还是需要和业务场景相结合,尽量结合最新的存算分离架构,把IO也offload出去。

如何评价 ToplingDB 的内嵌 Web? - 郭宽的回答 - 知乎
https://www.zhihu.com/question/501019174/answer/2250301468

关于远程 Compaction,我们和 中科大合作发表了 FaaS Compaction的论文,方案有差异但目标是接近的,都是把本地的计算 offload 到远程。

客观来说这部分的收益是很明显的,在“理想情况下”是可以把平均吞吐提升一倍的,不过我们最终没有启用,大部分原因是非技术因素,但面临的业务方挑战也确实存在:

  • 如何均衡远程 Compaction 和本地服务争抢 IO 资源?
  • 在盘的使用量较高时,如何避免盘本身出现延迟抖动?
  • 很多 RocksDB 的用户会使用用户态文件系统优化性能(如BlueFS的优化效果显著),远程 Compaction 是否会破坏这些优化?
  • 新型 Memtable 和新型 SSTable,虽然可以显著加速数据写入系统的速度,但作为 SSD 为主要存储设备的系统,最终的瓶颈是否还会落在磁盘带宽上呢?

从技术角度而言,我觉得在某些场景下打败 RocksDB,是没有问题的,但 RocksDB 自身的强大生命力并不是这些,而是其在 Facebook 内部已经达成了的研发默契,甚至说我们使用 RocksDB 构建存储系统的时候,是否也应该学习 Facebook,更多的在上层把事情做简单呢?这可能是我们需要长期思考的问题。