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

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int sum = 0, ans = 0;

        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum - k)) {
                ans += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }

        return ans;
    }
}

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        m = len(grid2)
        n = len(grid2[0])

        def dfs(row, column):
            isSubIsLand = grid1[row][column] == 1
            grid2[row][column] = 0
            neighbors = [[0, -1], [-1, 0], [0, 1], [1, 0]]
            for neighbor in neighbors:
                newRow = row + neighbor[0]
                newColumn = column + neighbor[1]
                if newRow < 0 or newColumn < 0 or newRow == m or newColumn == n or grid2[newRow][newColumn] == 0:
                    continue

                if dfs(newRow, newColumn) == False:
                    isSubIsLand = False

            return isSubIsLand

        ans = 0
        for i in range(m):
            for j in range(n):
                if grid2[i][j] == 1:
                    if dfs(i, j):
                        ans += 1

        return ans

class Solution {
    public int countSubIslands(int[][] grid1, int[][] grid2) {
        int m = grid1.length;
        int n = grid1[0].length;
        int count = 0;
        int[][] DIRECTIONS = {{-1,0},{0,1},{1,0},{0,-1}};
        boolean[][] seen = new boolean[m][n];
       
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
            {
                if (grid2[i][j] == 0 || seen[i][j])
                    continue;
               
                boolean isSubisland = true;
                Queue<int[]> q = new LinkedList<>();
                q.add(new int[]{i, j});
                seen[i][j] = true;
               
                while (!q.isEmpty())
                {
                    int[] cell = q.poll();
                    if (grid1[cell[0]][cell[1]] == 0)
                        isSubisland = false;
                    for (int[] dir : DIRECTIONS)
                    {
                        int row = cell[0] + dir[0];
                        int col = cell[1] + dir[1];
                        if (row >= 0 && row < m && col >= 0 && col < n && grid2[row][col] == 1 && !seen[row][col])  
                        {
                            q.add(new int[]{row, col});
                            seen[row][col] = true;
                        }
                    }
                }
               
                if (isSubisland)
                    count++;
            }
        return count;
    }
}

function countSubIslands(grid1: number[][], grid2: number[][]): number {
    let res = 0, m = grid1.length, n = grid1[0].length;
    const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    const visited = new Array(m).fill(null).map(item => Array(n).fill(false));
    const check = (a: number, b: number) => {
        let ans = true;
        const q: number[][] = [];
        q.push([a, b]);
        visited[a][b] = true;
        while (q.length) {
            const [x, y] = q.shift();
            if (!grid1[x][y]) ans = false;
            for (const dir of dirs) {
                const xx = x + dir[0], yy = y + dir[1];
                if (xx >= 0 && xx < m && yy >= 0 && yy < n && !visited[xx][yy] && grid2[xx][yy]) {
                    visited[xx][yy] = true;
                    q.push([xx, yy])
                }
            }
        }
        return ans;
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (!visited[i][j] && grid2[i][j] && check(i, j)) res++
        }
    }
    return res;
};

var countSubIslands = function(grid1, grid2) {
    const ROWS = grid1.length;
    const COLS = grid1[0].length;

    var dfs = function (r, c) {
        // If grid2 cell is water then no need to check with grid1
        if (r < 0 || c < 0 || r == ROWS || c == COLS || grid2[r][c] == 0) return true;

        // If grid2 is land but grid1 is water then invalid
        if (grid1[r][c] == 0) return false;

        // Mark as visited
        grid2[r][c] = 0;

        const left = dfs(r, c - 1);
        const right = dfs(r, c + 1);
        const top = dfs(r - 1, c);
        const down = dfs(r + 1, c);
        
        return top && down && left && right;
    }

    let ans = 0;

    for (let r = 0; r < ROWS; r++) {
        for (let c = 0; c < COLS; c++) {
            if (grid2[r][c] == 1 && dfs(r, c)) {
                ans++;
            }
        }
    }

    return ans;
};

class Solution {
    private final int[][] moves = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    private boolean isSubIsland(int x, int y, int[][] grid1, int[][] grid2, boolean[][] visited) {
        boolean isSubIsland = true;
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[] {x, y});
        visited[x][y] = true;
        while (!queue.isEmpty()) {
            int[] direction = queue.poll();
            int currX = direction[0];
            int currY = direction[1];
            if (grid1[currX][currY] == 0) {
                isSubIsland = false;
            }
            for (int[] move : moves) {
                int nextX = currX + move[0];
                int nextY = currY + move[1];
                if (nextX >= 0 && nextX < grid1.length &&
                    nextY >= 0 && nextY < grid1[0].length &&
                    !visited[nextX][nextY] &&
                    grid2[nextX][nextY] != 0) {
                    queue.offer(new int[] {nextX, nextY});
                    visited[nextX][nextY] = true;
                }
            }
        }
        return isSubIsland;
    }

    public int countSubIslands(int[][] grid1, int[][] grid2) {
        int ans = 0;
        int cols = grid1.length;
        int rows = grid1[0].length;
        boolean[][] visited = new boolean[grid1.length][grid1[0].length];
        for (int i = 0; i < cols; i++) {
            for (int j = 0; j < rows; j++) {
                if (!visited[i][j] && grid2[i][j] != 0 && isSubIsland(i, j, grid1, grid2, visited)) ans++;
            }
        }
        return ans;
    }
}

