Leetcode 刷题笔记-Leetcode 101 第6章 搜索

Leetcode 刷题笔记-Leetcode 101 第6章 搜索

搜索

深度优先搜索和广度优先搜索是两种最常见的优先搜索方法，它们被广泛地运用在图和树等结构中进行搜索。

深度优先搜索

Leetcode 695

岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直的四个方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。岛屿的面积是岛上值为 1 的单元格的数目。计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

class Solution {
public:
    static int DFS(vector<vector<int>> & grid,int x,int y,int m,int n){
        if(x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0){
            return 0;
        }
        grid[x][y] = 0;
        return 1 + DFS(grid,x+1,y,m,n) + DFS(grid,x-1,y,m,n) + DFS(grid,x,y+1,m,n) + DFS(grid,x,y-1,m,n);
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int maxarea = 0;
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(grid[i][j] == 1){
                    maxarea = max(maxarea,DFS(grid,i,j,m,n));
                }
            }
        }
        return maxarea;
    }
};

分析：标准的DFS，重点要判断是否越界以及返回值的处理。

错误：基本思路是正确的，返回值的处理有问题，以及想的有些复杂。

Leetcode 547

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。返回矩阵中 省份 的数量。

class Solution {
public:
    static void DFS(vector<vector<int>>& isConnected, vector<bool>& visit,int x,int n){
        if(x < 0 || x >= n || visit[x] == true){
            return;
        }
        visit[x] = true;
        for(int i=0;i<n;i++){
            if(isConnected[x][i] == 1){
                DFS(isConnected,visit,i,n);
            }
        }
        return;
    }
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        int sumCount = 0;
        vector<bool> visit(n);
        fill(visit.begin(),visit.end(),false);
        for(int i=0;i<n;i++){
            if(visit[i] == false){
                DFS(isConnected,visit,i,n);
                ++sumCount;
            }
        }
        return sumCount;
    }
};

分析：还是比较基本的DFS，只不过是一个一维的DFS，比较简单

错误：开始的思路有一些偏差，后面纠正过来没什么问题了。

Leetcode 417

有一个 m × n 的矩形岛屿，与太平洋和大西洋相邻。 太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格高于海平面的高度 。岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。返回网格坐标 result 的 2D 列表 ，其中 result[i] = [r<sub>i</sub>, c<sub>i</sub>] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。

class Solution {
public:
    static void DFS(vector<vector<int>>& heights,vector<vector<bool>>& Ocean,int x,int y,int m,int n){
        Ocean[x][y] = true;
        if(x+1 < m && Ocean[x+1][y] == false && heights[x+1][y] >= heights[x][y]){
            DFS(heights,Ocean,x+1,y,m,n);
        }
        if(x-1 >= 0 && Ocean[x-1][y] == false && heights[x-1][y] >= heights[x][y]){
            DFS(heights,Ocean,x-1,y,m,n);
        }
        if(y+1 < n && Ocean[x][y+1] == false && heights[x][y+1] >= heights[x][y]){
            DFS(heights,Ocean,x,y+1,m,n);
        }
        if(y-1 >= 0 && Ocean[x][y-1] == false && heights[x][y-1] >= heights[x][y]){
            DFS(heights,Ocean,x,y-1,m,n);
        }
        return;
    }
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int m = heights.size();
        int n = heights[0].size();
        vector<vector<bool>> pOcean(m,vector<bool>(n,false));
        vector<vector<bool>> aOcean(m,vector<bool>(n,false));
        for(int i=0;i<m;++i){
            if(pOcean[i][0] == false){
                DFS(heights,pOcean,i,0,m,n);
            }
            if(aOcean[i][n-1] == false){
                DFS(heights,aOcean,i,n-1,m,n);
            }
        }
        for(int i=0;i<n;++i){
            if(pOcean[0][i] == false){
                DFS(heights,pOcean,0,i,m,n);
            }
            if(aOcean[m-1][i] == false){
                DFS(heights,aOcean,m-1,i,m,n);
            }
        }
        vector<vector<int>> result;
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(pOcean[i][j] == true && aOcean[i][j] == true){
                    result.push_back(vector<int>{i,j});
                }
            }
        }
        return result;
    }
};

