图论力扣题型总结

Category： DSA

找路径问题

模板题

剑指 Offer 35. 复杂链表的复制; 感觉跟下一个题很类似, 就放在这里了, 哈希记录遍历情况, 然后递归创建新节点即可(当然还有纯链表做法)

class Solution {
    unordered_map<Node*, Node*> used;

public:
    Node* copyRandomList(Node* head) {
        if (!head) return head;
        if (!used.count(head)) {
            auto node = new Node(head->val);
            used[head] = node;
            node->next = copyRandomList(head->next);
            node->random = copyRandomList(head->random);
        }
        return used[head];
    }
};

拆链表方法:

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return head;
        // copy and link next
        for (auto cur{head}; cur; cur = cur->next->next) {
            auto tmp{new Node(cur->val)};
            tmp->next = cur->next;
            cur->next = tmp;
        }
        // copy random
        for (auto cur{head}; cur; cur = cur->next->next)
            cur->next->random = cur->random ? cur->random->next : nullptr;
        // separate
        auto ans{head->next};
        for (auto cur{head}; cur; cur = cur->next) {
            auto tmp{cur->next};
            cur->next = cur->next->next;
            tmp->next = cur->next ? cur->next->next : nullptr;
        }
        return ans;
    }
};

133. 克隆图;

DFS:

class Solution {
    unordered_map<Node*, Node*> used;

public:
    Node* cloneGraph(Node* node) {
        if (!node) return node;
        if (used.count(node)) return used[node];
        auto ans{new Node(node->val)};
        used[node] = ans;
        for (auto x : node->neighbors)
            ans->neighbors.emplace_back(cloneGraph(x));

        return ans;
    }
};

BFS: 不太容易想到

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) return node;
        unordered_map<Node*, Node*> used;
        used[node] = new Node(node->val);
        queue<Node*> q;
        q.emplace(node);
        while (!q.empty()) {
            auto cur = q.front();
            q.pop();
            for (auto x : cur->neighbors) {
                if (!used.count(x)) {
                    used[x] = new Node(x->val);
                    q.emplace(x);
                }
                used[cur]->neighbors.emplace_back(used[x]);
            }
        }
        return used[node];
    }
};

797. 所有可能的路径;

DFS:

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<int> path{0};
        vector<vector<int>> ans;
        int n = graph.size();
        function<void(int)> f = [&](int x) {
            if (x == n - 1) {
                ans.emplace_back(path);
                return;
            }
            for (int y : graph[x]) {
                path.emplace_back(y);
                f(y);
                path.pop_back();
            }
        };
        f(0);
        return ans;
    }
};

841. 钥匙和房间 - 力扣（LeetCode）; 本质就是找遍历过的房间

DFS:

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int n = rooms.size();
        bool vs[n];
        memset(vs, false, sizeof(vs));
        function<void(int)> dfs = [&](int x) {
            for (int y : rooms[x]) {
                if (!vs[y]) vs[y] = true, f(y);
            }
        };
        vs[0] = true;
        dfs(0);
        for (int i{}; i < n; ++i)
            if (!vs[i]) return false;
        return true;
    }
};

BFS:

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int n = rooms.size();
        bool vs[n];
        memset(vs, false, sizeof(vs));
        queue<int> q;
        vs[0] = true;
        q.emplace(0);
        while (!q.empty()) {
            auto x = q.front();
            q.pop();
            for (int y : rooms[x])
                if (!vs[y]) vs[y] = true, q.emplace(y);
        }
        for (int i{}; i < n; ++i)
            if (!vs[i]) return false;
        return true;
    }
};

1615. 最大网络秩 - 力扣（LeetCode）;

class Solution {
public:
    int maximalNetworkRank(int n, vector<vector<int>>& roads) {
        int g[n][n], cnt[n];
        memset(g, 0, sizeof(g)), memset(cnt, 0, sizeof(cnt));
        for (auto v : roads) {
            int a{v[0]}, b{v[1]};
            g[a][b] = g[b][a] = 1;
            ++cnt[a], ++cnt[b];
        }
        int ans{};
        // 遍历
        for (int i{}; i < n; ++i)
            for (int j{i + 1}; j < n; ++j)
                ans = max(ans, cnt[i] + cnt[j] - g[i][j]);
        return ans;
    }
};

