【LeetCode】《LeetCode 101》第六章:搜索

这篇具有很好参考价值的文章主要介绍了【LeetCode】《LeetCode 101》第六章:搜索。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

6.1 算法解释

深度优先搜索广度优先搜索 是两种最常见的优先搜索方法,它们被广泛应用于图和树等结构中搜索。

6.2 深度优先搜索

深度优先搜索(depth-first search,DFS)在搜索到一个新的节点时,立即对该节点进行遍历;因此遍历需要用先入后出的栈实现,也可以用通过与栈等价的递归实现。

对于树结构而言,由于总是对新节点调用遍历,因此看起来向着更“深”的方向前进。

深度优先搜索也可以用来检测环路:记录每个遍历过的节点的父节点,若一个节点被再次遍历且父节点不同,说明有环。

有时可能需要对已经搜索过的节点进行标记,防止在遍历时重复搜索某个节点,这种做法叫做状态记录记忆化

一般来说,深度优先搜索类型的题可以分为主函数辅函数

  • 主函数用于搜索所有的搜索位置,判断是否可以开始搜索,如果可以就在辅函数进行搜索。
  • 辅函数则负责深度优先搜索的递归调用。

当然,也可以使用栈实现深度优先搜索,但因为递归和栈的原理相同,而递归相对容易实现,因此刷题时更推荐递归写法。

不过在实际工程中,栈可能是最好的选择。一是因为便于理解,二是因为不易出现递归栈满的情况。

695. 岛屿的最大面积(中等)

【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索

方法一:栈

  1. 题解

    • 首先遍历 grid 的每一个位置,如果当前格子是陆地(grid[i][j] == 1),那么就对其进行深度优先搜索。
    • 将当前格子修改为 0,这是为了确保之后不会重复遍历该位置。
    • 接着,定义一个,存放陆地格子的坐标。
    • 然后当前位置的坐标入栈,之后开始遍历栈内格子的四个方向,直到栈为空。对于四个方向的遍历,这里设置了一个二维数组,分别对应上下左右四个方向。每确定下一个要遍历的坐标,都需要判断它的边界条件:是否仍在 grid 的合法坐标内,且当前格子为陆地。
    • 每遍历完一次栈,都需要确定当前最大的岛屿面积。
    • 最后,当所有格子都遍历一遍后,返回的 area 就是最大的岛屿面积。
  2. 代码

    class Solution {
    public:
        int maxAreaOfIsland(vector<vector<int>>& grid) {
            // 定义方向数组
            vector<vector<int>> dir{{0,1}, {0,-1}, {1,0}, {-1,0}};
            int m = grid.size(), n = m ? grid[0].size() : 0;
            int local_area , area = 0, x, y;
            for(int i = 0; i < m; ++i){
                for(int j = 0; j < n; ++j){
                    if(grid[i][j]){
                        local_area = 1;
                        grid[i][j] = 0; // 确保不会重复搜索
                        stack<pair<int, int>> island;
                        island.push({i, j});
                        while(!island.empty()){
                            auto [r, c] = island.top();
                            island.pop();
                            for(int k = 0; k < 4; ++k){
                                // 遍历 4 个方向
                                x = r + dir[k][0], y = c + dir[k][1];
                                if(x>=0 && x <= m-1 && y>=0 && y<=n-1 && grid[x][y] == 1){
                                    grid[x][y] = 0;
                                    island.push({x, y});
                                    local_area++;
                                }
                            }
                        }
                        area = max(area, local_area);
                    }
                }
            }
            return area;
        }
    };
    
  3. 收获

    • 思路很简单,需要学习一下模板,可以写起来会快很多。
    • 注意不要忽略 记忆化

方法二:递归的第一种写法

  1. 题解

    • 主函数遍历 grid 的每一个格子,判断是否可以搜索,如果可以的话,就调用辅函数 dfs 进行深度优先搜索;

    • 辅函数 dfs 负责进行深度优先搜索。首先,递归结束的条件是: grid[i][j] == 0,那么不会再增加新的面积,返回 0。

      如果递归不会结束,那么将 grid[i][j] 置为 0,防止重复搜索。

      接着一样遍历该位置的四个方向,进行边界判断以及确定下一个位置是否也是陆地,如果是的话,就对该位置再次进行递归。

  2. 代码

    class Solution {
    public:
        vector<vector<int>> dir{{0,1}, {0,-1}, {1,0}, {-1,0}};
        int maxAreaOfIsland(vector<vector<int>>& grid) {
            int m = grid.size(), n = m ? grid[0].size() : 0;
            int area = 0;
            for(int i = 0; i < m; ++i){
                for(int j = 0; j < n; ++j){
                    if(grid[i][j]){
                        area = max(area, dfs(grid, i, j));
                    }
                }
            }
            return area;
        }
        int dfs(vector<vector<int>>& grid, int i, int j){
            if(grid[i][j] == 0) return 0;
            grid[i][j] = 0;
            int x, y, area = 1;
            for(int k = 0; k < 4; ++k){
                x = i + dir[k][0], y = j + dir[k][1];
                if(x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() && grid[x][y]){
                    area += dfs(grid, x, y);                
                }
            }
            return area;
        }
    };
    

方法三:递归的第二种写法

  1. 题解

    • 这种写法的主函数和第一种写法的主函数一致,不同之处在于辅函数。
    • 辅函数递归结束的条件为:坐标越界 ,或者当前格子不是陆地,那么其面积为 0;
    • 否则,先将该格子置为 0,然后直接对该格子的四个方向调用递归。
  2. 代码

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

547. 省份数量(中等)

