Leetcode每日一题 —— 3619. 总价值可以被 K 整除的岛屿数目

依旧可以用并查集糊，注意求和时最好开个 int64，不然可能溢出。

class Solution {

public:

    int countIslands(vector<vector<int>>& grid, int k) {

        // 依旧并查集

        int m=grid.size(),n=grid[0].size();

        vector<int> parents(m*n,-1),sizes(m*n,1);

        vector<long long> sums(m*n,0);

        for(int i=0;i<m;i++){

            for(int j=0;j<n;j++){

                sums[i*n+j]=grid[i][j];

            }

        }

        auto find=[&](this auto&& self,int x) -> int {

            return parents[x]<0 ? x : parents[x]=self(parents[x]);

        };

        auto merge=[&](int x1,int x2){

            int root1=find(x1),root2=find(x2);

            if(root1==root2){

                return;

            }

            if(sizes[root1]<sizes[root2]){

                swap(root1,root2);

            }

            parents[root2]=root1;

            sizes[root1]+=sizes[root2];

            sums[root1]+=sums[root2];

        };

        // 合并非零岛屿来计数

        for(int i=0;i<m;i++){

            for(int j=0;j<n;j++){

                int idx=i*n+j;

                if(grid[i][j]<=0){

                    parents[idx]=-2;

                    continue;

                }

                if(i<m-1&&grid[i+1][j]>0){

                    merge(idx,(i+1)*n+j);

                }

                if(j<n-1&&grid[i][j+1]>0){

                    merge(idx,i*n+j+1);

                }

            }

        }

        int res=0;

        // 检查正整数岛屿能否被 k 整除

        for(int i=0;i<parents.size();i++){

            if(parents[i]==-1&&sums[i]%k==0){

                res++;

            }

        }

        return res;

    }

};

class Solution:

    def countIslands(self, grid: list[list[int]], k: int) -> int:

        m, n = len(grid), len(grid[0])

        vis = [[False] * n for _ in range(m)]



        def dfs(i, j, cur) -> int:

            if i < 0 or i == m or j < 0 or j == n or not grid[i][j] or vis[i][j]:

                return 0

 

            vis[i][j] = True

            cur = grid[i][j]

            cur += dfs(i, j-1, cur)

            cur += dfs(i-1, j, cur)

            cur += dfs(i, j+1, cur)

            cur += dfs(i+1, j, cur)

            

            return cur



        ans = 0

        for i in range(m):

            for j in range(n):

                if grid[i][j] and not vis[i][j]:

                    ans += dfs(i, j, 0) % k == 0

        return ans

那依旧bfs。

class Solution {

public:

    int countIslands(vector<vector<int>>& grid, int k) {

        int m = grid.size(), n = grid[0].size();

        static vector<int> dx = {0,1,0,-1}, dy = {1,0,-1,0};

        auto solve = [&](int x, int y) -> int {

            queue<int> q;

            q.push(x * n + y);

            int sum = grid[x][y];

            grid[x][y] = 0;

            while(!q.empty()) {

                auto t = q.front();

                q.pop();

                auto tx = t / n, ty = t % n;

                for(int i = 0; i < 4; i++) {

                    int nx = tx + dx[i], ny = ty + dy[i];

                    if(nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] > 0) {

                        sum = (sum + grid[nx][ny]) % k;

                        grid[nx][ny] = 0;

                        q.push(nx * n + ny);

                    }

                }

            }

            return sum % k == 0;

        };

        int res = 0;

        for(int i = 0; i < m; i++) {

            for(int j = 0; j < n; j++) {

                if(grid[i][j] > 0) {

                    res += solve(i,j);

                }

            }

        }

        return res;

    }

};