lc365_水壶问题 An Interview whit Steve Jobs VSCode Remote ssh跳板机配置 leveldb和rocksdb性能对比如何做
Algorithm
lc365_水壶问题
想了半天，没有想清楚，没啥思路，还是看题解学习一下吧。
示例一解释:
3L倒入5L，再倒入5L，然后3L桶剩下1L水，把5L倒空，然后把1L倒入，再倒入3L得到4L。
dfs
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
|
using PII = pair<int, int>;
class Solution {
public:
bool canMeasureWater(int x, int y, int z) {
stack<PII> stk;
stk.emplace(0, 0);
auto hash_function = [](const PII& o) {return hash<int>()(o.first) ^ hash<int>()(o.second);};
unordered_set<PII, decltype(hash_function)> seen(0, hash_function);
while (!stk.empty()) {
if (seen.count(stk.top())) {
// dfs，可以直接记忆搜索返回。
stk.pop();
continue;
}
seen.emplace(stk.top());
auto [remain_x, remain_y] = stk.top();
stk.pop();
if (remain_x == z || remain_y == z || remain_x + remain_y == z) {
return true;
}
// 把 X 壶灌满。
stk.emplace(x, remain_y);
// 把 Y 壶灌满。
stk.emplace(remain_x, y);
// 把 X 壶倒空。
stk.emplace(0, remain_y);
// 把 Y 壶倒空。
stk.emplace(remain_x, 0);
// 把 X 壶的水灌进 Y 壶，直至灌满或倒空。
stk.emplace(remain_x - min(remain_x, y - remain_y), remain_y + min(remain_x, y - remain_y));
// 把 Y 壶的水灌进 X 壶，直至灌满或倒空。
stk.emplace(remain_x + min(remain_y, x - remain_x), remain_y - min(remain_y, x - remain_x));
}
return false;
}
};
|
贝祖定理
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
bool canMeasureWater(int x, int y, int z) {
if (x + y < z) {
return false;
}
if (x == 0 || y == 0) {
return z == 0 || x + y == z;
}
return z % gcd(x, y) == 0;
}
};
// 链接：https://leetcode.cn/problems/water-and-jug-problem/solutions/161010/shui-hu-wen-ti-by-leetcode-solution/
|
Review
An Interview whit Steve Jobs
You can change your life. You can hack it, improve it and influence others.
When you learn that, you never be the same again.
Tips
VSCode Remote ssh跳板机配置
Share
leveldb和rocksdb性能对比如何做
因为网上的leveldb和rocksdb性能对比都是不够反应各公司自己业务场景需要的，
所以对于leveldb和rocksdb的性能测试还是需要结合实际的机器，实际的磁盘场景进行测试。
特别是rocksdb对SSD还有优化的情况下。
加上leveldb，rocksdb源码中都提供了 db_bench.cc 这个工具帮忙，其实挺方便测试的。
只要设置成相同的参数，然后进行测试就行了。
对于嵌入到了业务的leveldb和rocksdb，也可以将 db_bench.cc 进行定制化之后，
让其完全跑一样的代码进行测试。
参考
rocksdbBench2018的提到和leveldb设置一些相同参数