分析：仍然是比较普通的DFS，不过只要对周围的一圈进行DFS就足够了，不需要全部遍历。

错误：细节问题，写的时候一定好好检查 m和 n有没有用反。

回溯法

Leetcode 46

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。

class Solution {
public:
    static void backtracking(vector<int>& nums,int level,vector<vector<int>>&result){
        if(level == nums.size()-1){
            result.push_back(nums);
            return;
        }
        for(int i=level;i<nums.size();i++){
            swap(nums[i],nums[level]);
            backtracking(nums,level+1,result);
            swap(nums[i],nums[level]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        backtracking(nums,0,result);
        return result;
    }
};

分析：对于每一个当前位置 i，我们可以将其于之后的任意位置交换，然后继续处理位置 i+1，直到处理到最后一位。为了防止我们每此遍历时都要新建一个子数组储存位置 i之前已经交换好的数字，我们可以利用回溯法，只对原数组进行修改，在递归完成后再修改回来。

错误：学习一下回溯法的基本框架。

Leetcode 77

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

class Solution {
public:
    static void backtracking(vector<vector<int>> &result,vector<int> &temp,int n,int level,int k){
        if(temp.size() == k){
            result.push_back(temp);
            return;
        }
        for(int i=level+1;i<=n;++i){
            temp.push_back(i);
            backtracking(result,temp,n,i,k);
            temp.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> result;
        vector<int> temp;
        backtracking(result,temp,n,0,k);
        return result;
    }
};

分析：类似于排列问题，也可以进行回溯。排列回溯的是交换的位置，而组合回溯的是是否把当前的数字加入结果中。

错误：需要有一个记录状态的数值，要不然就变成全排列了。

Leetcode 79

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

class Solution {
public:
    static void backtracking(vector<vector<char>>& board, string &word,int x,int y,int m,int n,vector<vector<bool>> &visited,bool &find,int level){
        if(x < 0 || x >= m || y < 0 || y >= n){
            return;
        }
        if(visited[x][y] == true || word[level] != board[x][y] || find == true){
            return;
        }
        if(level == word.size() - 1){
            find = true;
            return;
        }
        visited[x][y] = true;
        backtracking(board,word,x+1,y,m,n,visited,find,level+1);
        backtracking(board,word,x-1,y,m,n,visited,find,level+1);
        backtracking(board,word,x,y+1,m,n,visited,find,level+1);
        backtracking(board,word,x,y-1,m,n,visited,find,level+1);
        visited[x][y] = false;
        return;
    }
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size();
        int n = board[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        bool find = false;
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                backtracking(board,word,i,j,m,n,visited,find,0);
            }
        }
        return find;
    }
};

分析：典型回溯题，判断条件需要多一些

错误1：回溯法不要有返回值，都使用引用传参

错误2：判断条件：①是否越界②访问过③不匹配④已经确定对的了

Leetcode 51

n皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的n皇后问题的解决方案。

class Solution {
public:
    void backtracking(vector<vector<string>> & result,vector<string> tempresult,vector<bool> &column,vector<bool> &ldiag,vector<bool> &rdiag,int n,int level){
        if(level == n){
            result.push_back(tempresult);
            return;
        }
        for(int i=0;i<n;++i){
            if (column[i] || ldiag[n-level+i-1] || rdiag[level+i]) {
                continue;
            }
            tempresult[level][i] = 'Q';
            column[i] = ldiag[n-level+i-1] = rdiag[level+i] = true;
            backtracking(result,tempresult,column,ldiag,rdiag,n,level+1);
            column[i] = ldiag[n-level+i-1] = rdiag[level+i] = false;
            tempresult[level][i] = '.';
        }
        return;
    }
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result;
        string tempstring = "";
        for(int i=0;i<n;i++){
            tempstring += ".";
        }
        vector<string> tempresult(n,tempstring);
        vector<bool> column(n,false);
        vector<bool> ldiag(2*n-1,false);
        vector<bool> rdiag(2*n-1,false);
        backtracking(result,tempresult,column,ldiag,rdiag,n,0);
        return result;
    }
};