【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索

  1. 题解

    • isConnected 每一行(列)代表一个节点,它的每列(行)代表是否存在相邻节点。
    • 这一题中,一共有 n 个节点,每个节点最多拥有 n 条边。因此,设置一个数组 visited,用于标记已经访问过的节点
    • 首先,对每个节点进行遍历,如果该节点 A 未被访问过,那么就对它进行搜索,看是否存在相邻节点。在主函数中能够进行搜索的节点,一定没有在辅函数中进行搜索过,因此能形成自己的一个圈,即 ans++
    • 判断是否存在相邻节点的方法也很简单,搜索该节点(这一行)的每个列,如果当前位置的节点 B 未被访问过,同时,它与节点 A 存在联系,即 isConnected[i][k] == 1,那么说明它们是相邻节点。此时,对节点 B 继续搜索。
  2. 代码

    class Solution {
    public:
        int findCircleNum(vector<vector<int>>& isConnected) {
            int ans = 0;
            int n = isConnected.size();
            vector<bool> visited(n, false); // 标记这个点是否被访问过
            for(int i=0; i<n; ++i){
                if(!visited[i]){
                    dfs(isConnected, i, visited);
                    ans++;
                }
            }
            return ans;
        }
        void dfs(vector<vector<int>>& isConnected, int i, vector<bool>& visited){
            visited[i] = true;
            for(int k=0; k<isConnected.size(); ++k){
                // 该点未被访问过,且两个点之间存在连接
                if(!visited[k] && isConnected[i][k]==1){
                    dfs(isConnected, k, visited);
                }
            }
        }
    };
    
  3. 收获

    • 这道题和上一道题的思路还是有点不一样的,我总以为这类型的题都会像上一题一样,对 1 / 0进行连续成块地搜索。然而,这道题用到了访问数组,思路清晰简单。

417. 太平洋大西洋水流问题(中等)

【LeetCode】《LeetCode 101》第六章:搜索【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索

  1. 思路

    • 虽然题目要求的是满足向下流能到达两个大洋的位置,如果对所有位置进行搜索,那么在不剪枝的情况下复杂度会很高。因此可以反过来想,从两个大洋开始向上流,这样只需要对矩形的四条边进行搜索。搜索完成之后,只需遍历一次矩阵,满足条件的位置即为两个大洋向上流都能到达的位置。
    • 定义两个矩阵 can_reach_pcan_reach_a ,它们分别记录两个大洋能够到达的位置;
    • 接着,按行遍历 heights 的第一列和最后一列,分别对应两个大洋;同理,按列遍历 heights 的第一行和最后一行,以它们作为起点进行搜索。
    • 在搜索过程中(即辅函数 dfs),终止条件是:该位置被标记为 can_reach ,那么说明可以达到这个位置。否则将该位置标记为 can_reach ,然后对它上下左右四个方向进行搜索。
    • 当搜索结束之后,回到主函数,判断同时满足 can_reach_p 和 can_reach_a 的位置,放入到答案数组 ans 并返回。
  2. 代码

    class Solution {
    public:
        vector<vector<int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
            int m = heights.size(), n = heights[0].size();
            vector<vector<bool>> can_reach_p(m, vector<bool>(n, false));
            vector<vector<bool>> can_reach_a(m, vector<bool>(n, false));
    
            vector<vector<int>> ans;
    
            for(int i=0; i<m ;++i){
                dfs(heights, i, 0, can_reach_p);
                dfs(heights, i, n-1, can_reach_a);
            }
            for(int j=0; j<n; ++j){
                dfs(heights, 0, j, can_reach_p);
                dfs(heights, m-1, j, can_reach_a);
            }
            for(int i=0; i<m; ++i){
                for(int j=0; j<n; ++j){
                    if(can_reach_a[i][j] && can_reach_p[i][j]){
                        ans.push_back(vector<int> {i, j});
                    }
                }
            }
            return ans;
        }
        void dfs(vector<vector<int>>& heights, int i, int j, vector<vector<bool>>& can_reach){
            if(can_reach[i][j])   return ;
            can_reach[i][j] = true;
            int x, y;
            for(int k=0; k<4; ++k){
                int x = i + dir[k][0], y = j + dir[k][1];
                if(x >= 0 && x < heights.size() && y >= 0 && y < heights[0].size() && heights[i][j] <= heights[x][y]){
                    dfs(heights, x, y, can_reach);
                }
            }
        }
    };
    
  3. 收获

    • 这道题要反其道而行之,不过总体思路都差不多,从一个点出发,然后一直搜索,直到这条路无法成功再返回上一层。这里用到两个标记数组,遍历时也分成太平洋和大西洋两种情况,方便处理。

总结

  1. 深度优先搜索

    思想:从一个位置出发,沿着一条路一直搜索,直到这条路没办法走通再返回上一层,继续搜索。

    关键在于:

    • 防止重复访问的数组,可以是数组本身,也可以另外设立一个(visited)或多个数组( can_reach_pcan_reach_a );
    • 辅函数 dfs 的返回值:如果只是为了标记访问数组,那么直接在访问数组上操作,返回 void ;如果每一趟搜索需要记录当前的值,那么就需要返回当前的值。
    • 辅函数 dfs 的终止条件:通常是该位置已经被访问过。

6.3 回溯法

回溯法是优先搜索的一种特殊情况,又称为试探法,常用于需要记录节点状态的深度优先搜索。通常来说,排列、组合、选择类问题,使用回溯法比较方便。

回溯法的核心是回溯。在搜索到某一节点的时候,如果我们发现当前节点(及其子节点)不是需求目标,我们回退到原来的节点继续搜索,并且把当前节点修改的状态还原

在具体的写法上,它与普通的深度优先搜索一样,都有 「修改当前节点状态」-> 「递归子节点」的步骤,不过还多了回溯的步骤,变成了「修改当前节点状态」-> 「递归子节点」-> 「回改当前节点状态」。

回溯法有两个诀窍,一是按引用传状态,二是所有的状态修改在递归完成后回改。

回溯法修改一般有两种情况,一种是修改最后一位输出,比如排列组合;一种是修改访问标记,比如矩阵里搜字符串。

46. 全排列(中等)

【LeetCode】《LeetCode 101》第六章:搜索