1042. 不邻接植花;

1376. 通知所有员工所需的时间;深搜

岛屿问题(二维网格上的搜索)

方向数组的简洁写法

这里总结一下方向数组, 一般来说就是一个 $4\times2$ 或者 $8\times2$ 的数组, 但是还可以更简洁, 还不容易出错.

四个方向

这里先给出一般的写法:

int dirs[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1};
for (int i{}; i < 4; ++i) {
    int nextx = x + dirs[i][0], nexty = y + dirs[i][1];
}

然后是优化版本:(一维数组$size=5$)

int dirs[] = {1, 0, -1, 0, 1};
for (int i{}; i < 4; ++i) {
    int nextx = x + dirs[i], nexty = y + dirs[i + 1];
    // cout << dirs[i] << " " << dirs[i + 1] << endl;
}

因为本质上就是四个方向, 不需要管顺序, 所以这样没有问题.

八个方向

这个有点技巧, 可以不用数组来做:

for (int i{-1}; i < 2; ++i) {
    for (int j{-1}; j < 2; ++j) {
        if (i == 0 && j == 0) // 去掉未更改的方向: (0, 0)
            continue;
        int nx = x + i, ny = y + j;
        // ...
    }
}

是不是很优雅.

数量

200. 岛屿数量;

DFS:

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int dirs[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1};
        bool visited[m][n];
        memset(visited, false, sizeof(visited));
        function<void(int, int)> f = [&](int x, int y) {
            if (visited[x][y] || grid[x][y] == '0') return;
            visited[x][y] = true;
            for (int i{}; i < 4; ++i) {
                int nextx = x + dirs[i][0], nexty = y + dirs[i][1];
                if (nextx < 0 || nextx >= m || nexty < 0 || nexty >= n)
                    continue;
                f(nextx, nexty);
            }
        };
        int ans{};
        for (int i{}; i < m; ++i)
            for (int j{}; j < n; ++j)
                if (!visited[i][j] && grid[i][j] == '1') {
                    visited[i][j] = true;
                    ++ans;
                    f(i, j);
                }
        return ans;
    }
};

BFS:

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int dirs[4][2]{-1, 0, 0, 1, 1, 0, 0, -1};
        bool visited[m][n];
        memset(visited, false, sizeof(visited));
        auto f = [&](int x, int y) {
            queue<pair<int,int>> que;
            que.emplace(x, y);
            visited[x][y] = true;
            while (!que.empty()) {
                auto [cx, cy] = que.front();
                que.pop();
                for (int i{}; i < 4; ++i) {
                    int nx = cx + dirs[i][0], ny = cy + dirs[i][1];
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                    if (!visited[nx][ny] && grid[nx][ny] == '1') {
                        que.emplace(nx, ny);
                        visited[nx][ny] = true;
                    }
                }
            }
        };
        int ans{};
        for (int i{}; i < m; ++i)
            for (int j{}; j < n; ++j)
                if (!visited[i][j] && grid[i][j] == '1') {
                    ++ans;
                    f(i, j);
                }
        return ans;
    }
};

面试题 16.19. 水域大小 - 力扣（Leetcode）;(本质上还是求数量, 就是多了个对角线而已, 海拔不用管)

class Solution {
public:
    vector<int> pondSizes(vector<vector<int>>& land) {
        vector<int> ans;
        int m = land.size(), n = land[0].size(), cnt{};
        bool vs[m][n];
        memset(vs, 0, sizeof(vs));

        function<void(int, int)> f = [&](int x, int y) {
            for (int i{-1}; i < 2; ++i) {
                for (int j{-1}; j < 2; ++j) {
                    if (i == 0 && j == 0)
                        continue;
                    int nx = x + i, ny = y + j;
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n || vs[nx][ny])
                        continue;
                    vs[nx][ny] = true;
                    if (land[nx][ny] == 0)
                        ++cnt, f(nx, ny);
                }
            }
        };
        for (int i{}; i < m; ++i)
            for (int j{}; j < n; ++j)
                if (!vs[i][j] && land[i][j] == 0)
                    cnt = 1, vs[i][j] = true, f(i, j), ans.emplace_back(cnt);
        sort(ans.begin(), ans.end());
        return ans;
    }
};

