算法集训营｜「LeetCamp 算法集训营」搜索专题 周常总结Week 4
微扰理论
1476
2021.08.04
2021.08.05
发布于 未知归属地
算法集训营技术交流

简介

大家好，我是负责「LeetCamp算法训练营」的 Leetor，本总结会对本周 (2021.07.26 - 2021.08.01)「学习计划」中面试常考的知识点和同学们的常见问题进行总结。大家如果有问题可以指出来，我会及时修改。本周的主题是搜索。

搜索

搜索可以说是算法面试中最常见的问题了。如果碰到没有思路的时候我们往往也可以通过搜索算法得到一个暴力但正确的解法。一般我们有两类搜索算法，分别是深度优先搜索和广度优先搜索。算法训练营的老师有总结两类算法特性如下，贴给大家以供参考。

广度优先搜索深度优先搜索
实现难度大小
空间消耗大小
需要考虑递归层数否是
针对某些特定问题适用不适用

5-sum

我们先来看第一题，5-sum。 相信许多同学都已经做过2-sum，3-sum，4-sum了，这在之前的双指针专题里我们也讲过。 那么很自然的，我们会想如果要做 5-sum，6-sum 乃至 n-sum，应该怎么解决呢？ 当然我们可以采用之前的类似方法，增加遍历的层数来解决。但会不会有更通用的做法呢？ 这时候搜索算法就有用武之地啦。 限于不是每个读者都报名了本期集训营，且这道题目前不在公开的题目范围内，我们贴一下题目内容。

image.png

既然提到搜索，那我们肯定要考虑清楚我们搜索的到底是什么？一种自然而然的想法就是我们遍历数组中取5个数的所有情况，看看每个情况是否满足和等于 target，这很明显就是一个组合问题啦。 那么有了思路，我们具体要怎么实现呢，DFS 为我们提供了非常好的武器。我们在 DFS 中去试探每个数字取或者不取，并标记到当前遍历的位置，我们一共取了多少个数。如果取的数正好为5，那么我们就去判断是否和满足条件了。翻译成代码如下。
注意为了减少遍历的空间大小，我们会做一些“剪枝”的操作，这也是搜索面试的关键要点。 比如下面的代码中，我们做了两个剪枝：

  1. 如果发现剩下的数全取也已经不够5个了，我们可以提前返回。
  2. 如果发现还没取到5个数，但是和已经超过目标值了，我们也可以提前返回。

复杂度虽然没有数量级的变化（要精确计算和证明是一件不简单的事情），但依旧可以让代码跑的快很多，可能原本超时的解法就不会超时了哦。感兴趣的同学可以自己去跑跑看到底两者差距有多大～

class Solution {
public:
    vector<int> nums;
    int target;

    bool dfs(int idx,int take,int sum){
        if(idx==nums.size()){
            if(sum==target&&take==5)
                return true;
            return false;
        }
        if(take==5)
            return sum==target;
        if(take+nums.size()-idx<5||sum>target)
            return false;
        return dfs(idx+1,take+1,sum+nums[idx])||dfs(idx+1,take,sum);
    }

    bool five_sum(vector<int>& nums, int target) {
        this->nums=nums;
        this->target=target;
        return dfs(0,0,0);
    }
};

作者：力扣 (LeetCode)
链接：https://leetcode.cn/leetbook/read/leetcamp/r65212/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

我们再来看看同学们关于这道题的问题。

image.png

第一个问题 有同学没有特别理解这个递归的写法。 其实这只是一个简写代码的技巧，因为我们知道c++在编译执行逻辑或语句的时候并不会真的对每个求或的表达式进行求值，而是求出第一个为真的值就返回真了。 当然实际的过程其实比这个过程要复杂不少，总而言之大致等同于下面的代码。

if (!dfs(xx1)) {return dfs(xx2);} else {return true;}

大家对递归不是很熟的时候应该尽量不用把递归的分支写在一行里哦。

image.png
image.png
第二个问题是关于剪枝的，首先表扬一下同学，想到额外补充一些可以被剪枝的场景。我看代码理解这两个剪枝的目的，一个是因为排序之后之后的数字都会比当前的值大，所以如果之后的数字都按照当前的值来取已经超过目标值了就肯定不行，另一个是因为之后最大的数字就是最后一个数字，如果都按最大的数字取也达不到目标值，那肯定也不行。从道理上来说这个肯定是可以的哦，不过这个代码里是有问题的。 大家感兴趣的可以自己找找看，哈哈哈，这里就不展开说了～

还有同学询问了关于剪枝后的复杂度问题，这道题的复杂度要证明出来其实并不简单，但我们可以对他缩放一下，画一画递归树，其实我们不难发现复杂度会接近于每个数取或不取的搜索空间遍历的复杂度。而这很显然是 2^n,由于有剪枝，我们的实际复杂度应该是比 2^n 要快不少的。如果为了准备面试，没有必要太纠结具体的证明哦。

封闭岛屿