【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索

  1. 题解
    【LeetCode】《LeetCode 101》第六章:搜索

    • 每一个结点表示了求解全排列问题的不同的阶段,这些阶段通过变量的「不同的值」体现,这些变量的不同的值,称之为「状态」;
    • 在「回头」以后,状态变量需要设置成为和先前一样,因此在回到上一层结点的过程中,需要撤销上一次的选择,这个操作称之为「状态重置」,回改到上一层节点的状态;
    • 首先,这棵树除了根结点和叶子结点以外,每一个结点做的事情其实是一样的,即:在已经选择了一些数的前提下,在剩下的还没有选择的数中,依次选择一个数,这显然是一个递归结构;
    • 递归的终止条件:一个排列中的数字已经选够了,因此定义变量 level 来表示当前已经选择的数字个数。
    • 具体来说,假设我们已经填到第 level 个位置,那么 nums 数组中 [0,level-1]是已填过的数的集合,[level , n -1]是待填的数的集合。我们肯定是用[level ,n-1]里的数去填第 level 个数,假设待填的数的下标为 i,那么填完以后我们将第 i 个数和第 level 个数交换,即能使得在填第 level+1 个数的时候 nums 数组的[0, level] 部分为已填过的数,[level+1,n-1]为待填的数,回溯的时候交换回来即能完成撤销操作
    • 比如,有 [2,5,8,9,10] 这5个数要填入,已经填了 [8,9] 两个数,那么这个数组目前为[8,9 | 2,5,10] 。假设第三个位置要填 10,为了维护数组,将 2 和 10 交换,保证数组继续保持分隔符左边的数已经填过,右边的待填 ,即 [8,9,10 | 2,5];回溯的时候,将 2 和 10 交换回来,就撤销了之前的操作。
  2. 代码

    class Solution {
    public:
        vector<vector<int>> permute(vector<int>& nums) {
            vector<vector<int>> ans;
            backtracking(nums, 0, ans);
            return ans;
        }
        void backtracking(vector<int> &nums, int level, vector<vector<int>> &ans){
            // l 表示当前选了几个数
            if(level == nums.size()){
                ans.push_back(nums);
                return ;
            }
            for(int i=level; i<nums.size(); ++i){
                swap(nums[i], nums[level]); // 修改当前节点状态
                backtracking(nums, level+1, ans); // 递归子节点
                swap(nums[i], nums[level]); // 回改当前节点状态
            }
        }
        
    };
    
  3. 收获

    • 不太熟悉递归和回溯,这类型的题需要多加练习。

77. 组合(中等)

【LeetCode】《LeetCode 101》第六章:搜索

【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索

  1. 思路

    • 和上一道例题类似,对于组合的问题,也可以进行回溯,把当前的数字加入结果中。

    • 首先画出树形结构。可以发现如下递归结构:

      1. 如果组合里有 1,那么需要在[2,3,4] 里再找 1 个数;
      2. 如果组合里有 2,那么需要在[3,4] 里再找 1 个数。注意: 这里不能再考虑1,因为包含1的组合,在第1种情况中已经包含;
      3. 依次类推,以上描述体现的递归结构是:在以n结尾的候选数组里,选出若干个元素。画出递归结构如下图:

      【LeetCode】《LeetCode 101》第六章:搜索

    • 递归的终止条件:当数组元素个数等于题目给出的 k 时,说明已经找到满足题目要求的数组。

    • 否则,从 1 开始进行搜索,先把 1 填入,然后对这个子节点进行递归,下一次填入的数字将会是 2,此时数组为 [1,2],满足终止条件,退回上一步,将 2 弹出,也就是回改当前节点状态。依次类推,直到将所有节点都遍历一遍。

  2. 代码

    class Solution {
    public:
        vector<vector<int>> combine(int n, int k) {
            vector<vector<int>> ans;
            vector<int> nums(k, 0);
            backtracing(n, 1, k, ans, nums, 0);
            return ans;
        }
        void backtracing(int n, int pos, int k, vector<vector<int>>& ans, vector<int>& nums, int count){
            // pos 表示当前位置要放入的数字
            // count 表示当前数组里的元素个数
            if(count == k){
                // 当数组个数已经达到 k
                // 说明已经找到一个符合要求的数组
                ans.push_back(nums);    
                return ;
            }
            for(int i=pos; i<=n; ++i){
                nums[count++] = i; // 修改当前节点状态
                backtracing(n, i+1, k, ans, nums, count); // 递归子节点
                count--; // 回改当前节点状态
            }
        }
    };
    
  3. 收获

    • 上一题是排列问题,所以通过交换位置来修改节点状态;这一题是组合问题,通过将当前数字加入结果来修改节点状态。
    • 将数字加入数组,我最近习惯于用push_back,然而有时候通过下标赋值,或许更方便,因为这样回退的时候只需要将下标 -1。
    • 如果要在子函数中修改主函数的参数,一定记得加上 引用 &

79. 单词搜索(中等)

【LeetCode】《LeetCode 101》第六章:搜索

【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索

  1. 思路

    • 和排列、组合问题不同,这一题修改的是访问标记;在对任意位置进行深度优先搜索的时候,先标记当前位置为已访问,以避免重复遍历(如防止向右搜索后又向左返回);在完成所有可能的搜索后,再回改当前的位置为未访问,防止干扰其他位置搜索到当前位置(因为这道题的搜索结果存在先后关系)。
  2. 代码

    class Solution {
    public:
        // vector<vector<int>> dir{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        bool exist(vector<vector<char>>& board, string word) {
            bool find = false;
            int m = board.size(), n = board[0].size();
            vector<vector<bool>> visited(m, vector<bool>(n, false));
            for(int i=0; i<m; ++i){
                for(int j=0; j<n; ++j){
                    backtracing(i, j, board, word, find, visited, 0);
                }
            }
            return find;
        }
        void backtracing(int i, int j,vector<vector<char>>& board,string word,bool& find,vector<vector<bool>>& visited, int pos){
            if(i<0 || i>=board.size() || j<0 || j>=board[0].size() || visited[i][j] || find || board[i][j] != word[pos])
                return ;
            if(pos == word.size() - 1){
                find = true;
                return ;
            }
            visited[i][j] = true;
            backtracing(i+1, j, board, word, find, visited, pos+1);
            backtracing(i-1, j, board, word, find, visited, pos+1);
            backtracing(i, j+1, board, word, find, visited, pos+1);
            backtracing(i, j-1, board, word, find, visited, pos+1);
            visited[i][j] = false;
        }
    };
    
  3. 收获

    • 这道题 11.18 的时候做过,但是当时不怎么会。
    • 这一道题和深度优先搜索很像,不同的是:深度优先修改了访问标记,防止重复搜索,而这道题是先将访问标记修改为 true,在完成所有可能的搜索后,再将其回改为 false,因为之后有可能再搜索到这个位置

