ARST打卡第219周[219/521]

发表于 分类于 阅读次数：
lc834_树中距离之和 GoogleTest Primer 百亿级分布式文件系统之元数据设计 VScode跑gtest

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:

  1. 然后生成一个 task.json
  2. 需要修改添加args -lgtest，以及gtest的依赖库 -lpthread
  3. 然后再次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"
}