第二十七天

我使用的C++，错误的地方请见谅，文章初衷仅用来督促本人学习，如果恰巧能够给你带来帮助，我会十分开心。

文章目录

• 第二十七天
• 一、130. 被围绕的区域
• 二、797. 所有可能的路径
• 三、78. 子集

一、130. 被围绕的区域

给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/surrounded-regions
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    int m, n;
    void dfs(vector<vector<char>>& board, int x, int y){
        if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O'){
            return;
        }
        board[x][y] = 'A';//将与边界相连的O标记为A，并向四周扩散
        dfs(board, x, y + 1);
        dfs(board, x, y - 1);
        dfs(board, x + 1, y);
        dfs(board, x - 1, y);
    }
    void solve(vector<vector<char>>& board) {
        //能活的棋子必然与边界相连，所以从边界上的o开始遍历，将棋盘中间接或直接相连的o标记为A，随后只需将A改为O，没有标记为A的o改为X即可
        //深度遍历尝试
        m = board.size();
        if (m == 0){
            return;
        }
        n = board[0].size();
        for (int i = 0; i < m; ++i){//左右两个边界
            dfs(board, i, 0);
            dfs(board, i, n - 1);
        }
        for (int i = 0; i < n; ++i){
            dfs(board, 0, i);
            dfs(board, m - 1, i);
        }
        for (int i = 0; i < m; ++i){
            for (int j = 0; j < n; ++j){
                if (board[i][j] == 'A'){
                    board[i][j] = 'O';
                }
                else if (board[i][j] == 'O') {
                    board[i][j] = 'X'; 
                }
            }
        }


    }
};

二、797. 所有可能的路径

给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）

graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/all-paths-from-source-to-target
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> stack;//利用栈来储存路径
    void dfs(vector<vector<int>>& graph, int x, int n){
        if (x == n){
            ans.push_back(stack);
        }
        for (auto& y : graph[x]){//将每一个点可以到访的点进行遍历
            stack.push_back(y);
            dfs(graph, y, n);
            stack.pop_back();
        }
    }
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        //有向无环图，意味着一条路径中一个点只会遍历到一次，不会出现重复遍历的情况，不需要另作标记
        //深度遍历每一条路径
        stack.push_back(0);
        dfs(graph, 0, graph.size() - 1);//从0开始遍历
        return ans;

    }
};

三、78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> stk;
    void dfs (vector<int>& nums, int cur){
        if (cur == nums.size()){
            ans.push_back(stk);
            return;
        }
        stk.push_back(nums[cur]);//一个选取，一个不选取，可以完美实现全排列
        dfs(nums, cur + 1);
        stk.pop_back();
        dfs(nums, cur + 1);
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return ans;
    }
};