51. N 皇后(困难)

【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索

  1. 题解

    • 这道题也是选择,和上一题一样,设置并修改状态数组,不同的是,上一题设置了一个二维数组记录状态,这一题设置了多个访问数组:行、列、左斜、右,记录它们是否存在皇后。由于本题有一个隐藏条件,即满足条件的结果中每一行或列有且仅有一个皇后,所以如果我们对每一行遍历插入皇后,就不需要对行建立访问数组,因此只需要设置三个访问数组:列、左斜、右斜。
  2. 代码

    class Solution {
    public:
        vector<vector<string>> solveNQueens(int n) {
            vector<vector<string>> ans;
            vector<string> board(n, string(n, '.'));
            // 定义了三个访问数组
            vector<bool> column(n, false), ldiag(2*n-1, false), rdiag(2*n-1, false);
            // 按行遍历
            backtracing(n, ans, board, column, ldiag, rdiag, 0);
            return ans;
        }
        void backtracing(int n, vector<vector<string>>& ans, vector<string>& board, vector<bool>& column, vector<bool>& ldiag, vector<bool>& rdiag, int row){
            // 每次遍历完一遍行 说明得到了一个答案
            if(row == n){
                ans.push_back(board);
                return ;
            }
            // i 表示 column
            for(int i=0; i<n ; ++i){
                if(column[i] || ldiag[n-row+i-1] || rdiag[row+i])   
                    continue;
                // 修改当前状态
                board[row][i] = 'Q';
                column[i] = ldiag[n-row+i-1] = rdiag[row+i] = true;
                // 递归子节点
                backtracing(n, ans, board, column, ldiag, rdiag, row+1);
                // 回改至当前的状态
                board[row][i] = '.';
                column[i] = ldiag[n-row+i-1] = rdiag[row+i] = false;
            }
        }
    };
    
  3. 收获

    • 这道题和上一道题很像,不同的是使用了多个访问数组,和 6.2 的最后一道练习题有异曲同工之妙,它也是在上一题的思路上使用多个数组。
    • 这里对于 ldiag 和 rdiag 的下标,可以通过找规律确定;
    • vector<string> board(n, string(n, '.')) ,感觉类似于二维的字符串数组,一个字符串里嵌套 n 个字符串。
    • 辅函数 backtracing 的终止条件是: n == row ,即遍历了所有行就得到一种答案。因为是递归,最后会回到 row=0, i=0 开始第二轮的遍历(找下一个可能的结果)。

总结

  1. 回溯法辅函数 backtracing() ,通常都是返回 void ,直接调用主函数的引用对数组进行修改。核心思想由三个步骤组成:「修改当前节点状态、递归子节点、回改当前节点状态」。

  2. 分为 排列组合选择三种题型:

    • 排列:回溯的是交换位置 [题 46];
    • 组合:回溯的是 是否把当前的数字加入结果 [题 77];
    • 选择:修改访问标记,访问数组既可以是单个[题 79],也可以是多个[题 51]。

6.4 广度优先搜索

广度优先搜索(BFS),一层层进行遍历,因此需要使用先入先出的队列。由于是按层次进行遍历的,广度优先搜索时按照“广”的方向进行遍历,也常常用来处理最短路径问题。

934.最短的桥(中等)

【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索

  1. 思路

    • 由于 0 代表水域,1 代表陆地,要区分两个岛屿,所以,在遍历 grid 矩阵的时候,只要第一次发现了某个格子为 1,则将发现的新大陆进行编号,即:将 1 变为 2

    • 首先通过 DFS 的方式寻找第一个岛屿

      • 在深度遍历的过程中,如果我们发现了某个格子为 0,则说明已经遍历到了岛屿的边缘部分,将其放入到队列 points 中,points 中保存着 int 数组,队列中的每个数组长度都是2,即: int[0]保存行,int[1] 保存列。
      • 如果发现某个格子为 1 ,说明该格子是岛屿的一部分,那么继续向它的四个方向递归遍历,确保能找到完整的第一个岛屿;
      • 如果某个格子为 2,说明这个格子已经遍历过了,由于我们使用了 DFS ,意味着该格子的四个方向肯定也递归过了,因此该递归结束,回到上一层递归;
    • 在找到第一个岛屿后,我们使用 BFS,查询其与第二个岛屿之间的距离。由于队列中保存了第一个岛屿的所有“边缘格子”,那么接下来就需要开启 while 循环,对外进行一层的岛屿扩充操作。遍历每个“边缘格子”,再分别从上/下/右/左,四个方向去查看相邻的格子。

      • 如果发现是 0,则表明是新的一层边缘格子,将其赋值为 2,并将其加入到队列中,用于下一次while循环。
      • 如果发现是 1,说明已经与另一个岛屿接壤了,返回扩展层数即可。
      • 如果发现是 2 ,说明遍历到第一个岛屿了,直接遍历下一个位置。
  2. 代码

    class Solution {
    public:
        int shortestBridge(vector<vector<int>>& grid) {
            int m = grid.size(), n = grid[0].size();
            vector<vector<int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
            queue<pair<int, int>> points;
            bool flipped = false;
            for(int i=0; i<m; ++i){
                if(flipped) break;
                for(int j=0; j<n; ++j){
                    // 使用dfs 将1均变成2
                    if(grid[i][j] == 1){
                        dfs(points, grid, i, j);
                        flipped = true;
                        break;
                    }
                }
            }
    
            // 使用bfs寻找第二个岛屿
            int x, y;
            int level = 0;
            while(!points.empty()){
                ++ level;
                int n_points = points.size();
                while(n_points--){
                    auto [r, c] = points.front();
                    points.pop();
                    for(int k=0; k<4; ++k){
                        x = r + dir[k][0], y = c + dir[k][1];
                        if(x>=0 && x<m && y>=0 && y<n){
                            if(grid[x][y] == 1){
                                return level;
                            }
                            else if(grid[x][y] == 0){
                                grid[x][y] = 2;
                                points.push({x, y});
                            }
                            else if(grid[x][y] == 2){
                                continue;
                            }
                        }
                    }
                }
            }
            return 0;
        }
        void dfs(queue<pair<int, int>>& points, vector<vector<int>>& grid, int i, int j){
            if(i<0 || i>=grid.size() || j<0 || j>=grid[0].size() || grid[i][j]==2)
                return ;
            // 如果遇到0,说明可能是路径之一 保存用于之后的遍历
            if(grid[i][j] == 0){
                points.push({i, j});
                return ;
            }
            grid[i][j] = 2;
            dfs(points, grid, i+1, j);
            dfs(points, grid, i-1, j);
            dfs(points, grid, i, j+1);
            dfs(points, grid, i, j-1);
        }
    };
    
    
  3. 收获

    • 广度优先遍历理解起来不难,队列的操作和栈也有些类似,不过队列的第一个元素是 queue.front() 。这道题思路也比较难,先用了 DFS 查找第一个岛屿,使用 BFS 查找第二个岛屿与第一个岛屿的最短距离。

