图论 --面试经典150题

tobegold574 Lv5
  2024-12-30 14:48:59 2024-12-30 14:48:59 Created   2024-12-31 11:42:05 2024-12-31 11:42:05 Updated    

被围绕的区域(medium)

做题过程

大概清楚肯定还是DFS和BFS都可以，但问题是该怎么组织代码结构，完全没有思路。而且抄都能抄错好几次。

算法概述

原题

本题要求为给出二维矩阵，需要通过原地操作将其中被’X’完全包围的’O’转换为’X’（在边界不算）。DFS看上去好写一些。

  • 时间复杂度为O(n*m)
  • 空间复杂度为O(n*m)

JAVA

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 {
    int n, m;

    public void solve(char[][] board) {
        n = board.length;
        m = board[0].length;
        // 再加一个m的检查就会编程2ms了，非常神奇，不过也确实不用检查m
        if (n == 0)
            return;
        
        for (int i = 0; i < n; i++) {
            // 竖着的两个边界 
            dfs(board, i, 0);
            dfs(board, i, m - 1);
        }

        for (int i = 1; i < m - 1; ++i) {
            // 横着的两个边界
            dfs(board, 0, i);
            dfs(board, n - 1, i);
        }

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                // A代表和边界的O连着
                if (board[i][j] == 'A') {
                    board[i][j] = 'O';
                    // 原本的O代表和边界的O是隔绝（即被X所包围）
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }

    // 找和边界上的O连着的其他O
    public void dfs(char[][] board, int x, int y) {
        // 是X或者是A或者越界就停止了
        if (x < 0 || x >= n || y < 0 || y >= m || board[x][y] != 'O')
            return;
        // 是O就先设置为A
        board[x][y] = 'A';
        // 上下左右
        dfs(board, x + 1, y);
        dfs(board, x - 1, y);
        dfs(board, x, y + 1);
        dfs(board, x, y - 1);
    }
}

总结

总而言之，思路如下：

  1. 检查四个边界的O
  2. 对边界上的O进行上下左右的移动递归，碰到标记过的或者X即停止（也就是没有连接的O了）
  3. 再次遍历整个矩阵，将标记转化回O，非标记O转化为X（捕获）

比较妙的地方是高效完成了边界连通O的筛选工作，通过 递归 和 记录标记 ，但这里并没有用标记数组，而是 直接原地标记 。

克隆图(medium)

做题过程

我想的就是BFS，但是感觉不太好维护，因为中间设计大量构建新节点的操作，但是新节点构建之前，如何处理它们作为neighbour的节点是一个问题。

算法概述

原题

本题要求为克隆一张无相连通图。DFS和BFS皆可。

  • 时间复杂度为O(n)
  • 空间复杂度为O(n)

JAVA

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
// DFS
class Solution {
    private HashMap <Node, Node> visited = new HashMap <> ();
    public Node cloneGraph(Node node) {
        if (node == null) {
            return node;
        }

        // 如果该节点已经被访问过了，则直接从哈希表中取出对应的克隆节点返回
        if (visited.containsKey(node)) {
            return visited.get(node);
        }

        // 克隆节点，最关键的neighbors在克隆时不作为参数，而是之后在递归中完成
        Node cloneNode = new Node(node.val, new ArrayList());
        // 哈希表存储
        visited.put(node, cloneNode);

        // 遍历该节点的邻居并更新克隆节点的邻居列表
        for (Node neighbor: node.neighbors) {
            cloneNode.neighbors.add(cloneGraph(neighbor));
        }
        return cloneNode;
    }
}

// BFS
class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) {
            return node;
        }

        HashMap<Node, Node> visited = new HashMap();

        // 将题目给定的节点添加到队列
        LinkedList<Node> queue = new LinkedList<Node> ();
        queue.add(node);
        // 克隆第一个节点并存储到哈希表中
        visited.put(node, new Node(node.val, new ArrayList()));

        // 广度优先搜索
        while (!queue.isEmpty()) {
            // 取出队列的头节点
            Node n = queue.remove();
            // 遍历该节点的邻居
            for (Node neighbor: n.neighbors) {
                // 要注意这个先决条件
                if (!visited.containsKey(neighbor)) {
                    // 如果没有被访问过，就克隆并存储在哈希表中
                    visited.put(neighbor, new Node(neighbor.val, new ArrayList()));
                    // 将邻居节点加入队列中
                    queue.add(neighbor);
                }
                // 更新当前节点的邻居列表
                visited.get(n).neighbors.add(visited.get(neighbor));
            }
        }

        return visited.get(node);
    }
}

总结

大抵思路如下：

  • 因为是无向连通图，所以使用哈希表（原节点和克隆节点对应）来做访问记录
  • 先创建出邻居节点（仅复制值），用哈希表记录，再加入队列（BFS）

可以看出，DFS比BFS简单很多，但是实现起来远没有BFS直观，BFS虽然预处理比较复杂，但是总体来讲，不会太脱离BFS的标准结构。还有要注意的是，DFS有个使用的先决条件，就是需要参数本身并不复杂，没有太多参量要交给隐式栈来维护，还有 哈希表 在这类问题中也是常用且好用的结构。

