LeetCode 刷题

2477 达到首都的最少油耗：给你一棵 n 个节点的树（一个无向、连通、无环图），每个节点表示一个城市，编号从 0 到 n - 1 ，且恰好有 n - 1 条路，0 是首都。给你一个二维整数数组 roads ，其中 roads[i] = [a_i, b_i] ，表示城市 a_i 和 b_i 之间有一条双向路。

• 每个城市有一辆车（均有 seats 个座位），且每个城市需要一名代表去首都参加会议。
• 代表可以选择乘坐自己所在城市的车辆，也可以选择乘坐其他城市的车辆。
• 相邻城市之间的车辆油耗是一升。

你需要计算所有代表到达首都所需的最少汽油量。

1
2
3
4
5
6
7
8
9
10
11

输入：roads = [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]], seats = 2
输出：7
解释：
- 代表 2 到达城市 3 ，消耗 1 升汽油。
- 代表 2 和代表 3 一起到达城市 1 ，消耗 1 升汽油。
- 代表 2 和代表 3 一起到达首都，消耗 1 升汽油。
- 代表 1 直接到达首都，消耗 1 升汽油。
- 代表 5 直接到达首都，消耗 1 升汽油。
- 代表 6 到达城市 4 ，消耗 1 升汽油。
- 代表 4 和代表 6 一起到达首都，消耗 1 升汽油。
最少消耗 7 升汽油。

形象化数组

将数组转换为树的形状：

1
2
3
4
5
6
7

       0
     / | \
    1  4  5
   /   |
  3    6
 /
2

问题转换与解题思路

题目等价于给出了一棵以节点 0 为根节点的多叉树，初始时树上的每一个节点都有一个人和一辆车，现在所有人都需要通过「车子」向节点 0 移动。

我们可以 贪心地 从每个叶子节点派车出发，只要车上还有空座位，就把该节点的人拉上车，并向根节点移动。要是车上没有座位了，那么就增派一辆车，也向根节点移动。这样就能保证所有人都到达首都，且油耗最少。

对于上面的示例路径 2->3->1->0，按上面的思路，有：

• 三个人需要去首都，在节点 2 派出一辆车，在节点 1 增派了一辆车，一共需要两辆车，消耗 4 升汽油。

通过观察分析，我们可以发现：

• x 个人通过某一段公路到达「该段路的终点」，该段路 需要消耗的油量（需要的车辆数）为「人数 / 座位数」向上取整。如：
  • 节点 2 一起移动到节点 3，需要的汽油总量为 ceil(1, 2) = 1；
  • 节点 2,3 一起移动到节点 1，需要的汽油总量为 ceil(2, 2) = 1；
  • 节点 2,3,1 一起移动到节点 0，需要的汽油总量为 ceil(3, 2) = 2。
• 一条子树总共需要的油量为每一段路需要的油量（需要的车辆数）之和。

那么，我们可以通过从根节点 0 往下进行 深度优先搜索 ，根据 路上累计的人数 计算统计每一条边上消耗的汽油（需要的车辆数），把所有边上消耗的汽油相加即为最终答案。

数据转换与存储

题目使用了一个二维数组存储图数据，而我们需要的是每一个节点的邻居节点。所以首先需要将二维数组中的数据转换到邻接矩阵中，存储每个节点的邻居节点，而邻居节点的数量是不固定的。

对于 Python 语言，我们可以使用二维列表完成每个邻居节点的存储：

1
2
3
4
5
6

n = roadsSize + 1
graph = [[] for _ in range(n)]
for edge in roads:
    x, y = edge[0], edge[1]
    graph[x].append(y)
    graph[y].append(x)

对于 C 语言，我们需要定义一个二维结构体列表，列表中的每一个位置是一个链表，存储它的所有邻居节点（具体看后面的代码实现）。

一个节点的所有邻居节点就是它在树中的父节点和子节点的集合，有些节点可能既有父节点又有子节点，而有些节点只有父节点。

贪心 + 深度优先搜索

通过从根节点 0 往下进行 深度优先搜索 ，根据 路上累计的人数 计算统计每一条边上消耗的汽油（需要的车辆数），把所有边上消耗的汽油相加即为最终答案。

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

// 单链表结构
typedef struct _linked {
    int val;
    struct _linked *next;
} ListNode;

