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

class Solution {
    public TreeNode replaceValueInTree(TreeNode root) {
        List<List<Integer>> levelSum = new ArrayList();
        Queue<TreeNode> queue = new LinkedList();
        root.val = 0;
        int sum = 0;
//create list
        queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList();
            for(int i = 0;i<size;i++){
                sum = 0;
                TreeNode node = queue.poll();
                if(node.right!=null) {
                    sum+=node.right.val;
                    queue.add(node.right);
                }
                if(node.left!=null){
                    sum+=node.left.val;
                    queue.add(node.left);
                }
                list.add(sum);
            }
            levelSum.add(list);
        }
//modify tree
        int index = 0;
        queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            sum = 0;
            List<Integer> list = levelSum.get(index++);
            for(int i:list)
                sum+=i;
            for(int i = 0;i<size;i++){
                TreeNode node = queue.poll();
                int val = list.get(i);
                if(node.right!=null) {
                    queue.add(node.right);
                    node.right.val = sum-val;
                }
                if(node.left!=null){
                    queue.add(node.left);
                    node.left.val = sum-val;
                }
            }
        }
        return root;
    }
}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def dfs_sum_level(cur, sum_level, level):
    sum_level[level] += cur.val
    if (cur.left):
        dfs_sum_level(cur.left, sum_level, level+1)
    if (cur.right):
        dfs_sum_level(cur.right, sum_level, level+1)

def dfs_calc_val(cur, sum_level, level, sum_same_parents):
    cur.val = sum_level[level] - sum_same_parents
    sum_leaf = 0
    if cur.left: sum_leaf += cur.left.val
    if cur.right: sum_leaf += cur.right.val
    if cur.left: dfs_calc_val(cur.left, sum_level, level+1, sum_leaf)
    if cur.right: dfs_calc_val(cur.right, sum_level, level+1, sum_leaf)

class Solution:
    def replaceValueInTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        sum_level = [0]*(int(1e5+7))
        
        dfs_sum_level(root, sum_level, 0)
        dfs_calc_val(root, sum_level, 0, root.val)
        return root

class Solution {
    public TreeNode replaceValueInTree(TreeNode root) {
        Map<Integer, Integer> layerSums = calculateLayerSum(root);
        return updateTree(root, 0, layerSums);
    }

    public TreeNode updateTree(TreeNode root, int layer, Map<Integer, Integer> layerSums) {
        if (root == null) return null;

        if (layer == 0) root.val = 0;

        int leftChild = (root.left != null) ? root.left.val : 0;
        int rightChild = (root.right != null) ? root.right.val : 0;

        int layerSum = layerSums.get(layer + 1);
        int childVal = layerSum - leftChild - rightChild;
        if (root.left != null) {
            root.left.val = childVal;
            updateTree(root.left, layer + 1, layerSums);
        }

        if (root.right != null) {
            root.right.val = childVal;
            updateTree(root.right, layer + 1, layerSums);
        }

        return root;
    }

    public Map<Integer, Integer> calculateLayerSum(TreeNode root) {
        Map<Integer, Integer> layerSums = new HashMap<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        int layer = 0;
        while (!queue.isEmpty()) {
            int layerSize = queue.size();
            int layerSum = 0;
            for (int i = 0; i < layerSize; i++) {
                TreeNode curNode = queue.poll();
                if (curNode == null) continue;

                layerSum += curNode.val;
                queue.add(curNode.right);
                queue.add(curNode.left);
            }
            layerSums.put(layer, layerSum);
            layer++;
        }

        return layerSums;
    }
}

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        s = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                s[i][j] = matrix[i - 1][j - 1] + s[i-1][j] + s[i][j-1] - s[i-1][j-1]
        
        result = 0
        def isValid(u, v):
            return u >= 0 and v >= 0
        for i in range(m+1):
            for j in range(n+1):
                k = 1
                while isValid(i - k, j - k):
                    if s[i][j] - s[i-k][j] - s[i][j-k] + s[i-k][j-k] == k ** 2:
                        result += 1
                    else:
                        break
                    k += 1

        return result

impl Solution {
    pub fn count_squares(matrix: Vec<Vec<i32>>) -> i32 {
        let (m, n) = (matrix.len(), matrix[0].len());

        let mut col_cont = vec![vec![0; n]; m];
        let mut row_cont = vec![vec![0; n]; m];
        let mut extents = vec![vec![0; n]; m];
        let mut result = 0;

        let mut col_count = 0;
        for j in 0..n {
            for i in 0..m {
                if matrix[i][j] == 0 {
                    col_count = 0;
                } else {
                    col_count += 1;
                }

                col_cont[i][j] = col_count;
            }

            col_count = 0;
        }

        let mut row_count = 0;
        for i in 0..m {
            for j in 0..n {
                if matrix[i][j] == 0 {
                    row_count = 0;
                } else {
                    row_count += 1;
                }

                row_cont[i][j] = row_count;
            }

            row_count = 0;
        }

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

                if i == 0 || j == 0 {
                    extents[i][j] = 1;
                    result += 1;
                    continue;
                }

                let count = col_cont[i][j].min(extents[i - 1][j - 1] + 1).min(row_cont[i][j]);
                result += count;
                extents[i][j] = count;
            }
        }

        result
    }
}

var countSquares = function(matrix) {
    const m = matrix.length, n = matrix[0].length;
    let ans = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            let k = matrix[i][j];
            if (i > 0 && j > 0 && k > 0) {
                matrix[i][j] = k = Math.min(
                    matrix[i-1][j],
                    matrix[i][j-1],
                    matrix[i-1][j-1]
                ) + 1;
            }
            ans += k;
        }
    }
    return ans;
};