除法求值(medium)

做题过程

想了一下大致思路，感觉蛮复杂的，首先要把所有倒数加进去，然后必须要有一个哈希表来维护所有的结果，不然不利于查询，最麻烦的就是这里必须要用DFS，因为必须要找到回路，或者找不下去才能停止查找，BFS不太能直观解决这种存在回路的问题，总之，思路很不清晰。结果官方题解是并查集。

算法概述

原题

本题要求为给出一个变量对数组和一个实数值数组，以及一个查询数组，实数值数组代表变量对的商，需要返回查询数组中要就计算的变量对的商。使用 并查集 或者 BFS （官方题解）。

BFS:

  • 时间复杂度为
  • 空间复杂度为

C++

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        // 记录边数（变量对的对数）
        int nvars = 0;
        unordered_map<string, int> variables;

        int n = equations.size();
        for (int i = 0; i < n; i++) {
            if (variables.find(equations[i][0]) == variables.end()) {
                variables[equations[i][0]] = nvars++;
            }
            if (variables.find(equations[i][1]) == variables.end()) {
                variables[equations[i][1]] = nvars++;
            }
        }

        // 对于每个点，存储其直接连接到的所有点及对应的权值
        vector<vector<pair<int, double>>> edges(nvars);
        for (int i = 0; i < n; i++) {
            int va = variables[equations[i][0]], vb = variables[equations[i][1]];
            edges[va].push_back(make_pair(vb, values[i]));
            edges[vb].push_back(make_pair(va, 1.0 / values[i]));
        }

        vector<double> ret;
        for (const auto& q: queries) {
            double result = -1.0;
            if (variables.find(q[0]) != variables.end() && variables.find(q[1]) != variables.end()) {
                int ia = variables[q[0]], ib = variables[q[1]];
                if (ia == ib) {
                    result = 1.0;
                } else {
                    queue<int> points;
                    points.push(ia);
                    vector<double> ratios(nvars, -1.0);
                    ratios[ia] = 1.0;

                    while (!points.empty() && ratios[ib] < 0) {
                        int x = points.front();
                        points.pop();

                        for (const auto [y, val]: edges[x]) {
                            if (ratios[y] < 0) {
                                ratios[y] = ratios[x] * val;
                                points.push(y);
                            }
                        }
                    }
                    result = ratios[ib];
                }
            }
            ret.push_back(result);
        }
        return ret;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/evaluate-division/solutions/548585/chu-fa-qiu-zhi-by-leetcode-solution-8nxb/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
public:
    int findf(vector<int>& f, vector<double>& w, int x) {
        if (f[x] != x) {
            int father = findf(f, w, f[x]);
            w[x] = w[x] * w[f[x]];
            f[x] = father;
        }
        return f[x];
    }

    void merge(vector<int>& f, vector<double>& w, int x, int y, double val) {
        int fx = findf(f, w, x);
        int fy = findf(f, w, y);
        f[fx] = fy;
        w[fx] = val * w[y] / w[x];
    }

    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        int nvars = 0;
        unordered_map<string, int> variables;

        int n = equations.size();
        for (int i = 0; i < n; i++) {
            if (variables.find(equations[i][0]) == variables.end()) {
                variables[equations[i][0]] = nvars++;
            }
            if (variables.find(equations[i][1]) == variables.end()) {
                variables[equations[i][1]] = nvars++;
            }
        }
        vector<int> f(nvars);
        vector<double> w(nvars, 1.0);
        for (int i = 0; i < nvars; i++) {
            f[i] = i;
        }

        for (int i = 0; i < n; i++) {
            int va = variables[equations[i][0]], vb = variables[equations[i][1]];
            merge(f, w, va, vb, values[i]);
        }
        vector<double> ret;
        for (const auto& q: queries) {
            double result = -1.0;
            if (variables.find(q[0]) != variables.end() && variables.find(q[1]) != variables.end()) {
                int ia = variables[q[0]], ib = variables[q[1]];
                int fa = findf(f, w, ia), fb = findf(f, w, ib);
                if (fa == fb) {
                    result = w[ia] / w[ib];
                }
            }
            ret.push_back(result);
        }
        return ret;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/evaluate-division/solutions/548585/chu-fa-qiu-zhi-by-leetcode-solution-8nxb/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

总结

c++的api方便一点，就用c++吧。并查集放后面再学，等我为这个主题添加一个搜索功能，不然太难找之前做过的算法整理了。还有这个图我的基础不好，这个解法整理起来蛮痛苦的，后面再回来弄图吧，把离散再好好看一看。

  • Title: 图论 --面试经典150题
  • Author: tobegold574
  • Created at : 2024-12-30 14:48:59
  • Updated at : 2024-12-31 11:42:05
  • Link: https://tobegold574.me/2024/12/30/图论-面试经典150题/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
图论 --面试经典150题
  1. 被围绕的区域(medium)
    1. 做题过程
    2. 算法概述
    3. JAVA
    4. 总结
  2. 克隆图(medium)
    1. 做题过程
    2. 算法概述
    3. JAVA
    4. 总结
  3. 除法求值(medium)
    1. 做题过程
    2. 算法概述
    3. C++
    4. 总结