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;
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]); 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; for (int first = 0; first < n; ++first) { if (first > 0 && nums[first] == nums[first - 1]) { continue; } int third = n - 1; int target = -nums[first]; for (int second = first + 1; second < n; ++second) { if (second > first + 1 && nums[second] == nums[second - 1]) { continue; } while (second < third && nums[second] + nums[third] > target) { --third; } if (second == third) { break; } if (nums[second] + nums[third] == target) { ans.push_back({nums[first], nums[second], nums[third]}); } } } return ans; } };
|
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,更多的在上层把事情做简单呢?这可能是我们需要长期思考的问题。