面积

695. 岛屿的最大面积;

DFS:

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int ds[4][2]{0, 1, 1, 0, 0, -1, -1, 0}, cnt{}, ans{};
        bool vs[m][n];
        memset(vs, false, sizeof(vs));
        function<void(int, int)> dfs = [&](int x, int y) {
            for (int i{}; i < 4; ++i) {
                int nx{x + ds[i][0]}, ny{y + ds[i][1]};
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                if (!vs[nx][ny] && grid[nx][ny])
                    vs[nx][ny] = true, ++cnt, dfs(nx, ny);
            }
        };
        for (int i{}; i < m; ++i)
            for (int j{}; j < n; ++j)
                if (!vs[i][j] && grid[i][j])
                    cnt = 1, vs[i][j] = true, dfs(i, j), ans = max(ans, cnt);
        return ans;
    }
};

BFS:

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int ds[4][2]{0, 1, 1, 0, 0, -1, -1, 0}, cnt{}, ans{};
        bool vs[m][n];
        memset(vs, false, sizeof(vs));
        queue<pair<int, int>> q;
        auto bfs = [&](int x, int y) {
            q.push({x, y});
            while (!q.empty()) {
                auto [a, b] = q.front();
                q.pop();
                for (int i{}; i < 4; ++i) {
                    int nx{a + ds[i][0]}, ny{b + ds[i][1]};
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                    if (!vs[nx][ny] && grid[nx][ny])
                        vs[nx][ny] = true, ++cnt, q.push({nx, ny});
                }
            }
        };
        for (int i{}; i < m; ++i)
            for (int j{}; j < n; ++j)
                if (!vs[i][j] && grid[i][j])
                    cnt = 1, vs[i][j] = true, bfs(i, j), ans = max(ans, cnt);
        return ans;
    }
};

遍历找数量

剑指 Offer 13. 机器人的运动范围;

DFS:

class Solution {
public:
    int movingCount(int m, int n, int k) {
        int ds[4][2]{0, 1, 1, 0, 0, -1, -1, 0};
        auto calc = [](int num) { // 计算数位和
            int ans{};
            while (num) ans += num % 10, num /= 10;
            return ans;
        };
        bool vs[m][n];
        memset(vs, false, sizeof(vs));
        int ans{1};
        function<void(int, int)> dfs = [&](int x, int y) {
            for (int i{}; i < 4; ++i) {
                int nx{x + ds[i][0]}, ny{y + ds[i][1]};
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                if (!vs[nx][ny] && calc(nx) + calc(ny) <= k)
                    ++ans, vs[nx][ny] = true, dfs(nx, ny);
            }
        };
        vs[0][0] = true;
        dfs(0, 0);
        return ans;
    }
};

BFS:

class Solution {
public:
    int movingCount(int m, int n, int k) {
        int ds[4][2]{0, 1, 1, 0, 0, -1, -1, 0};
        auto calc = [](int num) { // 计算数位和
            int ans{};
            while (num) ans += num % 10, num /= 10;
            return ans;
        };
        bool vs[m][n];
        memset(vs, false, sizeof(vs));
        int ans{1};
        queue<pair<int, int>> q;
        auto bfs = [&](int x, int y) {
            q.emplace(x, y);
            while (!q.empty()) {
                auto [a, b] = q.front();
                q.pop();
                for (int i{}; i < 4; ++i) {
                    int nx{a + ds[i][0]}, ny{b + ds[i][1]};
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                    if (!vs[nx][ny] && calc(nx) + calc(ny) <= k)
                        ++ans, vs[nx][ny] = true, q.emplace(nx, ny);
                }
            }
        };
        vs[0][0] = true;
        bfs(0, 0);
        return ans;
    }
};

