思想

今天开图论。Hot 100 里的图论比较基础，不是很全面。大概涉及到了搜索和拓扑排序。如果要学习最小生成树或者最短路径，或许还要再补补课。不管怎样，图论是一个具有很广泛研究对象的学科，和二叉树一样，只是个背景板。所以，见招拆招。

题目

200. Number of Islands

这题给了个二维数组，分别用 0 和 1 表示大海和小岛。连成一片的 1 认为是一个小岛，问小岛的数量是多少。

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
class Solution {
private:
    void dfs(vector<vector<char>>& grid, int i, int j) {
        int m = grid.size(), n = grid[0].size();

        // not island or invalid pos
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') return;

        // run to here, an island asserted
        grid[i][j] = '0';

        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);

        return;
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();

        int sum = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // if island
                if (grid[i][j] == '1') {
                    sum++;
                    dfs(grid, i, j);
                }
            }
        }

        return sum;
    }
};

这是一个比较典型的搜索题目，广搜或者深搜其实都可以，但广搜可以用递归，实现起来相对容易一些。此外，如果修改原始数据来打标记，整体的代码会更加清晰。最后是注意定义辅助函数。

我觉得图论的题目关键是要知道解法，如果忘记了这种题目的对应算法，似乎无力回天？（但其他题目不也是这样么？）嗯，或许我想说的是，图论的题目有点像公式，比如三角函数的和差化积公式，或者圆锥曲线的一些公式，不会就很难推导出来。

Whatever，当我是在废话吧。

207. Course Scheduler

同济排课助手（雾）。这题要求我们做一个排课，课程之间存在依赖关系，问我们能不能在依赖关系满足的情况下修完所有课程。本质是一个拓扑排序。

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
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> adj(numCourses);
        vector<int> indegrees(numCourses, 0);

        for (vector<int>& pre : prerequisites) {
            // for the first pos, add indegree
            indegrees[pre[0]]++;

            // for the second, add fan out
            adj[pre[1]].push_back(pre[0]);
        }

        // now we need a queue for available options
        queue<int> q;

        for (int i = 0; i < indegrees.size(); i++) {
            if (indegrees[i] == 0) {
                q.push(i);
            }
        }

        int taken = 0;

        while (!q.empty()) {
            int opt = q.front(); q.pop();  // opt one course
            taken++;
            // for fan out...
            for (int fanOut : adj[opt]) {
                indegrees[fanOut]--;
                if (indegrees[fanOut] == 0) {
                    // we could choose it now
                    q.push(fanOut);
                }
            }
        }

        return taken == numCourses;
    }
};

既然是拓扑排序，就用标准的解法。对每个结点，记录它的扇出，也就是后续课程，这样当我们学完这门课后，可以为其后继的入度减一，入度马上会讲到。而对于一门课是否能够选择，需要记录入度，也就是还需要修的前置课程数量，如果入度为 0，说明可以学这门课了。

That’s it. 没什么好多说的。

994. Rotting Oranges

腐烂的橘子。我感觉我好像在学校的 OJ 上做过类似的题目。腐烂的橘子每分钟可以传染其周围 4 个格子的健康橘子，使其腐烂。这样后者可以在下一分钟传染其周围的 4 个橘子。以此类推。问要花多长时间腐烂所有的橘子，如果不能，返回 -1。

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
class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        queue<pair<int, int>> q;

        int fresh = 0;

        int m = grid.size(), n = grid[0].size();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // if fresh
                if (grid[i][j] == 1) fresh++;
                else if (grid[i][j] == 2) q.push({i, j});
            }
        }

        int minutes = 0;

        vector<pair<int, int>> dd = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

        while (!q.empty() && fresh > 0) {
            minutes++;
            int row = q.size();

            for (int i = 0; i < row; i++) {  // hierarchy traverse
                auto [x, y] = q.front(); q.pop();

                for (auto &[dx, dy] : dd) {
                    if (x + dx >= 0 && x + dx < m && y + dy >= 0 && y + dy < n && grid[x+dx][y+dy] == 1) {
                        fresh--;
                        grid[x+dx][y+dy] = 2;
                        q.push({x+dx, y+dy});
                    }
                }
            }
        }

        return fresh == 0 ? minutes : -1;
    }
};

我觉得这题算是让我了解了 C++17 的一个结构化绑定结构，类似于 Python 的解包，可以把一个具有很多元素的内容分别赋值给多个单变量。当然，注意是否有 & 的差别。如果在 auto [x, y] 那里加了引用，会导致引用到 pop 后的元素，未定义行为。

整个算法的逻辑相对简单。是一个层次遍历问题。所以很熟悉的，队列 + 每层计数器的结构又出现了。