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

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        def find_land(grid):
            lands = {}
            for i in range(len(grid)):
                for j in range(len(grid[0])):
                    if grid[i][j] == 1:
                        lands[i, j] = grid[i][j]
            return lands
        def get_neighbors(grid, i, j):
            n, m = len(grid), len(grid[0])
            lst = [(i-1, j), (i+1, j), (i, j+1), (i, j-1)]
            res = []
            for a, b in lst:
                if a >= 0 and a < n and b >= 0 and b < m:
                    res.append((a, b))
            return res
        lands = find_land(grid)
        # print(lands)
        ans = 0
        for (i, j), _ in lands.items():
            # print(i, j)
            neighbors = get_neighbors(grid, i, j)
            tmp = 4
            for neighbor in neighbors:
                tmp -= lands.get(neighbor, 0)
            ans += tmp
        # print(ans)
        return ans

public class Solution {
    public static int CountAdjacentOnes(int[][] matrix, int row, int col)
    {
        int count = 0;
        if (row - 1 >= 0 && matrix[row - 1][col] == 1)
        {
            count++;
        }
        if (row + 1 < matrix.Length && matrix[row + 1][col] == 1)
        {
            count++;
        }
        if (col - 1 >= 0 && matrix[row][col - 1] == 1)
        {
            count++;
        }

        if (col + 1 < matrix[0].Length && matrix[row][col + 1] == 1)
        {
            count++;
        }

        return count;
    }
    public int IslandPerimeter(int[][] grid) {
        int count = 0;
        for(int i =0;i < grid.Length;i++)
        {
            for(int j = 0; j < grid[0].Length;j ++)
            {
                if(grid[i][j] ==1)
                {
                    count+= 4-CountAdjacentOnes(grid,i,j);
                    if(CountAdjacentOnes(grid,i,j)==0)
                        return count;
                }
            }
        }
        return count;
    }
}

var islandPerimeter = function(grid) {
    let perimeter = 0;
    let row = grid.length - 1;
    let col = grid[0].length - 1;
    let offsets = [[0, 1], [1, 0]];

    for (let i = 0; i <= row; i++) {
        for (let j = 0; j <= col; j++) {
            if (grid[i][j]) {
                perimeter += 4
                offsets.forEach( ([x, y]) => {
                    if (grid[i + x] && grid[i + x][j + y]) {
                        perimeter -= 2;
                    }
                })
            };
        }
    }

    return perimeter;
};

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        directions = [[0, -1], [0, 1], [-1, 0], [1, 0]]
        m = len(grid)
        n = len(grid[0])
        def dfs(row, column):
            grid[row][column] = "0"
            for dx, dy in directions:
                neighborX = dx + row
                neighborY = dy + column
                if 0 <= neighborX < m and 0 <= neighborY < n and grid[neighborX][neighborY] == "1":
                    dfs(neighborX, neighborY)

        islands = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    islands +=1
                    dfs(i, j)


        return islands

class Solution {
    public int numIslands(char[][] grid) {
        int res = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == '0') continue;
                res += helper(grid, i, j);
            }
        }
        return res;
    }

    private int helper(char[][] grid, int row, int col) {
        if(Math.min(row, col) < 0 || row >= grid.length || col >= grid[0].length) return 0;
        if(grid[row][col] != '1') return 0;
        grid[row][col] = '0';
        helper(grid, row, col+1);
        helper(grid, row+1, col);
        helper(grid, row, col-1);
        helper(grid, row-1, col);
        return 1;
    }
}

class Solution {
    int rows, cols;
    boolean[][] markIsland;
    public int numIslands(char[][] grid) {
        int countIsland = 0;
        rows = grid.length;
        cols = grid[0].length;
        markIsland = new boolean[rows][cols];

        for(int r=0; r < rows; r++){
            for(int c=0; c < cols; c++){
                if(grid[r][c] == '1' && markIsland[r][c] == false){
                    countIsland++;
                    markNeighbor(grid, r, c);
                }
            }
        }
        return countIsland;
    }

    private void markNeighbor(char[][] grid, int r, int c){
        if(isIndexOutOfBound(r, c))
            return;
        if(markIsland[r][c])
            return;

        if(grid[r][c] == '1'){
            markIsland[r][c] = true;
            markNeighbor(grid, r-1, c);
            markNeighbor(grid, r+1, c);
            markNeighbor(grid, r, c-1);
            markNeighbor(grid, r, c+1);
        }
    }