修改一个块

827. 最大人工岛 - 力扣（Leetcode）;

class Solution {
public:
    int largestIsland(vector<vector<int>> &grid) {
        int n = grid.size();
        bool vs[n][n];
        memset(vs, 0, sizeof(vs));
        int ds[][2] = {1, 0, 0, 1, -1, 0, 0, -1};
        unordered_map<int, int> cnt; // num:square
        int square{};
        function<void(int, int, int)> f = [&](int x, int y, int num) {
            for (int i{}; i < 4; ++i) {
                int nx = x + ds[i][0], ny = y + ds[i][1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n || vs[nx][ny] ||
                    grid[nx][ny] == 0)
                    continue;
                vs[nx][ny] = 1, grid[nx][ny] = num, ++square, f(nx, ny, num);
            }
        };
        bool isFull{true};
        // 给不同岛屿标号
        for (int i{}, k{1}; i < n; ++i) {
            for (int j{}; j < n; ++j) {
                if (grid[i][j] == 0)
                    isFull = false;
                if (!vs[i][j] && grid[i][j] == 1) {
                    vs[i][j] = 1, square = 1, grid[i][j] = k, f(i, j, k);
                    cnt[k++] = square;
                }
            }
        }
        if (isFull)
            return n * n;
        int ans{};
        unordered_set<int> vsg; // 记录加入岛屿的编号
        for (int i{}; i < n; ++i) {
            for (int j{}; j < n; ++j) {
                if (grid[i][j] == 0) {
                    int tmp{1}; // 加入的块大小
                    vsg.clear();
                    for (int d{}; d < 4; ++d) {
                        // near coordinate
                        int ni = i + ds[d][0], nj = j + ds[d][1];
                        if (ni < 0 || ni >= n || nj < 0 || nj >= n)
                            continue;
                        int num = grid[ni][nj];
                        if (vsg.count(num))
                            continue;
                        tmp += cnt[num];
                        vsg.insert(num);
                    }
                    ans = max(ans, tmp);
                }
            }
        }
        return ans;
    }
};

飞地问题: 考虑边界处理

数量

1020. 飞地的数量 - 力扣（LeetCode）;

DFS:

class Solution {
public:
    int numEnclaves(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int ds[4][2]{0, 1, 1, 0, 0, -1, -1, 0}, cnt{}, ans{};
        bool vs[m][n];
        memset(vs, false, sizeof(vs));
        function<void(int, int)> dfs = [&](int x, int y) {
            for (int i{}; i < 4; ++i) {
                int nx{x + ds[i][0]}, ny{y + ds[i][1]};
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                if (!vs[nx][ny] && grid[nx][ny])
                    vs[nx][ny] = true, ++cnt, dfs(nx, ny);
            }
        };
        // 先去掉不是飞地的单元格
        for (int i{}; i < m; ++i) { // 首尾两列
            if (grid[i][0]) vs[i][0] = true, dfs(i, 0);
            if (grid[i][n - 1]) vs[i][n - 1] = true, dfs(i, n - 1);
        }
        for (int j{1}; j < n - 1; ++j) {
            if (grid[0][j]) vs[0][j] = true, dfs(0, j);
            if (grid[m - 1][j]) vs[m - 1][j] = true, dfs(m - 1, j);
        }

        for (int i{1}; i < m - 1; ++i)
            for (int j{1}; j < n - 1; ++j)
                if (!vs[i][j] && grid[i][j])
                    cnt = 1, vs[i][j] = true, dfs(i, j), ans += cnt;
        return ans;
    }
};

BFS:

class Solution {
public:
    int numEnclaves(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int ds[4][2]{0, 1, 1, 0, 0, -1, -1, 0}, cnt{}, ans{};
        bool vs[m][n];
        memset(vs, false, sizeof(vs));
        queue<pair<int, int>> q;
        auto bfs = [&](int x, int y) {
            q.emplace(x, y);
            while (!q.empty()) {
                auto [a, b] = q.front();
                q.pop();
                for (int i{}; i < 4; ++i) {
                    int nx{a + ds[i][0]}, ny{b + ds[i][1]};
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                    if (!vs[nx][ny] && grid[nx][ny])
                        vs[nx][ny] = true, ++cnt, q.emplace(nx, ny);
                }
            }
        };
        // 先去掉不是飞地的单元格
        for (int i{}; i < m; ++i) { // 首尾两列
            if (grid[i][0]) vs[i][0] = true, bfs(i, 0);
            if (grid[i][n - 1]) vs[i][n - 1] = true, bfs(i, n - 1);
        }
        for (int j{1}; j < n - 1; ++j) {
            if (grid[0][j]) vs[0][j] = true, bfs(0, j);
            if (grid[m - 1][j]) vs[m - 1][j] = true, bfs(m - 1, j);
        }

        for (int i{1}; i < m - 1; ++i)
            for (int j{1}; j < n - 1; ++j)
                if (!vs[i][j] && grid[i][j])
                    cnt = 1, vs[i][j] = true, bfs(i, j), ans += cnt;
        return ans;
    }
};

围绕

跟飞地反过来了: (原地修改)

130. 被围绕的区域;

DFS:

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int ds[4][2]{1, 0, 0, 1, -1, 0, 0, -1};
        int m = board.size(), n = board[0].size();
        bool vs[m][n];
        memset(vs, false, sizeof(vs));
        function<void(int, int, bool)> dfs = [&](int x, int y, bool isbound) {
            for (int i{}; i < 4; ++i) {
                int nx{x + ds[i][0]}, ny{y + ds[i][1]};
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                if (!vs[nx][ny] && board[nx][ny] == 'O')
                    vs[nx][ny] = true, board[nx][ny] = isbound ? 'O' : 'X',
                    dfs(nx, ny, isbound);
            }
        };
        for (int i{}; i < m; ++i) { // 首尾两列
            if (board[i][0] == 'O') vs[i][0] = true, dfs(i, 0, true);
            if (board[i][n - 1] == 'O')
                vs[i][n - 1] = true, dfs(i, n - 1, true);
        }
        for (int j{1}; j < n - 1; ++j) {
            if (board[0][j] == 'O') vs[0][j] = true, dfs(0, j, true);
            if (board[m - 1][j] == 'O')
                vs[m - 1][j] = true, dfs(m - 1, j, true);
        }

        for (int i{1}; i < m - 1; ++i)
            for (int j{1}; j < n - 1; ++j)
                if (!vs[i][j] && board[i][j] == 'O')
                    vs[i][j] = true, board[i][j] = 'X', dfs(i, j, false);
    }
};

BFS:

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int ds[4][2]{1, 0, 0, 1, -1, 0, 0, -1}, m = board.size(),
                                                n = board[0].size();
        bool vs[m][n];
        memset(vs, false, sizeof(vs));
        queue<pair<int, int>> q;
        auto bfs = [&](int x, int y, bool isbound = true) {
            q.emplace(x, y);
            while (!q.empty()) {
                auto [a, b] = q.front();
                q.pop();
                for (int i{}; i < 4; ++i) {
                    int nx{a + ds[i][0]}, ny{b + ds[i][1]};
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                    if (!vs[nx][ny] && board[nx][ny] == 'O')
                        vs[nx][ny] = true, board[nx][ny] = isbound ? 'O' : 'X',
                        q.emplace(nx, ny);
                }
            }
        };
        for (int i{}; i < m; ++i) { // 首尾两列
            if (board[i][0] == 'O') vs[i][0] = true, bfs(i, 0);
            if (board[i][n - 1] == 'O') vs[i][n - 1] = true, bfs(i, n - 1);
        }
        for (int j{1}; j < n - 1; ++j) {
            if (board[0][j] == 'O') vs[0][j] = true, bfs(0, j);
            if (board[m - 1][j] == 'O') vs[m - 1][j] = true, bfs(m - 1, j);
        }

        for (int i{1}; i < m - 1; ++i)
            for (int j{1}; j < n - 1; ++j)
                if (!vs[i][j] && board[i][j] == 'O')
                    vs[i][j] = true, board[i][j] = 'X', bfs(i, j, false);
    }
};