126. 单词接龙 II(困难)

【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索

  1. 题解

    • 我们可以把初始字符串、终止字符串、以及单词表中所有的字符串都想象成节点。如果两个字符串只有一个字符不同,那么它们相连。因为题目要求输出修改次数最少的所有修改方式,因此使用 BFS ,求得起始节点到终止节点的最短距离。
    • 同时使用了一个小技巧:双向搜索 。并不是直接从起始节点进行BFS ,而是每轮遍历都从起始节点和终点节点的单词列表中,选择较少单词的列表进行BFS,这样可以减少搜索的总节点数。
    • 搜索过程的具体思想见代码注释。
    • 在搜索结束后,需要通过回溯,重建所有可能的最短路径。
  2. 代码

    class Solution {
    public:
        vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
            vector<vector<string>> ans;
            // 因为需要快速判断扩展的单词是否出现在WordList中 
            // 因此使用哈希表提高效率
            unordered_set<string> dict;
            dict.insert(wordList.begin(), wordList.end());
            // 判断 endWord 是否出现在哈希表
            if(!dict.count(endWord))    return ans;
            // 特殊用例处理 
            // 确保beginWord不在wordList - 题目要求
            // 确保endWord不在WordList - 否则对于以下用例会重复输出答案
            // "a" "c" ["a","b","c"]
            dict.erase(beginWord);
            dict.erase(endWord);
            // 开始进行 BFS
            // 定义两个无序集合 分别保存从beginWord/endWord出发变换的字符串列表
            unordered_set<string> q1{beginWord}, q2{endWord};
            // <key:当前字符串, 由key可以变换的单词列表>
            unordered_map<string, vector<string>> next;
            // reversed=false:从beginWord出发变换
            // reversed=true:从endWord出发变换 
            bool reversed=false, found=false;
            while(!q1.empty()){
                //  q 保存 当前的单词可以变换到的单词列表
                unordered_set<string> q;
                for(const auto &w : q1){
                    // 将当前单词保存在 w
                    // 对 s 的每一位替换成26位的小写字母 
                    string s = w;
                    for(int i=0; i<s.size(); ++i){
                        // 保存要修改的字符 用于后续恢复
                        char ch = s[i];
                        for(int j=0; j<26; ++j){
                            s[i] = j + 'a';
                            if(q2.count(s)){
                                // 如果q2出现了s 说明此时已经变换到endWord
                                // reversed=true:说明从后往前,因此是将w插入到s的单词列表(反向操作)
                                // reversed=false:从前往后,因此是将s(变换后)插入到w(未变化)的单词列表
                                reversed? next[s].push_back(w) : next[w].push_back(s);
                                found = true;
                            }
                            if(dict.count(s)){
                                // 如果dict出现s 说明变换后的单词在WordList中
                                reversed? next[s].push_back(w) : next[w].push_back(s);
                                // 将其加入到q 用于后续遍历
                                q.insert(s);
                            }
                        }
                        s[i] = ch; // 恢复该字符 遍历下一种可能的情况
                    }
                }
                if(found)   break;
                // 要保证最短 因此单词不可以重复出现
                // 删除WordList中已经出现过的单词
                for(const auto &w : q){
                    dict.erase(w);
                }
                // 如果 q 的单词比 q2 少
                // 那么应该遍历 q
                if(q.size() <= q2.size()){
                    q1 = q;
                }else{
                    // 如果 q2 的单词少 则遍历 q2
                    // 需要颠倒顺序
                    reversed = !reversed;
                    q1 = q2; 
                    q2 = q; 
                }
            }
            if(found){
                // 如果能够找到 那么回溯 重建这条最短路径
                vector<string> path = {beginWord};
                backtracking(beginWord, endWord, next, path, ans);
            }
            return ans;
        }
        void backtracking(const string& beginWord,const string& endWord, unordered_map<string, vector<string>>& next, vector<string>& path, vector<vector<string>> &ans){
            if(beginWord == endWord){
                ans.push_back(path);
                return ;
            }
            for(const auto &s : next[beginWord]){
                // 修改当前节点状态
                path.push_back(s);
                // 回溯子节点
                backtracking(s, endWord, next, path, ans);
                // 回改当前节点状态
                path.pop_back();
            }
        }
    };
    
  3. 收获

    • 这道题很难,看了题解勉强看懂。不过这道题有一个 bug,由于LeetCode修改了样例,导致该题解会超时,不过先把这道题的思想理清楚即可。

6.5 练习

130. 被围绕的区域(中等)