    private boolean isIndexOutOfBound(int r, int c){
        return r < 0 || r >= rows || c < 0 || c >= cols;
    }
}

class Solution {
    public int numIslands(char[][] grid) {
        int ans = 0;
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[i].length; j++){
                if(grid[i][j] == '1'){
                    ans++;
                    dfs(grid, i, j);
                }
            }
        }
        return ans;
    }
    public void dfs(char[][] grid, int i, int j){
        if(i < 0 || j <0 || grid.length <= i  || grid[0].length <= j || grid[i][j] != '1'){
            return;
        }
        grid[i][j] = '-';
        dfs(grid, i, j + 1);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i - 1, j);
    }
}

var numIslands = function(grid) {
    let rows = grid.length;
    let cols = grid[0].length;
    let res = 0;

    var dfs = function (row, col) {
        if (row < 0 || col < 0 || row >= rows || col >= cols || grid[row][col] == '0') return;

        grid[row][col] = '0'; // Mark it as visited.

        dfs(row, col - 1);
        dfs(row, col + 1);
        dfs(row - 1, col);
        dfs(row + 1, col);
    }

    var bfs = function (row, col) {
        let queue = [[row, col]];
        while (queue.length) {
            let [r, c] = queue.shift();
            if (r >= 0 && c >= 0 && r < rows && c < cols && grid[r][c] == '1') {
                // Mark as visited
                grid[r][c] = '0';
                queue.push([r, c - 1]);
                queue.push([r, c + 1]);
                queue.push([r - 1, c]);
                queue.push([r + 1, c]);
            }
        }
    }

    for (let row = 0; row < rows; row++) {
        for (let col = 0; col < cols; col++) {
            if (grid[row][col] == '1') {
                res += 1;
                dfs(row, col);
            }
        }
    }

    return res;
};

class Solution {
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int count = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1') {
                    ++count;
                    dfs(grid, i, j, m, n);
                }
            }
        }
        return count;
    }

    public void dfs(char[][] grid, int x, int y, int m, int n) {
        if (x >= 0 && y >= 0 && x < m && y < n && grid[x][y] == '1') {
            grid[x][y] = ' ';
            dfs(grid, x + 1, y, m, n);
            dfs(grid, x - 1, y, m, n);
            dfs(grid, x, y + 1, m, n);
            dfs(grid, x, y - 1, m, n);
        }
    }
}

function numIslands(grid: string[][]): number {
    let res = 0, m = grid.length, n = grid[0].length;
    const dirs = [[0,1], [1,0], [0,-1], [-1,0]];
    for (let i = 0; i <m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === '1') {
                res++;
                grid[i][j] = '0';
                const q: [number, number][] = [];
                q.push([i,j]);
                while (q.length) {
                    const [x,y] = q.shift();
                    for (const dir of dirs) {
                        const xx = x + dir[0], yy = y + dir[1];
                        if(xx >= 0 && xx < m && yy >=0 && yy < n && grid[xx][yy] === '1') {
                            grid[xx][yy] = '0';
                            q.push([xx, yy])
                        }   
                    }
                }
            }
        }
    }   
    return res;
};

var numIslands = function(grid) {
    let count = 0;
    let row = grid.length;
    let col = grid[0].length;

    function dfs(i, j) {
        if (i < 0 || i >= row || j < 0 || j >= col || grid[i][j] === '0' || grid[i][j] === -1) {
            return;
        }

        grid[i][j] = -1;
        dfs(i, j - 1);
        dfs(i, j + 1);
        dfs(i - 1, j);
        dfs(i + 1, j);
    }

    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if (grid[i][j] === '1') {
                count++;
                dfs(i, j);
            }
        }
    }
    
    return count;
};

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        result = 0
        m, n = len(grid), len(grid[0])

        dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1] # (-1, 0), (0, 1), (1, 0), (0, -1)

        def dfs(u, v, m, n):
            if grid[u][v] == '0':
                return
           
            grid[u][v] = '0'
            for i in range(4):
                if u + dx[i] >= 0 and u + dx[i] < m and v + dy[i] >= 0 and v + dy[i] < n:
                    bfs(u + dx[i], v + dy[i], m, n)
       
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    result += 1
                    dfs(i, j, m, n)
        return result