水流

417. 太平洋大西洋水流问题;

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int m = heights.size(), n = heights[0].size();
        int ds[4][2]{0, 1, 1, 0, 0, -1, -1, 0};
        vector<vector<bool>> vsa(m, vector<bool>(n)), vsp(m, vector<bool>(n));
        vector<vector<int>> ans;
        function<void(int, int, vector<vector<bool>>&)> dfs =
            [&](int x, int y, vector<vector<bool>>& vs) {
                for (int i{}; i < 4; ++i) {
                    int nx{x + ds[i][0]}, ny{y + ds[i][1]};
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n || vs[nx][ny])
                        continue;
                    if (heights[nx][ny] >= heights[x][y])
                        vs[nx][ny] = true, dfs(nx, ny, vs);
                }
            };
        for (int i{}; i < m; ++i) {
            vsp[i][0] = true, dfs(i, 0, vsp);
            vsa[i][n - 1] = true, dfs(i, n - 1, vsa);
        }
        for (int j{}; j < n; ++j) {
            vsp[0][j] = true, dfs(0, j, vsp);
            vsa[m - 1][j] = true, dfs(m - 1, j, vsa);
        }
        for (int i{}; i < m; ++i)
            for (int j{}; j < n; ++j)
                if (vsa[i][j] && vsp[i][j]) ans.push_back({i, j});
        return ans;
    }
};

简洁写法:

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int m = heights.size(), n = heights[0].size();
        int ds[4][2]{0, 1, 1, 0, 0, -1, -1, 0};
        vector<vector<bool>> vsa(m, vector<bool>(n, false)),
            vsp(m, vector<bool>(n, false));
        function<void(int, int, vector<vector<bool>>&)> dfs =
            [&](int x, int y, vector<vector<bool>>& vs) {
                if (vs[x][y]) return;
                vs[x][y] = true;
                for (int i{}; i < 4; ++i) {
                    int nx{x + ds[i][0]}, ny{y + ds[i][1]};
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n || vs[nx][ny])
                        continue;
                    if (heights[x][y] <= heights[nx][ny]) // 新值更大(逆流而上)
                        dfs(nx, ny, vs);
                }
            };
        for (int i{}; i < m; ++i) dfs(i, 0, vsp), dfs(i, n - 1, vsa);
        for (int j{}; j < n; ++j) dfs(0, j, vsp), dfs(m - 1, j, vsa);
        vector<vector<int>> ans;
        for (int i{}; i < m; ++i)
            for (int j{}; j < n; ++j)
                if (vsp[i][j] && vsa[i][j]) ans.push_back({i, j});
        return ans;
    }
};

BFS:

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int m = heights.size(), n = heights[0].size();
        int ds[4][2]{0, 1, 1, 0, 0, -1, -1, 0};
        vector<vector<bool>> vsa(m, vector<bool>(n, false)),
            vsp(m, vector<bool>(n, false));
        auto bfs = [&](int x, int y, vector<vector<bool>>& vs) {
            queue<pair<int, int>> q;
            q.emplace(x, y);
            while (!q.empty()) {
                auto [a, b] = q.front();
                q.pop();
                vs[a][b] = true;
                for (int i{}; i < 4; ++i) {
                    int nx{a + ds[i][0]}, ny{b + ds[i][1]};
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n || vs[nx][ny])
                        continue;
                    if (heights[a][b] <= heights[nx][ny]) // 新值更大(逆流而上)
                        vs[nx][ny] = true, q.emplace(nx, ny);
                }
            }
        };
        for (int i{}; i < m; ++i) bfs(i, 0, vsp), bfs(i, n - 1, vsa);
        for (int j{}; j < n; ++j) bfs(0, j, vsp), bfs(m - 1, j, vsa);
        vector<vector<int>> ans;
        for (int i{}; i < m; ++i)
            for (int j{}; j < n; ++j)
                if (vsp[i][j] && vsa[i][j]) ans.push_back({i, j});
        return ans;
    }
};