【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索

  1. 题解

    • 由于边界的 ‘O’ 肯定不会填充为 ‘X’ ,因此可以从边界的 ‘O’ 出发,对于可以到达的 ‘O’ ,说明它与边界的 ‘O’ 相连 ,不可能被 ‘X’ 全包围,此时将遍历到的 ‘O’ 修改为 ‘#’ ;
    • 因此,对数组 board 的四条边进行遍历,如果该格子为 ‘O’,那么就对它进行 DFS ,遇到的所有 ‘O’ 都修改成 ‘#’ ,没有被修改的 ‘O’ 说明被 ‘X’ 全包围;
    • 遍历结束后,将 board 中的 ‘#’ 修改为 ‘O’ ,将 ‘O’ 修改为 ‘X’
  2. 代码

    class Solution {
    public:
        void solve(vector<vector<char>>& board) {
            int m = board.size(), n = board[0].size();
            for(int i=0; i<m; ++i){
                if(board[i][0] == 'O')  dfs(board, i, 0);
                if(board[i][n-1] == 'O')    dfs(board, i, n-1);
    
            }
            for(int j=0; j<n; ++j){
                if(board[0][j] == 'O')  dfs(board, 0, j);
                if(board[m-1][j] == 'O')  dfs(board, m-1, j);
            }
            for(int i=0; i<m; ++i){
                for(int j=0; j<n; ++j){
                    if(board[i][j] == 'O')  board[i][j] = 'X';
                    else if(board[i][j] == '#') board[i][j] = 'O';
                }
            }
        }
        void dfs(vector<vector<char>>& board, int i, int j){
            if(i<0 || i>=board.size() || j<0 || j>=board[0].size() || board[i][j]== 'X' || board[i][j] == '#')  return ;
            board[i][j] = '#';
            // visited[i][j] = true;
            dfs(board, i+1, j);
            dfs(board, i-1, j);
            dfs(board, i, j+1);
            dfs(board, i, j-1);
            // return false;
        }
    };
    
  3. 收获

    • 这道题没抓住重点,我是从中心(非边界)开始遍历,如果格子 ‘O’ 的四周都是 ‘X’ ,那么可以将其修改为 ‘X’ 。但是很难实现,因此浪费了很多时间。看了一眼题解后,很快做出来了,说明我掌握了搜索的算法,但是没办法将其应用到实际中。
    • 此外,我一开始还设置了一个访问数组防止重复搜索,然后题解中直接用 board[i][j] == '#' 代替访问数组,确实可行,而且不会额外占用内存。

257. 二叉树的所有路径(简单)

【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索

  1. 题解

    • 这道题思路很简单,就是对根节点调用 DFS ,如果搜索到的节点不为空,那么就将它的值放入路径 path ,继续判断它是否存在子节点:如果不存在,说明已经找到一条路径,存入答案数组;存在的话继续递归子节点。
  2. 代码

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
    public:
        vector<string> binaryTreePaths(TreeNode* root) {
            vector<string> ans;
            dfs(root, ans, "");
            return ans;
        }   
        void dfs(TreeNode* root, vector<string>& ans, string path){
            if(root != nullptr){
                path += to_string(root->val);
                if(root ->left == nullptr && root -> right == nullptr){
                    ans.push_back(path);
                }else{
                    path += "->";
                    dfs(root->left, ans, path);
                    dfs(root->right, ans, path);
                }
            }
        }
    };
    
  3. 收获

    • 这道题思路不难,用的是最基本的 DFS 模板,但是我对于 《题目给出结构体》 这类型的题不熟悉,不知道如何使用。
    • 这道题出错的地方:
      • path 一开始定义为 vector<string> ,难怪 ans.push_back(path) 出错;
      • path 不应该加上 引用 & ,因为加上引用的话,会不断修改它,我们在对根节点右子树进行遍历的时候,只希望 path 中有 根节点。

47. 全排列 II(中等)

【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索

  1. 思路

    • 这道题是 46.全排列 的升级版,多了一个条件:「序列包含重复数字」。因此,相比于 46 ,可能会出现重复结果。

    • 一开始我想用 set 去重,但是发现不是是很方便。所以,我们在遍历的时候,可以对重复结果进行剪枝。如图所示,显然,对于序列 [1,1*,2] ,如果第一个 1 已经放入在第一个位置上,那么对于 1* 来说,如果再放在第一个位置, 那么肯定和前一种情况重复,因此需要去除。

    • 因此,如果第一个 1 已经使用,那么我们就不再考虑同一位置上的 1* 的情况。设置条件为 : if(i>0 && nums[i] == nums[i-1] && !vis[i-1]) continue;

    • 这里,为了方便考虑重复数字,我们再遍历之前应该对数组进行排序,保证相同数字相邻。这里有一个问题,因为我代码使用了 swap 交换两个数字的位置,而每次backtracking 后,swap 都会将 nums变回 backtracking 之前的顺序,因此在回溯的时候,每次都需要对 nums 重新排序

      【LeetCode】《LeetCode 101》第六章:搜索

  2. 代码

    class Solution {
    public:
        vector<vector<int>> permuteUnique(vector<int>& nums) {
            vector<vector<int>> ans;
            vector<bool> vis(nums.size(), false);
            backtracking(nums, ans, 0, vis);
            return ans;
        }
        void backtracking(vector<int>& nums, vector<vector<int>>& ans, int level, vector<bool>& vis){
            if(level == nums.size()){
                ans.push_back(nums);
                return ;
            }
            for(int i=level; i<nums.size(); ++i){
                // swap之后可能无序 所以需要重新排序
                sort(nums.begin() + level, nums.end());
                // 剪枝 
                if(i>0 && nums[i] == nums[i-1] && !vis[i-1])  continue;
                vis[i] = true; // 修改当前状态
                swap(nums[i], nums[level]);
                backtracking(nums, ans, level+1, vis); // 递归子节点
                vis[i] = false; // 回改当前状态
                swap(nums[i], nums[level]);
            }
        }
    };
    
  3. 收获

    • 这道题做了特别久,可能和今天状态不好也有关系,其实整体思路并不难,但是我没有考虑到swap 都会将 nums变回 backtracking 之前的顺序,导致有一个实例一直没办法通过。 错误实例及原因分析

40. 组合总和 II(中等)

【LeetCode】《LeetCode 101》第六章:搜索

