力扣周赛246期(下)

这是我参与更文挑战的第26天，活动详情查看：更文挑战

1905. 统计子岛屿

思路分析

每次遇到like “%岛屿%”问题，就会想到是dfs，中等题难度又向来是改个模版就完事了，所以不会太难。

依旧是矩阵以外视为水域，0也是水域。因此代码有

if(x < 0 || x >= grid2.size() || y < 0 || y >= grid2[0].size()){
            return; 
}
// 并不是岛屿
if (grid2[x][y] != 1)return;
复制代码

题干中定义子岛屿为： grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含

因此我们需要增加一个判断grid2[i][j] == 1的时候，对应索引在grid1上是否也是1。

代码

class Solution {
public:
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        int ret = 0;
        for(int i = 0; i < grid2.size(); i++){
            for(int j = 0; j < grid2[0].size(); j++){
                if(grid2[i][j] == 1){
                    bool flag = true;
                    dfs(grid1, grid2, flag, i, j);
                    if (flag == true)ret++;
                }
            }
        }
        return ret;
    }
    void dfs(vector<vector<int>>& grid1, vector<vector<int>>& grid2, bool& flag, int x, int y){
        // cout << x << " " << y << endl;
        // 地址非法
        if(x < 0 || x >= grid2.size() || y < 0 || y >= grid2[0].size()){
            return; 
        }
        // 并不是岛屿
        if (grid2[x][y] != 1)return;
        grid2[x][y] = 2;
        if(grid1[x][y] != 1)flag = false;
        dfs(grid1, grid2, flag, x + 1, y);
        dfs(grid1, grid2, flag, x - 1, y);
        dfs(grid1, grid2, flag, x, y + 1);
        dfs(grid1, grid2, flag, x, y - 1);
        return;
    }
};
复制代码

1906. 查询差绝对值的最小值

思路分析

这种一看穷举就会爆，所以第一时间点开相关标签，发现没有动态规划，

那没事了

从题型给出的输入输出看，如果不是动态规划，那基本就是前缀和（因为能在给定起点和终点，省穷举复杂度的算法并不是很多）。

常规前缀和的思路并不能帮我们解决问题，（因为这题求和并不能解决问题），所以我们要从题干出发，我们需要知道起点到终点的范围内，是否全是某个数（可以理解为某个数有多少个），或者都有什么数，顺序我们是并不关心的。

我们点开提示发现

这才注意到：

因此我们可以将前缀求和，转为对1-100每个数的计数。并对每个起点终点，从1-100进行遍历，找到最小差值即可。

代码

略略略。