分析：最典型的回溯法之一。类似于在矩阵中寻找字符串，本题也是通过修改状态矩阵来进行回溯。不同的是，我们需要对每一行、列、左斜、右斜建立访问数组，来记录它们是否存在皇后。本题需要判断满足条件的结果中每一行或列有且仅有一个皇后。这是因为我们一共只有 n行和 n列。所以如果我们通过对每一行遍历来插入皇后，我们就不需要对行建立访问数组了。

错误：再理解吧。

广度优先搜索

Leetcode 934

在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。返回必须翻转的 0 的最小数目。（可以保证答案至少是 1 。）

class Solution {
public:
    static void DFS(vector<vector<int>>& grid,queue<pair<int,int>> &points,int x,int y,int n){
        if(x < 0 || x >= n || y < 0 || y >= n || grid[x][y] == 2){
            return;
        }
        if(grid[x][y] == 0){
            points.push({x,y});
            return;
        }
        grid[x][y] = 2;
        DFS(grid,points,x+1,y,n);
        DFS(grid,points,x-1,y,n);
        DFS(grid,points,x,y+1,n);
        DFS(grid,points,x,y-1,n);
        return;
    }
    int shortestBridge(vector<vector<int>>& grid) {
        int n = grid.size();
        queue<pair<int,int>> points;
        bool find = false;
        for(int i=0;i<n;++i){
            if(find == true){
                break;
            }
            for(int j=0;j<n;++j){
                if(grid[i][j] == 1){
                    find = true;
                    DFS(grid,points,i,j,n);
                    break;
                }
            }
        }
        int level = 0;
        vector<vector<int>> d = {{0,1},{0,-1},{1,0},{-1,0}};
        while(!points.empty()){
            ++level;
            int n_points = points.size();
            while(n_points--){
                auto [r,c] = points.front();
                grid[r][c] = 2;
                points.pop();
                for(int k=0;k<4;k++){
                    int x = r + d[k][0];
                    int y = c + d[k][1];
                    if(x >= 0 && y >= 0 && x < n && y < n){
                        if(grid[x][y] == 1){
                            return level;
                        }
                        else if(grid[x][y] == 0){
                            grid[x][y] = 2;
                            points.push({x,y});
                        }
                    }
                }
            }
        }
        return 0;
    }
};

分析：先通过任意搜索方法找到其中一个岛屿，然后利用广度优先搜索，查找其与另一个岛屿的最短距离

错误：BFS好久没有练习了，也是生疏了。

Leetcode 126

给定一个起始字符串和一个终止字符串，以及一个单词表，求是否可以将起始字符串每次改一个字符，直到改成终止字符串，且所有中间的修改过程表示的字符串都可以在单词表里找到。若存在，输出需要修改次数最少的所有更改方式。

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string> &wordList) {
        vector<vector<string>> res;
        // 因为需要快速判断扩展出的单词是否在 wordList 里，因此需要将 wordList 存入哈希表，这里命名为「字典」
        unordered_set<string> dict = {wordList.begin(), wordList.end()};
        // 修改以后看一下，如果根本就不在 dict 里面，跳过
        if (dict.find(endWord) == dict.end()) {
            return res;
        }
        // 特殊用例处理
        dict.erase(beginWord);

        // 第 1 步：广度优先搜索建图
        // 记录扩展出的单词是在第几次扩展的时候得到的，key：单词，value：在广度优先搜索的第几层
        unordered_map<string, int> steps = {{beginWord, 0}};
        // 记录了单词是从哪些单词扩展而来，key：单词，value：单词列表，这些单词可以变换到 key ，它们是一对多关系
        unordered_map<string, set<string>> from = {{beginWord, {}}};
        int step = 0;
        bool found = false;
        queue<string> q = queue<string>{{beginWord}};
        int wordLen = beginWord.length();
        while (!q.empty()) {
            step++;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                const string currWord = move(q.front());
                string nextWord = currWord;
                q.pop();
                // 将每一位替换成 26 个小写英文字母
                for (int j = 0; j < wordLen; ++j) {
                    const char origin = nextWord[j];
                    for (char c = 'a'; c <= 'z'; ++c) {
                        nextWord[j] = c;
                        if (steps[nextWord] == step) {
                            from[nextWord].insert(currWord);
                        }
                        if (dict.find(nextWord) == dict.end()) {
                            continue;
                        }
                        // 如果从一个单词扩展出来的单词以前遍历过，距离一定更远，为了避免搜索到已经遍历到，且距离更远的单词，需要将它从 dict 中删除
                        dict.erase(nextWord);
                        // 这一层扩展出的单词进入队列
                        q.push(nextWord);
                        // 记录 nextWord 从 currWord 而来
                        from[nextWord].insert(currWord);
                        // 记录 nextWord 的 step
                        steps[nextWord] = step;
                        if (nextWord == endWord) {
                            found = true;
                        }
                    }
                    nextWord[j] = origin;
                }
            }
            if (found) {
                break;
            }
        }
        // 第 2 步：回溯找到所有解，从 endWord 恢复到 beginWord ，所以每次尝试操作 path 列表的头部
        if (found) {
            vector<string> Path = {endWord};
            backtrack(res, endWord, from, Path);
        }
        return res;
    }

    void backtrack(vector<vector<string>> &res, const string &Node, unordered_map<string, set<string>> &from,
             vector<string> &path) {
        if (from[Node].empty()) {
            res.push_back({path.rbegin(), path.rend()});
            return;
        }
        for (const string &Parent: from[Node]) {
            path.push_back(Parent);
            backtrack(res, Parent, from, path);
            path.pop_back();
        }
    }
};