【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索

  1. 题解

    • 这道题的思路结合了 77 和 47 ,首先依照 77 的算法思想,完成组合排列,接着利用 47 去重的思想,去除重复组合。
    • 对于不出现重复序列的题目,一般都需要排序,便于去重。
    • 组合排列:设定一个值 sum ,用于保存当前数组元素之和,当 sum == target ,说明我们已经找到一个符合要求的数组,存入 ans;如果 sum > target ,由于我们的数组是升序排列,那么后续元素肯定比当前元素大,因此该情况一定不可能,此时回退到上一个状态;如果 sum < target ,那么进入循环,取下一个元素继续判断。
    • 在选择元素的时候,需要注意需要保存当前元素的下标 pos,递归该节点的时候,应该从当前元素的下一个元素开始考虑,才不会出现一直使用同一元素的情况。
    • 去重 思想参考上一道题,思路完全一致。
  2. 代码

    class Solution {
    public:
        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
            vector<vector<int>> ans;
            vector<bool> visit(candidates.size(), false);
            vector<int> option;
            sort(candidates.begin(), candidates.end());
            backtracking(candidates, ans, target, 0, option, 0, visit);
            return ans;
        }
        void backtracking(vector<int> &candidates, vector<vector<int>> &ans, int target, int sum, vector<int> option, int pos, vector<bool> &visit){
            if(sum == target){
                ans.push_back(option);
                return ;
            }
            else if(sum > target){
                return ;
            }
            for(int i=pos; i<candidates.size(); ++i){
                // 剪枝
                if(i>0 && candidates[i] == candidates[i-1] && !visit[i-1])  continue;
                // 修改当前状态
                visit[i] = true;
                sum += candidates[i];
                option.push_back(candidates[i]);
                // 递归子节点
                backtracking(candidates, ans, target, sum, option, i+1, visit);
                // 回改当前状态
                visit[i] = false;
                sum -= candidates[i];
                option.pop_back();
            }
    
        }
    };
    
  3. 收获

    • 昨天在去重的思路上卡了很久,不过总算有收获,今天很快就自己做出来了!

37. 解数独(困难)

【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索

  1. 思路

    • 为了防止数字冲突,设置了三个访问数组对已经使用的数字进行标记,分别是行、列 和 3*3 格子。
    • 首先,遍历 board ,如果当前元素是数字,那么修改对应的访问数组;如果当前元素是 ‘.’ ,说明之后需要修改这个位置,把它放入 spaces ;
    • 接着,递归 spaces 的每一个元素, 设置 pos 标记当前遍历到的元素下标;
    • 如果 pos == spaces.size() ,说明我们已经对所有 ‘.’ 进行了修改,将 valid 置为 true ,结束递归;
    • 否则,对每个 ‘.’ 进行修改。考虑在该位置上填入 1 - 9,当且仅当 valid = false ,且该数字在三个访问数组中都为 false,那么可以填入,此时需要将该数字填入 board ,同时修改访问数组的状态; 然后递归子节点,回溯的时候需要回改当前状态,不过这里不需要将填入的数字改回 ‘.’ ,因为该位置注定要填入一个数字的,所以无需修改回去。
  2. 代码

    class Solution {
    public:
        bool valid = false;
        void solveSudoku(vector<vector<char>>& board) {
            // 三个访问数组,分别对应于行、列、3*3
            vector<vector<bool>> txt(9, vector<bool>(9, false));
            vector<vector<bool>> row(9, vector<bool>(9, false));
            vector<vector<bool>> col(9, vector<bool>(9, false));
            // 记录需要填入的位置坐标
            vector<pair<int, int>> spaces;
            for(int i=0; i<9; ++i){
                for(int j=0; j<9; ++j){
                    if(board[i][j] != '.'){
                        // 对已有数字进行标记 防止重复
                        row[i][board[i][j] - '1'] = true;
                        col[j][board[i][j] - '1'] = true;
                        txt[(i / 3) * 3 + (j / 3)][board[i][j] - '1'] = true;
                    }
                    else{
                        // 记录需要填入的位置坐标
                        spaces.push_back({i, j});
                    }
                }
            }
            backtracking(board, 0, row, col, txt, spaces);
        }
        void backtracking(vector<vector<char>>& board, int pos, vector<vector<bool>> &row, vector<vector<bool>> &col, vector<vector<bool>> &txt, vector<pair<int, int>> &spaces){
            // pos 表示当前遍历到 spaces的元素下标
            // 递归结束的条件
            if(pos == spaces.size()){
                // 说明每个需要填入的位置都已经遍历了
                valid = true;
                return ;
            }
            auto [i, j] = spaces[pos];
            for(int k=0; k<9; ++k){
                if(!valid && !row[i][k] && !col[j][k] && !txt[(i / 3) * 3 + (j / 3)][k]){
                    // 说明这个数字还没被使用
                    // 修改当前节点的状态
                    board[i][j] = k + '0' + 1;
                    row[i][k] = col[j][k] = txt[(i / 3) * 3 + (j / 3)][k] = true;
                    // 递归子节点
                    backtracking(board, pos+1, row, col, txt, spaces);
                    // 不需要再改回"."
                    // 回改当前状态
                    row[i][k] = col[j][k] = txt[(i / 3) * 3 + (j / 3)][k] = false;
                }            
            }
        }
    };
    
  3. 收获

    • 这道题思路不难,对应于回溯题的 N 皇后 ,需要设置多个访问数组。不过我没想到设置 spaces 来保存需要修改的位置,因此没想到递归的结束条件。

310. 最小高度树(中等)