拓扑排序

课程表系列

207. 课程表;

class Solution {
public:
    bool canFinish(int n, vector<vector<int>>& arr) {
        vector<vector<int>> g(n);
        for (auto v : arr) // 建图
            g[v[0]].emplace_back(v[1]);
        vector<int> in(n);
        queue<int> q;
        for (auto v : g)
            for (auto i : v) ++in[i];
        for (int i{}; i < n; ++i)
            if (0 == in[i]) q.emplace(i);
        int ans{};
        while (!q.empty()) {
            int u = q.front();
            ++ans;
            q.pop();
            for (auto i : g[u])
                if (--in[i] == 0) q.emplace(i);
        }
        return ans == n;
    }
};

DFS:

class Solution {
public:
    bool canFinish(int n, vector<vector<int>>& arr) {
        vector<vector<int>> g(n);
        for (auto v : arr) // 建图
            g[v[0]].emplace_back(v[1]);
        int vs[n];         // 0:未遍历, 1:遍历中, 2:入栈
        memset(vs, 0, sizeof(vs));
        bool ans{true};
        function<void(int)> f = [&](int x) {
            vs[x] = 1;
            for (auto i : g[x])
                if (0 == vs[i]) {
                    f(i);
                    if (!ans) return;
                } else if (vs[i] == 1) {
                    ans = false;
                    return;
                }
            vs[x] = 2; // 记录
        };
        for (int i{}; i < n && ans; ++i)
            if (!vs[i]) f(i);
        return ans;
    }
};

210. 课程表 II;

class Solution {
public:
    vector<int> findOrder(int n, vector<vector<int>>& arr) {
        vector<vector<int>> g(n);
        for (auto v : arr) // 建图
            g[v[1]].emplace_back(v[0]);
        vector<int> in(n);
        queue<int> q;
        for (auto v : g)
            for (auto i : v) ++in[i];
        for (int i{}; i < n; ++i)
            if (0 == in[i]) q.emplace(i);
        vector<int> ans(n);
        int i{};
        while (!q.empty()) {
            int u = q.front();
            ans[i++] = u;
            q.pop();
            for (auto i : g[u])
                if (--in[i] == 0) q.emplace(i);
        }
        return i != n ? vector<int>() : ans;
    }
};

考虑距离

广度优先

($\bigstar$)542. 01 矩阵;剑指 Offer II 107. 矩阵中的距离; (多源最短路)

需要从 0 开始考虑, 存入队列然后分别计算到最近的 1 的距离. (DP 更好)

 class Solution {
 public:
     vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
         int m = mat.size(), n = mat[0].size();
         int ds[4][2]{0, 1, 1, 0, 0, -1, -1, 0};
         bool vs[m][n];
         memset(vs, 0, sizeof(vs));
         auto ans(mat);
         queue<pair<int, int>> q; // 放入所有的 0
         for (int i{}; i < m; ++i)
             for (int j{}; j < n; ++j)
                 if (mat[i][j] == 0) q.emplace(i, j), vs[i][j] = true;
         // BFS, 找 0 最近的 1
         while (!q.empty()) {
             auto [x, y] = q.front();
             q.pop();
             for (int i{}; i < 4; ++i) {
                 int nx{x + ds[i][0]}, ny{y + ds[i][1]};
                 if (nx < 0 || nx >= m || ny < 0 || ny >= n || vs[nx][ny])
                     continue;
                 vs[nx][ny] = true;
                 ans[nx][ny] += ans[x][y];
                 q.emplace(nx, ny);
             }
         }
         return ans;
     }
 };

下面这个题跟 0-1 矩阵恰好反过来了.