// 创建一个链表节点
ListNode *createListNode(int val) {
    ListNode *node = (ListNode *)malloc(sizeof(ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

// 释放链表空间
void freeList(ListNode *list) {
    while (list) {
        ListNode *cur = list;
        list = list->next;
        free(cur);
    }
}

// 打印链表内容
void printList(ListNode *list) {
    while (list) {
        printf("%d ", list->val);
        list = list->next;
    }
    printf("\n");
}

// 向上取整
int myCeil(int a, int b) {
    return (a + b - 1) / b;
}

long long minimumFuelCost(int** roads, int roadsSize, int* roadsColSize, int seats) {
    int n = roadsSize + 1; // n 个节点有 n-1 条路，n-1=roadsSize

    // 定义一个二维列表，存储每个节点的邻居节点（在树中看，邻居就是它的子节点和父节点）
    ListNode **graph = (ListNode **)malloc(n * sizeof(ListNode *));
    memset(graph, NULL, n * sizeof(ListNode *));

    for (int i = 0; i < roadsSize; i++) {
        int x = roads[i][0], y = roads[i][1];

        // y 的邻居节点是 x，将 x 追加到节点 y 对应的列表中
        ListNode *nodeX = createListNode(x);
        nodeX->next = graph[y];
        graph[y] = nodeX;

        ListNode *nodeY = createListNode(y);
        nodeY->next = graph[x];
        graph[x] = nodeY;
    }

    // 到这里，每个节点的邻居节点就有了（邻居在列表中的顺序无关紧要）
    // for (int i = 0; i < n; i++) {
    //     printf("node %d can be reached: ", i);
    //     printList(graph[i]);
    // }

    long long res = 0;
    dfs(0, -1, seats, &res, graph); // 从多叉树的根节点出发，向下遍历每棵子树

    for (int i = 0; i < n; i++) {
        freeList(graph[i]);
    }
    free(graph);

    return res;
}

int dfs(int cur, int father, int seats, long long *res, const ListNode **graph) {
    int peopleSum = 1;

    // 遍历当前节点的邻居节点（包含父节点和子节点）
    for (ListNode *node = graph[cur]; node; node = node->next) {
        int val = node->val;
        // 递归地遍历当前节点的子节点，不递归当前节点的父节点
        if (val != father) {
            // 累计以当前节点为根的子节点人数
            peopleSum += dfs(val, cur, seats, res, graph);
        }
    }

    if (cur != 0) { // 不是根节点时，计算耗油
        *res += myCeil(peopleSum, seats);
    }

    return peopleSum;
}

代码分析

向上取整

a 与 b 相除的向上取整公式：(a + b - 1) / b。因为 a/b 的余数最大为 b-1，我们多加一个 b-1 会使得：

• 当原来余数为 0 时，新公式计算出来的商的部分还是原来的值；
• 当原来余数不为 0 时，多加的那部分 b-1 结合原来不为 0 的余数，会使得商的值加一。

这样，便达到一个向上取整的效果。

邻居节点

每个节点的邻居节点打印（以上面的示例为例）：

1
2
3
4
5
6
7

node 0 can be reached: 5 4 1 
node 1 can be reached: 0 3 
node 2 can be reached: 3 
node 3 can be reached: 2 1 
node 4 can be reached: 6 0 
node 5 can be reached: 0 
node 6 can be reached: 4 

DFS 理解

在小破站上看到一个评论：

处理递归，核心就是千万不要想子问题的过程，你的脑子才能处理几层？马上就绕迷糊了。重要的是，要想子问题的结果，思路就清晰了。

是的，只要代码的边界条件和非边界条件的逻辑写对了，其它的事情交给数学归纳法就好了。也就是说，写对了这两个逻辑，你的代码自动就是正确的了，没必要想递归是怎么一层一层走的。

基于上面的评论，这道题中的 DFS 需要做的是（个人理解）：

1. 从多叉树的根节点出发，向下遍历每棵子树（也就是递归地遍历当前节点的子节点，不递归当前节点的父节点）；
2. 也就是说，当遍历的节点的邻居节点是父节点时，不再递归，会得到一个返回值 1；
3. 当遍历的节点的邻居节点是子节点时，递归地遍历它的子节点，累计子树的大小（累计返回值）；
4. 计算完子树大小后，计算到达该子树的根节点时的油耗，累加到最终结果中。

例如，对于上面的序号 2，当遍历节点 2 时，递归函数是 dfs(2, 3, ...)，节点 2 中存储的节点是 3，也就是它的父节点，且它没有其它节点了。所以，for 循环结束，不再递归，累计油耗到答案，并返回人数 1。这个返回值后面要累计给 dfs(3, 1, ...) 的返回值 1，即当前的 peopleSum 值就是 dfs(2, 3, ...) + dfs(3, 1, ...) = 2，从节点 3 到它的父节点 1 需要油耗 ceil(2, 2) = 1。

为什么不需要计算根节点 0 的耗油？
根节点 0 不需要累计油耗到答案，是因为累计的是每个节点到其父节点的公路上的油耗，根节点没有它的父节点，即没有公路，也就不需要油耗了。