thảo luận Leetcode mỗi ngày

class Solution {
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int m, n;
    public int countSubIslands(int[][] grid1, int[][] grid2) {
        m = grid1.length; n = grid1[0].length;
        int ans = 0;
        boolean[][] visited = new boolean[m][n];

        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                if (grid2[row][col] == 1 && !visited[row][col]) {
                    ans = dfs(row, col, visited, grid1, grid2) ? ans + 1 : ans;
                }
            }
        }

        return ans;
    }

    private boolean dfs(int row, int col, boolean[][] visited, int[][] grid1, int[][] grid2) {
        if (row < 0 || row >= m || col < 0 || col >= n || visited[row][col] || grid2[row][col] != 1) {
            return true;
        }

        visited[row][col] = true;
        boolean ans = grid1[row][col] == 1;

        for (int[] dir: dirs) {
            if (!dfs(dir[0] + row, dir[1] + col, visited, grid1, grid2)) {
                ans = false;
            }
        }

        return ans;
    }
}

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        result = 0
        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        m, n = len(grid1), len(grid1[0])
        
        def isSubIsland(u, v, m, n):
            q = deque([(u, v)])
            valid = True
            grid2[u][v] = 0
            while q:
                x, y = q.popleft()
                if grid1[x][y] == 0:
                    valid = False
                for dx, dy in directions:
                    if (0 <= x + dx < m and 0 <= y + dy < n and grid2[x + dx][y + dy] == 1):
                        grid2[x + dx][y + dy] = 0
                        q.append((x+dx, y+dy))
                        
            return valid

        for i in range(m):
            for j in range(n):
                if grid2[i][j] == 1 and isSubIsland(i, j, m, n):
                    result += 1

        return result

public class Solution {
    public int CountSubIslands(int[][] grid1, int[][] grid2) {
        int ans = 0;
        int n = grid2.Length;
        int m = grid2[0].Length;

        bool[,] visited = new bool[n, m];
        bool isSubIsland = true;
        for(int i = 0; i < n; i ++)
        {
            for(int j = 0; j < m; j ++)
            {
                if(grid2[i][j] == 1 && !visited[i,j])
                {
                    isSubIsland = true;
                    DFS(grid1, grid2, i, j, n, m, visited, ref isSubIsland);
                    if(isSubIsland)
                    {
                        ans ++;
                    }
                }
            }
        }

        return ans;
    }
    public void DFS(int[][] grid1, int[][] grid2, int i, int j, int n, int m, bool[,] visited, ref bool isSubIsland)
    {
        if( i < 0 || j < 0 || i >= n || j >= m || grid2[i][j] == 0 || visited[i,j])
        {
            return;
        }

        if(grid2[i][j] != grid1[i][j])
        {
            isSubIsland = false;
            return;
        }
        visited[i,j] = true;
        DFS(grid1, grid2, i + 1, j, n, m, visited, ref  isSubIsland);
        DFS(grid1, grid2, i - 1, j, n, m, visited, ref  isSubIsland);
        DFS(grid1, grid2, i, j + 1, n, m, visited, ref  isSubIsland);
        DFS(grid1, grid2, i, j - 1, n, m, visited, ref  isSubIsland);
    }
}

class Solution {
    int[][] map;
    boolean[][] check;

    public int countSubIslands(int[][] grid1, int[][] grid2) {
        map = new int[grid1.length][grid1[0].length];
        int result = 0;

        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                if (grid1[i][j] == 1 && grid1[i][j] == grid2[i][j]) {
                    map[i][j] = 2;
                }
                else map[i][j] = grid2[i][j] - grid1[i][j];
            }
        }

        check = new boolean[map.length][map[0].length];

        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                if (!check[i][j]) {
                    if (map[i][j] == 2 && isSub(i, j)) {
                        result++;
                    }
                    check[i][j] = true;
                }
            }
        }

        return result;
    }

    public boolean isSub(int i, int j) {
        if (i < 0 || j < 0 || i >= map.length || j >= map[0].length)
            return true;
        if (map[i][j] <= 0)
            return true;
        if (map[i][j] == 1)
            return false;
        if (check[i][j])
            return true;
       
        check[i][j] = true;
        boolean result = isSub(i - 1, j) && isSub(i, j-1) && isSub(i + 1, j) && isSub(i, j + 1);
        if (!result) map[i][j] = 1;

        return result;
    }
}

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        rowNumbs = len(grid1)
        colNumbs = len(grid1[0])
        if rowNumbs < 1 or colNumbs <1 :
            return 0
        numberIslands = 0
        for i in range(rowNumbs):
            for j in range(colNumbs):
                if grid2[i][j] == 1:
                    isSubland = [True]
                    self.helpers(grid1, grid2, i, j, isSubland)
                    if (isSubland[0]):
                        numberIslands += 1   
        return numberIslands
    
    def helpers(self,grid1: List[List[int]],  grid2: List[List[int]], row, col, isSubland):
        if (row < 0 or row >= len(grid2) or col < 0 or col >= len(grid2[0])):
            return
        if (grid2[row][col] == 0):
            return
        if (grid1[row][col] == 0):
            isSubland[0] = False
        grid2[row][col] = 0
        right = self.helpers(grid1, grid2, row + 1, col, isSubland)
        left = self.helpers(grid1, grid2, row - 1, col, isSubland)
        bot = self.helpers(grid1, grid2, row, col -1, isSubland)
        top = self.helpers(grid1, grid2, row, col + 1, isSubland)

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        n = len(stones)
        components = n
        uf = DisjoinSet(n)
        for i in range(n):
            for j in range(i + 1, n):
                if stones[i][0] == stones[j][0] or stones[i][1] == stones[j][1]:
                    if uf.union(i, j):
                        components -= 1

        return n - components


class DisjoinSet:
    def __init__(self, size):
        self.root = [i for i in range(size)]
        self.rank = [0]*size

    def find(self, x):
        while x != self.root[x]:
            x = self.root[x]

        return x
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return False
        if self.rank[rootX] < self.rank[rootY]:
            self.root[rootX] = rootY
        elif self.rank[rootX] > self.rank[rootY]:
            self.root[rootY] = rootX
        else:
            self.root[rootX] = rootY
            self.rank[rootY] += 1

        return True