一：岛屿数量

假期结束了，没有足够时间刷题了，因此往后只采用一种语言解题，方法还是向官方看齐

image-20251009212225200

1. 深度优先搜索

遍历所有元素，然后将该元素的周围为1的元素设为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
class Solution {
public:
    int row = 0;
    int col = 0;
    int numIslands(vector<vector<char>>& grid) {
        int num = 0;
        row = grid.size();
        if (row == 0) return num;
        col = grid[0].size();
        if (col == 0) return num;
        for (int i = 0; i < row; ++i)
            for (int j = 0; j < col; ++j)
            {
                if (grid[i][j] == '1')
                {
                    ++num;
                    recursion(grid, i, j);      // 当前位置
                }
            }
        return num;
    }
    void recursion(vector<vector<char>>& grid, int i, int j)
    {
        grid[i][j] = 0;     // 访问过的点设为0
        if (i - 1 >= 0 && grid[i - 1][j] == '1') recursion(grid, i - 1, j);     // 遍历上下左右四个点
        if (j - 1 >= 0 && grid[i][j - 1] == '1') recursion(grid, i, j - 1);
        if (i + 1 < row && grid[i + 1][j] == '1') recursion(grid, i + 1, j);
        if (j + 1 < col && grid[i][j + 1] == '1') recursion(grid, i, j + 1);
    }
};

image-20251009212430386

2. 广度优先搜索

广度使用队列来维护节点，优先处理队列顶端的前后左右四个元素

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
class Solution {
public:
    int row = 0;
    int col = 0;
    int numIslands(vector<vector<char>>& grid) {
        int num = 0;
        row = grid.size();
        if (row == 0) return num;
        col = grid[0].size();
        if (col == 0) return num;
        queue<pair<int, int>> queueNum;
        for (int i = 0; i < row; ++i)
            for (int j = 0; j < col; ++j)
                if (grid[i][j] == '1')
                {
                    ++num;
                    grid[i][j] = '0';
                    queueNum.push(pair(i, j));
                    while (!queueNum.empty())
                    {
                        auto cur = queueNum.front();
                        queueNum.pop();
                        int i = cur.first;
                        int j = cur.second;
                        if (i - 1 >= 0 && grid[i - 1][j] == '1')
                        {
                            grid[i - 1][j] = '0';
                            queueNum.push(pair(i - 1, j));
                        }
                        if (j - 1 >= 0 && grid[i][j - 1] == '1')
                        {
                            grid[i][j - 1] = '0';
                            queueNum.push(pair(i, j - 1));
                        }
                        if (i + 1 < row && grid[i + 1][j] == '1')
                        {
                            grid[i + 1][j] = '0';
                            queueNum.push(pair(i + 1, j));
                        }
                        if (j + 1 < col && grid[i][j + 1] == '1')
                        {
                            grid[i][j + 1] = '0';
                            queueNum.push(pair(i, j + 1));
                        }
                    }
                }
        return num;
    }
};

image-20251009212440708

3. 并查集

这个数据结构就是为了处理这种“查询两个元素是否属于同一集合”和“合并两个元素所在的集合”的操作而生的。parent.push_back(i * n + j)将每个元素的父节点保存

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
class UnionFind
{
public:
    vector<int> parent;     // 记录父节点
    vector<int> depth;      // 记录节点深度
    int count = 0;          // 记录独立森林数
    UnionFind(vector<vector<char>>& grid)       // 初始化森林和父节点列表
    {
        int row = grid.size();
        int col = grid[0].size();
        for (int i = 0; i < row; ++i)
            for (int j = 0; j < col; ++j)
            {
                if (grid[i][j] == '1')
                {
                    parent.emplace_back(i * col + j);       // 父节点为自己
                    ++count;            // 森林数量+1
                }
                else parent.emplace_back(-1);        // 无父节点
                depth.emplace_back(0);           // 深度为1
            }
    }
    int Find(int i)          // 查找父节点
    {
        if (parent[i] != i) parent[i] = Find(parent[i]);        // 父节点不是本身，向上查找
        return parent[i];
    }
    void Unite(int x, int y)            // 联合
    {
        x = Find(x);        
        y = Find(y);
        if (x != y)     // 两者父节点不相同，相同节点不必处理
        {
            if (depth[x] < depth[y]) parent[x] = y;           // 深度浅接到深度深的节点，方便查找
            else if (depth[x] > depth[y]) parent[y] = x;
            else parent[x] = y;
            --count;
            x > y ? ++depth[y] : ++depth[x];
        }
    }
};

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int nr = grid.size();
        if (!nr) return 0;
        int nc = grid[0].size();
        UnionFind uf(grid);
        for (int r = 0; r < nr; ++r) 
            for (int c = 0; c < nc; ++c) 
                if (grid[r][c] == '1') {
                    grid[r][c] = '0';           // 不需要，只是为了减少重复访问的次数
                    if (r - 1 >= 0 && grid[r-1][c] == '1') uf.Unite(r * nc + c, (r-1) * nc + c);
                    if (r + 1 < nr && grid[r+1][c] == '1') uf.Unite(r * nc + c, (r+1) * nc + c);
                    if (c - 1 >= 0 && grid[r][c-1] == '1') uf.Unite(r * nc + c, r * nc + c - 1);
                    if (c + 1 < nc && grid[r][c+1] == '1') uf.Unite(r * nc + c, r * nc + c + 1);
                }
        return uf.count;
    }
};

