Algorithm
lc834_树中距离之和
题意很清晰，就是要把每段距离计算相加，这里肯定不能O(n^2),应该是要树状dp，但是好久没写过树状dp了，先学习一波题解
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
|
class Solution {
public:
vector<int> ans, sz, dp;
vector<vector<int>> graph;
// 以u为根，f为父节点的树状dp，获取dp[u]所有子节点到根的和
void dfs(int u, int f) {
// sz[u]=1 是一开始自身节点数为1
sz[u] = 1;
dp[u] = 0;
for (auto& v: graph[u]) {
if (v == f) {
continue;
}
dfs(v, u);
dp[u] += dp[v] + sz[v];
sz[u] += sz[v];
}
}
void dfs2(int u, int f) {
// ans[u] 就等于 u 为根时的dp值
ans[u] = dp[u];
for (auto& v: graph[u]) {
if (v == f) {
continue;
}
// 伪装成v为根，去获取ans[v]=dp[v]后恢复
int pu = dp[u], pv = dp[v];
int su = sz[u], sv = sz[v];
dp[u] -= dp[v] + sz[v];
sz[u] -= sz[v];
dp[v] += dp[u] + sz[u];
sz[v] += sz[u];
dfs2(v, u);
dp[u] = pu, dp[v] = pv;
sz[u] = su, sz[v] = sv;
}
}
vector<int> sumOfDistancesInTree(int n, vector<vector<int>>& edges) {
ans.resize(n, 0);
sz.resize(n, 0);
dp.resize(n, 0);
graph.resize(n, {});
for (auto& edge: edges) {
int u = edge[0], v = edge[1];
graph[u].emplace_back(v);
graph[v].emplace_back(u);
}
dfs(0, -1);
dfs2(0, -1);
return ans;
}
};
|
Review
GoogleTest Primer
很多的开源工程软件基本上跑的都是gtest，复习一下基本用法，还是要看官方文档的。
Tips
百亿级分布式文件系统之元数据设计
这篇文章对元数据集群MDS三大方面的设计思想进行了讨论：元数据管理方案、元数据切分方案和多副本机制。值得看一看。
Share-VScode跑gtest
可能得前置步骤
VScode安装cpp:
安装 C/C++ 扩展：打开 VSCode 扩展市场，搜索「C/C++」并安装扩展。
安装编译gtest
安装 Google Test：
- 如果你使用的是 Windows，可以下载并安装 pre-built 版本；
- 如果你使用的是 Linux 或 macOS，可以使用命令行安装：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
# ubuntu/Debian安装源码
sudo apt-get install libgtest-dev
# 编译安装
# 学习brpc过程中发现有一条命令的版本
sudo apt-get install -y cmake libgtest-dev && cd /usr/src/gtest && sudo cmake . && sudo make && sudo mv lib/libgtest* /usr/lib/ && cd -
# cd /usr/src/gtest
# sudo mkdir build
# cd build
# sudo cmake ..
# sudo make
# # 复制库目录
# sudo cp libgtest*.a /usr/local/lib
# mac
# brew install gtest
|
测试使用
创建测试代码：新建一个 C++ 文件，并写入测试代码，例如：
1
2
3
4
5
6
7
8
9
10
|
#include <gtest/gtest.h>
TEST(TestCaseName, TestName) {
EXPECT_EQ(1, 1);
}
int main(int argc, char** argv) {
::testing::InitGoogleTest(&argc, argv);
return RUN_ALL_TESTS();
}
|
直接命令使用
1
2
3
4
5
6
7
8
9
10
11
12
|
⚡ 07/12|11:30:32 test /usr/bin/g++ -fdiagnostics-color=always -g /root/code/test/tmp.cpp -o /root/code/test/tmp -lgtest -lpthread
⚡ 07/12|11:34:42 test ./tmp
[==========] Running 1 test from 1 test case.
[----------] Global test environment set-up.
[----------] 1 test from TestCaseName
[ RUN ] TestCaseName.TestName
[ OK ] TestCaseName.TestName (0 ms)
[----------] 1 test from TestCaseName (0 ms total)
[----------] Global test environment tear-down
[==========] 1 test from 1 test case ran. (0 ms total)
[ PASSED ] 1 test.
|
通过VScode使用
在 VSCode 中运行单元测试：打开命令面板（Ctrl+Shift+P），输入Debug: Start Without Debugging:
- 然后生成一个 task.json
- 需要修改添加args
-lgtest，以及gtest的依赖库 -lpthread
- 然后再次
Debug: Start Without Debugging才能运行成功
json最终形态
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
|
{
"tasks": [
{
"type": "cppbuild",
"label": "C/C++: g++ 生成活动文件",
"command": "/usr/bin/g++",
"args": [
"-fdiagnostics-color=always",
"-g",
"${file}",
"-o",
"${fileDirname}/${fileBasenameNoExtension}",
"-lgtest",
"-lpthread"
],
"options": {
"cwd": "${fileDirname}"
},
"problemMatcher": [
"$gcc"
],
"group": {
"kind": "build",
"isDefault": true
},
"detail": "调试器生成的任务。"
}
],
"version": "2.0.0"
}
|