This is the 26th day of my participation in Gwen Challenge

1905. Statistical sub-islands

Thought analysis

Every time I encounter a question like “% islands %”, I will think of DFS. The medium difficulty is always to change the template, so it is not too difficult.

It’s still outside of the matrix as a water area, and 0 is also a water area. So the code has

if(x < 0 || x >= grid2.size() || y < 0 || y >= grid2[0].size()) {return; 
}
// It is not an island
if(grid2[x][y] ! =1)return;
Copy the code

Each cell of the island in grid2 is fully contained by the same island in Grid1

Therefore, we need to add a judgment whether the corresponding index on grid1 is also 1 when grid2[I][j] == 1.

code

class Solution {
public:
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        int ret = 0;
        for(int i = 0; i < grid2.size(a); i++){for(int j = 0; j < grid2[0].size(a); 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;
        // The address is invalid
        if(x < 0 || x >= grid2.size() || y < 0 || y >= grid2[0].size()) {return; 
        }
        // It is not an island
        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; }};Copy the code

1906. Query the minimum absolute value of the difference

Thought analysis

This kind of thing is going to explode at the first sight, so the first time I click on the relevant label, I find that there is no dynamic programming,

That’s fine

From the input and output given by the question type, if it is not dynamic programming, it is basically prefix sum (because there are not many algorithms that can save exhaustive complexity at a given starting point and ending point).

Conventional prefix and train of thought and can’t help us solve the problem, (because this sum will not solve the problem), so we should start from the problem of dry, we need to know the starting point to the finish line, within the scope of the whether is full of a certain number (can be understood as a certain number of how many), or have what number, order we don’t care.

We clicked on the hint and found

Then I noticed:

So we can sum the prefixes, turn them into numbers from 1 to 100. And for each starting point and end point, traversal from 1-100 to find the minimum difference.

code

A little.