1162. 地图分析;

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int ds[4][2]{0, 1, 1, 0, 0, -1, -1, 0};
        bool vs[m][n];
        memset(vs, false, sizeof(vs));
        queue<pair<int, int>> q;
        for (int i{}; i < m; ++i)
            for (int j{}; j < n; ++j)
                if (grid[i][j]) // 1 放入队列
                    q.emplace(i, j), vs[i][j] = true;
        int ans{}, dist{};
        while (!q.empty()) {
            int nq = q.size();
            for (int k{}; k < nq; ++k) { // 这里是精髓, 遍历完层才更新距离, 而不是每走一个点就更新
                auto [x, y] = q.front();
                q.pop();
                ans = max(ans, dist);
                for (int i{}; i < 4; ++i) {
                    int nx{x + ds[i][0]}, ny{y + ds[i][1]};
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n || vs[nx][ny])
                        continue;
                    vs[nx][ny] = true;
                    q.emplace(nx, ny);
                }
            }
            ++dist;
        }
        return ans ? ans : -1;
    }
};

1091. 二进制矩阵中的最短路径;

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        if (grid[0][0]) return -1;
        int ds[][2]{0, 1, 1, 0, 0, -1, -1, 0, -1, 1, 1, -1, -1, -1, 1, 1};
        int m = grid.size(), n = grid[0].size(), vs[m][n];
        memset(vs, 0, sizeof(vs));
        queue<pair<int, int>> q;
        q.emplace(0, 0);
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            if (x == m - 1 && y == n - 1) return vs[x][y] + 1;
            for (int i{}; i < 8; ++i) {
                int nx{x + ds[i][0]}, ny{y + ds[i][1]};
                if (nx < 0 || nx >= m || ny < 0 || ny >= n || vs[nx][ny])
                    continue;
                if (!grid[nx][ny]) q.emplace(nx, ny), vs[nx][ny] = vs[x][y] + 1;
            }
        }
        return -1;
    }
};

优化的广搜

127. 单词接龙;需要优化的广度优先(暴力枚举单词)

class Solution {
public:
    int ladderLength(string beginWord, string endWord,
                     vector<string>& wordList) {
        unordered_set<string> st(wordList.begin(), wordList.end());
        if (!st.count(endWord)) return 0;
        unordered_map<string, int> vs; // count
        queue<string> q;
        q.emplace(beginWord);
        vs[beginWord] = 1;
        while (!q.empty()) {
            auto w = q.front();
            q.pop();
            int path = vs[w];
            for (int i{}; i < w.size(); ++i) {
                auto tmp{w};
                for (int j{}; j < 26; ++j) {
                    tmp[i] = j + 'a';
                    if (tmp == endWord) return path + 1;
                    if (st.count(tmp) && !vs.count(tmp))
                        vs[tmp] = path + 1, q.emplace(tmp);
                }
            }
        }
        return 0;
    }
};

1129. 颜色交替的最短路径 - 力扣（LeetCode）;

单源最短路

Dijkstra 算法

787. K 站中转内最便宜的航班;

2699. 修改图中的边权;(两次 Dijkstra 的题, 需要考虑很多情况)

连通分量

无向图的连通分量

本质上就是通过 DFS 来做的.

2316. 统计无向图中无法互相到达点对数 - 力扣（LeetCode）;

class Solution {
public:
    long long countPairs(int n, vector<vector<int>>& edges) {
        vector<vector<int>> g(n);
        for (auto v: edges) {
            g[v[0]].emplace_back(v[1]);
            g[v[1]].emplace_back(v[0]);
        }
        vector<bool> vs(n);
        function<int(int)> f = [&](int x) {
            if (vs[x]) {
                return 0;
            }
            vs[x] = true;
            int t{1};
            for (auto i : g[x]) {
                if (!vs[i]) {
                    t += f(i);
                }
            }
            return t;
        };
        auto ans = 0ll, s = ans;
        for (int i{}; i < n; ++i) {
            int t = f(i);
            ans += s * t;
            s += t;
        }
        return ans;
    }
};

上篇数字十进制位,四则运算编程技巧及力扣题目总结

下篇二分查找力扣题目总结