题目意思很简单，就是我们需要寻找不和边界相连的岛屿数量，也就是 0 的连通分量。
一种我非常欣赏的简化处理方式就是我们先将和大陆，也就是边界相连的陆地全部标为 1，他们对我们求孤岛来说并没有任何区别，将他们视作大海是完全没有问题的，而这会大大简化我们的思考负担。将边界的陆地连通分量都置为 1 之后，我们只需要去数害有多少个1的连通分量即可。比较高级的写法可以用并差集来做。
而本周的主题是搜索，我们还是来讲搜索怎么做。这个题用 DFS 和 BFS 都是可以的，我们只需要遍历每个位置，如果是陆地的话就从该位置开始进行 DFS 或者 BFS，扩张所有相邻的陆地，将访问过的节点置为 1.这样每个连通分量只会在一次 BFS 或者 DFS 的过程中被遍历到。
大家可以参考我的写法:

class Solution {
public:
    int m;
    int n;

    int closedIsland(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        int ans = 0;

        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 0 && !dfs(grid, i, j)) ans++;
            }
        }

        return ans;
    }

    bool dfs(vector<vector<int>>& grid, int i, int j) {
        if (i < 0 || j < 0 || i >= m || j >= n) return true;
        if (grid[i][j] == 1) return false;
        grid[i][j] = 1;

        bool b1 = dfs(grid, i - 1, j);
        bool b2 = dfs(grid, i + 1, j);
        bool b3 = dfs(grid, i, j - 1);
        bool b4 = dfs(grid, i, j + 1);

        return b1 || b2 || b3 || b4;
    }

};

作者：wfnuser
链接：https://leetcode.cn/problems/number-of-closed-islands/solution/dfsyi-ci-bian-li-c-by-wfnuser-7a6u/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

然后我们看看同学的问题。

image.png

这里的思路和我的写法其实是比较相近的，不用返回值，就需要将一个标记位作为参数传入。同学在这里犯的错误就是，应该要传递引用，否则参数会被拷贝一份，并达不到用 flag 标记状态的效果，原有的 flag 将一直保持原状。

同样这题可以用 BFS 实现。给出一个别人的实现供大家参考。

class Solution {
public:
    int closedIsland(vector<vector<int>>& grid) {
        int ret = 0;
        int ylen = grid.size();
        int xlen = grid[0].size();
        for (int i = 0; i < ylen; i++) {
            for (int j = 0; j < xlen; j++) {
                if (i == 0 || j == 0 || i == ylen-1 || j == xlen-1) {
                    bfs(j, i, grid);
                    //或者dfs(j, i, grid);
                }
            }
        }
        for (int i = 0; i < ylen; i++) {
            for (int j = 0; j < xlen; j++) {
                if (grid[i][j] == 0) {
                    ret++;
                    bfs(j, i, grid);
                    //或者dfs(j, i, grid);
                }
            }
        }
        return ret;
    }
    
    void dfs(int x, int y, vector<vector<int>>& grid) {
        int xlen = grid[0].size();
        int ylen = grid.size();
        if (x >= xlen || y >= ylen || x < 0 || y < 0 || grid[y][x] == 1) {
            return;
        }
        grid[y][x] = 1;
        int vx[] = {0, 1, 0, -1};
        int vy[] = {1, 0, -1, 0};
        for (int i = 0; i < 4; i++) {
            dfs(x+vx[i], y+vy[i], grid);
        }
    }
    
    void bfs(int x, int y, vector<vector<int>>& grid) {
        if (grid[y][x] == 1) {
            return;
        }
        int xlen = grid[0].size();
        int ylen = grid.size();
        queue<vector<int>> q;
        q.push({x, y});
        
        int vx[] = {0, 1, 0, -1};
        int vy[] = {1, 0, -1, 0};
        
        while (!q.empty()) {
            int curx = q.front()[0];
            int cury = q.front()[1];
            q.pop();
            grid[cury][curx] = 1;
            for (int i = 0; i < 4; i++) {
                int nextx = curx+vx[i];
                int nexty = cury+vy[i];
                if (nextx >= 0 && nextx < xlen && nexty >= 0 && nexty < ylen) {
                    if (grid[nexty][nextx] == 0) {
                        q.push({nextx, nexty});
                    }
                }
            }            
        }
    }
};

作者：cui-ze
链接：https://leetcode.cn/problems/number-of-closed-islands/solution/yi-ti-kan-tou-dfs-he-dfs-by-xiao-xiao-suan-fa/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

关于BFS的变种

在搜索起点和终点都明确的情况下，我们有时候会用双向BFS去减少搜索空间，大家画一下图的话可以感受出来我们大约可以减少一半的搜索空间。
如果熟练掌握，相信在面试的时候会让面试官眼前一亮的。给一个题目供大家思考：「433.最小基因变化」

总结

搜索是一种非常常用的算法，通过遍历算法问题的每种状态，我们往往是可以得到一个答案的。在许多时候，搜索并不是最高效的做法，但他往往是最容易想到的做法，在面试时如果没有想到更高效的解法，先给一个搜索的解法也是非常不错的选择哦，我们往往称之为暴力法。
大多数问题 BFS 和 DFS 其实都是可以解决的，个人觉得可能DFS写起来会简单一些。有一种场景BFS会比较常用，比如在迷宫中寻找a到b的最短距离这种，BFS 首次寻找到目标的时候一定是离起点最近的。而 DFS 则没有这个特性。
总之大家还是多多做题，多多总结，相信 DFS 和 BFS 都没有问题的。

评论 (0)