class Solution {
    public int countSquares(int[][] matrix) {
        int count = 0;
        int level = matrix.length;

        while (level > 0) {
            for (int i = 0; i < level; i++) {
                for (int j = 0; j < matrix[i].length; j++) {
                    if (matrix[i][j] == 1)
                        count++;

                    if (j == matrix[i].length - 1 || i == level - 1) {
                        matrix[i][j] = 0;
                        continue;
                    }
                        
                    if (matrix[i][j] + matrix[i][j+1] + matrix[i+1][j] + matrix[i+1][j+1] == 4)
                        matrix[i][j] = 1;

                    else
                        matrix[i][j] = 0;
                }
            }
            level--;
        }

        return count;
    }
}

class Solution {
    public int countSquares(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;       

        int res = 0;
        for (int size = 1; size <= m; size++) {
            if (size > n) {
                break;
            }

            for (int i = 0; i <= m - size; i++) {
                for (int j = 0; j <= n - size; j++) {
                    if (isSquare(matrix, i, j, size)) {
                        res++;
                    }
                }
            }
        }

        return res;
    }

    private boolean isSquare(int[][] matrix, int y, int x, int size) {
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (matrix[y + i][x + j] == 0) {
                    return false;
                }
            }
        }

        return true;
    }
}

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        vector<vector<int>> dp(matrix.size(), vector<int>(matrix[0].size(), 0));
        int ans = 0;
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[0].size(); j++) {
                if (matrix[i][j]) {
                    if (i == 0 || j == 0) dp[i][j] = 1;
                    else dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1;
                }
                ans += dp[i][j];
            }
        }
        return ans;
    }
};

class Solution {
    public int countSquares(int[][] matrix) {
        int[][] dp = new int[matrix.length + 1][matrix[0].length + 1];
        dp[0][0] = 0;
        int ans = 0;
        for (int i = 1; i <= matrix.length; i++) {
            for (int j = 1; j <= matrix[i - 1].length; j++) {
                if (matrix[i - 1][j - 1] == 1) {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
                    ans += dp[i][j];
                }
            }
        }
        return ans;
    }
}

class Solution {
    public static final int R = 0;
    public static final int C = 1;
    public int countSquares(int[][] matrix) {
        int height = matrix.length;
        int width = matrix[0].length;

        int[][] prefixSum = new int[height][width];

        for (int r = 0; r < height; r++) {
            for (int c = 0; c < width; c++) {
                int left = (c == 0) ? 0 : prefixSum[r][c - 1];
                int up = (r == 0) ? 0 : prefixSum[r - 1][c];
                int diagonal = (c == 0 || r == 0) ? 0 : prefixSum[r - 1][c - 1];
                prefixSum[r][c] = left + up - diagonal + matrix[r][c];
            }
        }

        int squareSubMatrix = 0;
        for (int r = 0; r < height; r++) {
            for (int c = 0;  c < width; c++) {
                for (int squareSize = 0; squareSize < Math.min(height - r, width - c); squareSize++) {
                    int[] topLeft =  new int[]{r, c};
                    int[] bottomRight = new int[]{r + squareSize, c + squareSize};

                    int squareCal = prefixSum[bottomRight[R]][bottomRight[C]];
                    squareCal -= (topLeft[C] == 0) ? 0 : prefixSum[bottomRight[R]][topLeft[C] - 1];
                    squareCal -= (topLeft[R] == 0) ? 0 : prefixSum[topLeft[R] - 1][bottomRight[C]];;
                    squareCal += (topLeft[C] == 0 || topLeft[R] == 0) ? 0 : prefixSum[topLeft[R] - 1][topLeft[C] - 1];
                    if (squareCal == (squareSize + 1) * (squareSize + 1)) {
                        squareSubMatrix++;
                    }
                }
            }
        }
        return squareSubMatrix;
        
    }
}

func countSquares(matrix [][]int) int {
    rs := 0
    m, n := len(matrix), len(matrix[0])
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if i == 0 || j == 0 {
                dp[i][j] = matrix[i][j]
            } else if (matrix[i][j]) == 1 {
                dp[i][j] = 1 + Min(dp[i][j-1], Min(dp[i-1][j-1], dp[i-1][j]))
            } // else { dp[i][j] = 0; }
            rs += dp[i][j]
        }
    }
    return rs
}

func Min(a int, b int) int {
    if a < b { return a }
    return b
}

class Solution {
    public int countSquares(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int side = Math.min(m,n);
        int count = 0;
        int[][] sum = new int[m+1][n+1];
        for(int i = 1;i<m+1;i++){
            for(int j = 1;j<n+1;j++){
                sum[i][j] = matrix[i-1][j-1]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
            }
        }
        
        for(int i =1;i<=side;i++){
            for(int j=i;j<m+1;j++){
                for(int k =i;k<n+1;k++){
                    if(sum[j][k] - sum[j-i][k] -sum[j][k-i]+sum[j-i][k-i] == i*i)
                        count++;
                }
            }
        }
        return count;

    }
}

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        const int m = matrix.size();
        const int n = matrix[0].size();
        int count = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 1) {
                    if (i > 0 && j > 0) {
                        matrix[i][j] += min(matrix[i - 1][j - 1], min(matrix[i][j - 1], matrix[i - 1][j]));
                    }
                    count += matrix[i][j];
                }
            }
        }
        return count;
    }
};