分析：比较复杂的BFS+回溯法

错误：太复杂暂时还理解不了，慢慢来吧。。。

练习

Leetcode 130

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

class Solution {
public:
    static void DFS(vector<vector<char>>& board,int x,int y,int m,int n){
        if(x < 0 || y < 0 || x >= m || y >= n){
            return;
        }
        if(board[x][y] == 'X' || board[x][y] == 'A'){
            return;
        }
        board[x][y] = 'A';
        DFS(board,x+1,y,m,n);
        DFS(board,x-1,y,m,n);
        DFS(board,x,y-1,m,n);
        DFS(board,x,y+1,m,n);
        return;
    }
    void solve(vector<vector<char>>& board) {
        int m = board.size();
        int n = board[0].size();
        for(int i=0;i<m;++i){
            DFS(board,i,0,m,n);
            DFS(board,i,n-1,m,n);
        }
        for(int i=0;i<n;++i){
            DFS(board,0,i,m,n);
            DFS(board,m-1,i,m,n);
        }
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(board[i][j] == 'A'){
                    board[i][j] = 'O';
                }
                else{
                    board[i][j] = 'X';
                }
            }
        }
        return;
    }
};

分析：也是比较普通的DFS，注意记录是否访问过即可。

一遍AC

Leetcode 257

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