class Solution {
    public int countSubIslands(int[][] grid1, int[][] grid2) {
        int row= grid2.length;
        int col = grid2[0].length;
        int cnt =0;
        for(int i  =0 ;i < row;i++){
            for(int j = 0; j < col ; j++){
                if(grid2[i][j]==1){
                    if(dfs(grid1, grid2, i, j,true)) cnt++;
                }
            }
        }
        return cnt;
    }
    public boolean dfs(int[][] grid1, int[][] grid2, int i , int j,boolean res){
        if(grid1[i][j] != 1) res=false;
        int row= grid2.length;
        int col = grid2[0].length;
        grid2[i][j]=-1;
        int[][] directions = {{-1,0},{0,1},{1,0},{0,-1}};

        for(int[] dir:directions ){
            int m = i +dir[0];
            int n = j + dir[1];
            if(m<row && m>=0 && n<col && n>=0 && grid2[m][n]==1){
                res = dfs(grid1, grid2, m, n, res);
            }
        }
        return res;
    }
}

class Solution {
    boolean isSubIsland;
    public int countSubIslands(int[][] grid1, int[][] grid2) {
        int count = 0;
        for(int row = 0;row<grid2.length;row++){
            for(int col = 0;col<grid2[0].length;col++){
                if(grid2[row][col]==1){
                    isSubIsland = true;
                    count++;
                    sink(grid2,grid1,row,col);
                    if(!isSubIsland) count--;
                }
            }
        }
        return count;
    }

    public void sink(int[][] grid2, int[][] grid1, int row, int col){
        if(
        row<0||
        row>=grid2.length||
        col>=grid2[0].length||
        col<0||
        grid2[row][col]==0
        )
            return;
        if(grid1[row][col]==0)
            isSubIsland = false;
        grid2[row][col] = 0;
        sink(grid2, grid1, row+1, col);
        sink(grid2, grid1, row-1, col);
        sink(grid2, grid1, row, col+1);
        sink(grid2, grid1, row, col-1);
    }
}

impl Solution {
    pub fn count_sub_islands(mut grid1: Vec<Vec<i32>>, mut grid2: Vec<Vec<i32>>) -> i32 {
        fn dfs(i: usize, j: usize, grid1: &Vec<Vec<i32>>, grid2: &mut Vec<Vec<i32>>, cur_island: i32) -> bool {
            grid2[i][j] = cur_island;

            let neighbours = [(i - 1, j), (i, j + 1), (i + 1, j), (i, j - 1)];
            let (m, n) = (grid2.len(), grid2[0].len());

            let mut result = (grid1[i][j] != 0);

            for (k, l) in neighbours {
                if !(0 <= k && k < m && 0 <= l && l < n) {
                    continue;
                }

                if grid2[k][l] != 1 {
                    continue;
                }

                result = result && (grid1[i][j] == grid1[k][l]);
                let cascade = dfs(k, l, grid1, grid2, cur_island);
                result = result && cascade;
            }

            result
        }

        let (m, n) = (grid2.len(), grid2[0].len());

        let mut cur_island = 1;
        let mut sub_island_count = 0;

        for i in 0..m {
            for j in 0..n {
                if grid2[i][j] != 1 {
                    continue;
                }

                cur_island += 1;

                if dfs(i, j, &grid1, &mut grid2, cur_island) {
                    sub_island_count += 1;
                }
            }
        }

        sub_island_count
    }
}

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        isSub = True
        m , n = len(grid1) , len(grid1[0])
        cnt = 0
        def sink(i , j):
            nonlocal isSub
            if i >= m or j >= n or i < 0 or j < 0 or grid2[i][j] == 0: return
            if grid1[i][j] == 0:
                isSub = False
            grid2[i][j] = 0
            sink(i + 1 , j)
            sink(i - 1 , j)
            sink(i , j + 1)
            sink(i , j - 1)

        for i in range(m):
            for j in range(n):
                if grid2[i][j] == 1:
                    isSub = True
                    cnt += 1
                    sink(i , j)
                    if not isSub: cnt -= 1
        
        return cnt