image-20251009212451985

二：腐烂的橘子

image-20251009234004357

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int time = 0;
        int numFre = 0;
        int row = grid.size(); 
        int col = grid[0].size();
        queue<pair<int, int>> Q;
        if (row == 0 || col == 0 ) return 0;
        for (int i = 0; i < row; ++i)
            for (int j = 0; j < col; ++j)
            {
                if (grid[i][j] == 2)
                    Q.push(pair{i ,j});
                if (grid[i][j] == 1)
                    ++numFre;
            }
        if (numFre == 0) return 0;
        while (!Q.empty())
        {
            int size = Q.size();
            ++time;
            for (int i = 0; i < size; ++i)
            {
                int x = Q.front().first;
                int y = Q.front().second;
                Q.pop();
                if (x - 1 >= 0 && grid[x - 1][y] == 1)
                {
                    grid[x - 1][y] = 2;
                    Q.push(pair{x - 1, y});
                    --numFre;
                }
                if (x + 1 < row && grid[x + 1][y] == 1)
                {
                    grid[x + 1][y] = 2;
                    Q.push(pair{x + 1, y});
                    --numFre;
                }
                if (y - 1 >= 0 && grid[x][y - 1] == 1)
                {
                    grid[x][y - 1] = 2;
                    Q.push(pair{x, y - 1});
                    --numFre;
                }
                if (y + 1 < col && grid[x][y + 1] == 1)
                {
                    grid[x][y + 1] = 2;
                    Q.push(pair{x, y + 1});
                    --numFre;
                }
            }
        }
        if (numFre != 0) return -1;
        return time - 1;
    }
};

image-20251009234041465

三：课程表

image-20251010153007494

1. 深度优先搜索

实际上是判断该结构是否为有向无环图，使用0、1、2来表示节点的状态，再次遇到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
class Solution {
public:
    vector<vector<int>> edge;
    vector<int> visit;
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        edge.resize(numCourses);
        visit.resize(numCourses); 
        for (auto& it : prerequisites)
            edge[it[1]].emplace_back(it[0]);            // 构造节点的有向边
        for (int i = 0; i < numCourses; ++i)
            if (visit[i] == 0)              // 未访问的节点，每一个都判断防止森林的情况
                {
                    if (!recursion(i)) return false;
                }
        return true;
        
    }
    bool recursion(int i)
    {
        visit[i] = 1;               // 表示正在访问，还未完成
        for (auto sub : edge[i])        // 寻找子节点
        {
            if (visit[sub] == 0)
                {
                    if (!recursion(sub)) return false;
                }         // 表明子节点存在环，直接返回无需设为已完成
            else if(visit[sub] == 1)      // 访问到正在访问的节点，表明出现环
                return false;
        }
        visit[i] = 2;               // 完成访问
        return true;
    }
};

image-20251010153101579

2. 广度优先搜索

用队列维护没有入度的节点，然后对每个子节点的入度减一，然后添加子节点到队列，记录的子节点数量和题目要求的值相同表明可以完成课程

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
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> edge;
        vector<int> inEdge;
        edge.resize(numCourses);
        inEdge.resize(numCourses); 
        for (auto& it : prerequisites)
        {
            edge[it[1]].emplace_back(it[0]);            // 构造节点的有向边
            ++inEdge[it[0]];                    // 入边的数量
        }
        queue<int> q;
        int allNum = 0;
        for (int i = 0; i < numCourses; ++i)        // 没有入度的节点
            if (inEdge[i] == 0) q.push(i);
        while (!q.empty())
        {
            ++allNum;
            int cur = q.front();
            q.pop();
            for (auto& sub : edge[cur])
            {
                --inEdge[sub];
                if (inEdge[sub] == 0) q.push(sub);
            }
        }
        return allNum == numCourses;
    }
};

image-20251010153049678