class Solution {
public:
    static void DFS(TreeNode* &root,vector<string> &paths,string temp){
        if(root != nullptr){
            temp += to_string(root->val);
            if(root->left == nullptr && root->right == nullptr){
                paths.push_back(temp);
                return;
            }
            else{
                temp += "->";
                DFS(root->left,paths,temp);
                DFS(root->right,paths,temp);
            }
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> paths;
        DFS(root,paths,"");
        return paths;
    }
};

分析：使用深度优先搜索。在深度优先搜索遍历二叉树时，我们需要考虑当前的节点以及它的孩子节点。如果当前节点不是叶子节点，则在当前的路径末尾添加该节点，并继续递归遍历该节点的每一个孩子节点。如果当前节点是叶子节点，则在当前路径末尾添加该节点后我们就得到了一条从根节点到叶子节点的路径，将该路径加入到答案即可。如此，当遍历完整棵二叉树以后我们就得到了所有从根节点到叶子节点的路径。

错误：陷入回溯法的坑了。

Leetcode 47

给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。

class Solution {
public:
    static void backtracking(vector<int>& nums,vector<vector<int>> &result,int level){
        if(level == nums.size() - 1){
            result.push_back(nums);
            return;
        }
        set<int> st;
        for(int i=level;i<nums.size();++i){
            if(st.find(nums[i]) == st.end()){
                st.insert(nums[i]);
                swap(nums[level],nums[i]);
                backtracking(nums,result,level+1);
                swap(nums[level],nums[i]);
            }
        }
        return;
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> result;
        backtracking(nums,result,0);
        return result;
    }
};

分析：与全排列基本相同，添加一个set用于记录曾经交换过的数字，如果这个数字曾经交换过就不换了

错误：看了网上的思路。

Leetcode 40

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次 。

class Solution {
public:
    static void backtracking(vector<int>& candidates,vector<vector<int>> &result,vector<int> &path,vector<bool> &used,int level,int sum,int target){
        if(sum > target){
            return;
        }
        else if(sum == target){
            result.push_back(path);
            return;
        }
        else{
            for(int i=level;i<candidates.size() && sum + candidates[i] <= target;++i){
                if(i > 0 && candidates[i] == candidates[i-1] && used[i - 1] == false){
                    continue;
                }
                sum += candidates[i];
                path.push_back(candidates[i]);
                used[i] = true;
                backtracking(candidates,result,path,used,i+1,sum,target);
                used[i] = false;
                sum -= candidates[i];
                path.pop_back();
            }
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> path;
        vector<bool> used(candidates.size(),false);
        sort(candidates.begin(),candidates.end());
        backtracking(candidates,result,path,used,0,0,target);
        return result;
    }
};

分析：还是组合数，但是数字内部有重复的，因此需要对同一树层上的“使用过”进行去重。

错误：没什么思路。

Leetcode 37

编写一个程序，通过填充空格来解决数独问题。

class Solution {
public:
    static bool isValid(int i,int j,char k,vector<vector<char>>& board){
        set<char> st;
        for(int x=0;x<9;x++){
            st.insert(board[i][x]);
            st.insert(board[x][j]);
        }
        int p = i / 3;
        int q = j / 3;
        for(int x = p*3;x < p*3+3;++x){
            for(int y = q * 3;y < q*3+3;++y){
                st.insert(board[x][y]);
            }
        }
        if(st.find(k) == st.end()){
            return true;
        }
        return false;
    }
    static bool backtracking(vector<vector<char>>& board){
        for(int i=0;i<9;++i){
            for(int j=0;j<9;++j){
                if(board[i][j] != '.'){
                    continue;
                }
                for(char k = '1';k <= '9';++k){
                    if(isValid(i,j,k,board)){
                        board[i][j] = k;
                        if(backtracking(board) == true){
                            return true;
                        }
                        board[i][j] = '.';
                    }
                }
                return false;
            }
        }
        return true;
    }
    void solveSudoku(vector<vector<char>>& board) {
        bool judge = backtracking(board);
        return;
    }
};

分析：二维的回溯问题，说白了就是去尝试填充每一个数字，合理就填上，不合理就删掉之前填充的重新进行尝试。

错误：看题解。

Leetcode 310

给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        int m = edges.size();
        vector<int> result;
        if(m == 0){
            result.push_back(0);
            return result;
        }
        vector<int> degree(n,0);
        vector<vector<int>> tree(n);
        for(int i=0;i<m;++i){
            ++degree[edges[i][0]];
            ++degree[edges[i][1]];
            tree[edges[i][0]].push_back(edges[i][1]);
            tree[edges[i][1]].push_back(edges[i][0]);
        }
        queue<int> q;
        for(int i=0;i<n;++i){
            if(degree[i] == 1){
                q.push(i);
            }
        }
        while(!q.empty()){
            int size = q.size();
            result.clear();
            for(int i=0;i<size;++i){
                int top = q.front();
                result.push_back(top);
                q.pop();
                --degree[top];
                for(int j=0;j<tree[top].size();++j){
                    --degree[tree[top][j]];
                    if(degree[tree[top][j]] == 1){
                        q.push(tree[top][j]);
                    }
                }
            }
        }
        return result;
    }
};

分析：拓扑排序的思想，从多端同时BFS到中心点，直到到达最后一层，输出这一层的结点即为最小的高度。

错误：看了思路后自己实现，注意判断边界条件。

总结

深度优先、广度优先和回溯法，理解的还是并不是非常深入，今后还要多加练习。