public class Solution
{
    public int NumIslands(char[][] grid)
    {
        int numIslands = 0;
        int rows = grid.Length;
        if (rows == 0) return 0;
        int cols = grid[0].Length;

        for (int row = 0; row < rows; row++)
        {
            for (int col = 0; col < cols; col++)
            {
                if (grid[row][col] == '1')
                {
                    numIslands++;
                    DFS(row, col, rows, cols, grid);
                }
            }
        }

        return numIslands;
    }

    private void DFS(int row, int col, int rows, int cols, char[][] grid)
    {
        if (row < 0 || rows <= row || col < 0 || cols <= col || grid[row][col] == '0')
        {
            return;
        }

        grid[row][col] = '0';

        DFS(row - 1, col, rows, cols, grid); // Up
        DFS(row + 1, col, rows, cols, grid); // Down
        DFS(row, col - 1, rows, cols, grid); // Left
        DFS(row, col + 1, rows, cols, grid); // Right
    }
}

class Solution {
    public int numIslands(char[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        int count=0;
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                if(grid[i][j]=='1'){
                    traversal(i,j,grid,rows,cols);
                    count++;
                } 
            }
        }
        return count;
    }
    private void traversal(int i,int j, char[][] grid, int rows, int cols){
        grid[i][j]='.';
        if(i+1<rows && grid[i+1][j]=='1') traversal(i+1,j,grid,rows, cols);
        if(j+1<cols && grid[i][j+1]=='1') traversal(i,j+1,grid,rows, cols);
        if(j-1>=0 && grid[i][j-1]=='1') traversal(i,j-1,grid,rows, cols);
        if(i-1>=0 && grid[i-1][j]=='1') traversal(i-1,j,grid,rows, cols);
    }
}

from queue import Queue

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        row = len(grid)
        col = len(grid[0])
        visited = [[False for j in range(col)] for i in range(row)]
        queue = Queue()
        count = 0
        for i in range(row):
            for j in range(col):
                if grid[i][j] == '1' and not visited[i][j]:
                    count += 1
                    queue.put((i, j))
                    visited[i][j] = True
                    while not queue.empty():
                        (curR, curC) = queue.get()
                        if curR > 0 and grid[curR-1][curC] == '1' and not visited[curR-1][curC]:
                            visited[curR-1][curC] = True
                            queue.put((curR-1, curC))
                        if curR < row - 1 and grid[curR+1][curC] == '1' and not visited[curR+1][curC]:
                            visited[curR+1][curC] = True
                            queue.put((curR+1, curC))
                        if curC > 0 and grid[curR][curC-1] == '1' and not visited[curR][curC-1]:
                            visited[curR][curC-1] = True
                            queue.put((curR, curC-1))
                        if curC < col - 1 and grid[curR][curC+1] == '1' and not visited[curR][curC+1]:
                            visited[curR][curC+1] = True
                            queue.put((curR, curC+1))
        return count

    public int numIslands(char[][] grid) {
        int sumIslands = 0;
        for (int row = 0; row < grid.length; row++) {
            for (int col = 0; col < grid[row].length; col++) {
                if (grid[row][col] == '1') {
                    ++sumIslands;
                    DFSfill0(grid, row, col);
                }
            }
        }
        return sumIslands;
    }

    private void DFSfill0(char[][] grid, int row, int col) {
        if (row >= 0 && col >= 0 && row < grid.length && col < grid[row].length
                && grid[row][col] == '1') {
            grid[row][col] = '0';
            DFSfill0(grid, row + 1, col);
            DFSfill0(grid, row - 1, col);
            DFSfill0(grid, row, col - 1);
            DFSfill0(grid, row, col + 1);
        }
    }

class Solution {
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int ans = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    ans++;
                    dfs(i, j, grid);
                }
            }
        }

        return ans;
    }

    private void dfs(int row, int col, char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] == '0') {
            return;
        }

        grid[row][col] = '0';

        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        for (int[] dir: dirs) {
            dfs(row + dir[0], col + dir[1], grid);
        }
    }
}