【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索

  1. 思路

    • 这道题是求的是树的最小高度,一般用 BFS 求解。通过画图,可以发现,越靠近里面的节点越有可能是最小高度树的根节点。因此,我们可以从叶子节点(度=1)出发,每一次遍历都剥掉最外层的叶子节点,最后剩下的叶子节点就是最小高度树的根节点。
    • 首先使用邻接表存储树,使用一维数组存储每个节点的
    • 接着,将度为1的节点,即叶子节点,入队
    • 然后对队列中的每一个元素使用 BFS,直到队列为空,此时 ans 保存的就是最后状态的叶子节点,也就是最小高树的根节点。注意,由于 ans 会保存每轮的叶子节点,因此每次进行下一轮搜索的时候,需要将 ans 清空。
  2. 代码

    class Solution {
    public:
        vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
            if(n==1) return {0};
            vector<vector<int>> m(n); // 邻接表
            vector<int> degree(n, 0);
            vector<int> ans;
            // 保存邻接矩阵和度
            for(int i=0; i<edges.size(); ++i){
                int u = edges[i][0], v = edges[i][1];
                ++degree[u];++degree[v];
                m[u].push_back(v);
                m[v].push_back(u);
            }
            queue<int> q;
            // 叶子节点入队
            for(int i=0; i<n; ++i){
                if(degree[i] == 1)  q.push(i);
            }
            // 一层层从外往内剥,剩下的叶子节点就是根节点
            while(!q.empty()){
                // ans 会保存最后状态下的叶子节点
                ans.clear();
                int q_size = q.size();
                for(int i=0; i<q_size; ++i){
                    int t = q.front();
                    q.pop();
                    ans.push_back(t);
                    for(auto j : m[t]){
                        // 由于剥掉了外层 因此它的度-1
                        degree[j] --;
                        // 如果当前节点是叶子节点 入队
                        if(degree[j] == 1)  q.push(j);
                    }
                }
            }
            return ans;
        }
    };
    
  3. 收获

    • 对于树的存储方式(邻接表) 和度,我有想到。不过,“先将叶子节点入队, 然后一层层向内剥” ,这个思路我没有想到,而且 BFS 相对不够熟悉。

17. 电话号码的字母组合(中等)

【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索

思路及代码: 17. 电话号码的字母组合

679. 24 点游戏(困难)

【LeetCode】《LeetCode 101》第六章:搜索
【LeetCode】《LeetCode 101》第六章:搜索

679. 24 点游戏文章来源地址https://www.toymoban.com/news/detail-407786.html

到了这里,关于【LeetCode】《LeetCode 101》第六章:搜索的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 第六章.决策树(Decision Tree)—CART算法

    第六章.决策树(Decision Tree) CART决策树的生成就是递归地构建二叉决策树的过程。 CART用基尼(Gini)系数最小化准则来进行特征选择,生成二叉树 。 1).题干: 分别计算它们的Gini系数增益,取Gini系数增益值最大的属性作为决策树的根节点属性。 2).计算 ①. 根节点的Gini系数: ②

    2024年01月17日
    浏览(49)
  • 数据结构与算法分析 第六章 图 作业讲解

     参考教材: 《数据结构(C语言版 第2版)》 严蔚敏,李冬梅,吴伟民编著,人民邮电出版社,2022年版。 截图未标明出处均为原创或取自《数据结构(C语言版 第2版)》~   本文对应的作业题讲解视频:   数据结构与算法分析作业讲解视频合集 https://www.bilibili.com/video/BV1N

    2024年02月03日
    浏览(45)
  • 算法设计与分析复习笔记第六章分支限界法

    分支限界法的基本思想 分支限界法类似于回溯法,也是一种在问题的解空间树T中搜索问题解的算法。 但在一般情况下,分枝限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分枝限界法的求解目标则是找出满足约束条件的一个

    2024年02月03日
    浏览(47)
  • 蓝桥杯算法竞赛系列第六章——蓝桥必备篇之模拟、思维

    欢迎回到: 遇见蓝桥遇见你,不负代码不负卿! 目录 一、简单模拟 栗子:换酒问题 栗子:按奇偶排序数组 栗子:害死人不偿命的(3n+1)猜想 栗子:挖掘机技术哪家强 二、查找元素 栗子:找 x 三、图形输出 栗子:跟奥巴马一起编程 四、日期处理 栗子:日期差值 五、进

    2023年04月22日
    浏览(51)
  • 第23天-代码随想录刷题训练-第六章 ● 669. 修剪二叉搜索树 ● 108.将有序数组转换为二叉搜索树 ● 538.把二叉搜索树转换为累加树

    - LeetCode 链接 给你二叉搜索树的根节点 root ,同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树,使得所有节点的值在[low, high]中。 修剪树不应该改变保留在树中的元素的相对结构 (即,如果没有被移除,原有的父代子代关系都应当保留)。 可以证明,存在唯一的答案

    2024年02月05日
    浏览(37)
  • leetcode(矩阵)74. 搜索二维矩阵(C++详细解释)DAY7

    给你一个满足下述两条属性的 m x n 整数矩阵: 每行中的整数从左到右按非严格递增顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回 false 。 m == matrix.length n == matrix[i].length 1 = m, n = 100 -10^ 4 = matrix

    2024年02月19日
    浏览(35)
  • DFS(深度优先搜索)详解(概念讲解,图片辅助,例题解释,剪枝技巧)

    目录 那年深夏 引入 1.什么是深度优先搜索(DFS)? 2.什么是栈? 3.什么是递归? 图解过程  问题示例 1、全排列问题 2、迷宫问题 3、棋盘问题(N皇后)  4、加法分解 模板 剪枝 1.简介 2.剪枝的原则   3.剪枝策略的寻找的方法 4.常见剪枝方法 最后 他终于抬起头,眨了眨眼睛

    2023年04月08日
    浏览(38)
  • 算法训练day15Leetcode102二叉树层序遍历226翻转二叉树101对称二叉树

    https://www.bilibili.com/video/BV1ue4y1Y7Mf/?vd_source=8272bd48fee17396a4a1746c256ab0ae 层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。 需要借用一个辅助数据结构即队列来实现,队列先进先出,符合一层一层遍历的逻辑,而用栈先

    2024年01月18日
    浏览(53)
  • LeetCode-200. 岛屿数量【深度优先搜索 广度优先搜索 并查集 数组 矩阵】

    给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。 岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外,你可以假设该网格的四条边均被水包围。 示例 1: 输入:grid = [ [“1”,“1”,“1”,“

    2024年04月14日
    浏览(38)
  • 第六章 集合引用类型

    6.1 Object         到目前为止,大多数引用值的示例使用的是Object类型。Object是ECMAScript中最常用的类型之一。虽然Object的实例没有多少功能,但很适合存储和在应用程序间交换数据。         显式地创建Object的实例有两种方式。第一种是使用new操作符和Object构造函数,

    2024年01月18日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包