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，更多的在上层把事情做简单呢？这可能是我们需要长期思考的问题。