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

class Solution:
    def sumOfDistancesInTree(self, n: int, edges: List[List[int]]) -> List[int]:
        g = defaultdict(list)
        for edge in edges:
            g[edge[0]].append(edge[1])
            g[edge[1]].append(edge[0])

        cache = {}
        def dfs(prev, u):
            if (prev, u) in cache:
                return cache[(prev, u)]
            if (-1, u) in cache:
                num_node1, num_edge1 = cache[(-1, u)]
                num_node2, num_edge2 = cache[(u, prev)]
                return num_node1 - num_node2, num_edge1 - num_edge2 - num_node2
            num_node, num_edge = 0, 0
            for v in g[u]:
                if v == prev:
                    continue
                node, edge = dfs(u, v)
                num_node += node
                num_edge += edge + node
            cache[(prev, u)] = (num_node + 1, num_edge)
            return num_node + 1, num_edge
        ret = [-1 for i in range(n)]
        def cal(u):
            if ret[u] >= 0:
                return
            ret[u] = dfs(-1, u)[1]
            for v in g[u]:
                cal(v)
        cal(0)
        return ret

use std::collections::HashMap;

impl Solution {
    pub fn sum_of_distances_in_tree(n: i32, edges: Vec<Vec<i32>>) -> Vec<i32> {
        let vertex_count = n as usize;
        let mut map_edges = HashMap::<usize, Vec<usize>>::new();

        for edge in edges.into_iter() {
            let source = edge[0] as usize;
            let target = edge[1] as usize;

            if let Some(vertices) = map_edges.get_mut(&source) {
                vertices.push(target);
            } else {
                map_edges.insert(source, vec![target]);
            }

            if let Some(vertices) = map_edges.get_mut(&target) {
                vertices.push(source);
            } else {
                map_edges.insert(target, vec![source]);
            }
        }

        let mut subtree_distance_sums = vec![0; vertex_count];
        let mut subtree_sizes = vec![0; vertex_count];
        let mut distance_sums = vec![0; vertex_count];

        Self::build_foundation(&map_edges, &mut subtree_distance_sums, &mut subtree_sizes);
        Self::reroot(&map_edges, &mut subtree_distance_sums, &mut subtree_sizes, &mut distance_sums);

        distance_sums.into_iter().map(|sum| sum as i32).collect()
    }

    fn build_foundation(
        edges: &HashMap<usize, Vec<usize>>,
        subtree_distance_sums: &mut Vec<usize>,
        subtree_sizes: &mut Vec<usize>
    ) {
        let n = subtree_sizes.len();
        let mut visited = vec![false; n];

        Self::build_foundation_visit(0, &mut visited, edges, subtree_distance_sums, subtree_sizes);
    }

    fn build_foundation_visit(
        vertex: usize,
        visited: &mut Vec<bool>,
        edges: &HashMap<usize, Vec<usize>>,
        subtree_distance_sums: &mut Vec<usize>,
        subtree_sizes: &mut Vec<usize>
    ) {
        let n = subtree_sizes.len();
        visited[vertex] = true;

        for &neighbour in edges.get(&vertex).unwrap_or(&vec![]).iter() {
            if visited[neighbour] {
                continue;
            }

            Self::build_foundation_visit(neighbour, visited, edges, subtree_distance_sums, subtree_sizes);

            subtree_distance_sums[vertex] += subtree_distance_sums[neighbour] + subtree_sizes[neighbour];
            subtree_sizes[vertex] += subtree_sizes[neighbour];
        }

        subtree_sizes[vertex] += 1;
    }

    fn reroot(
        edges: &HashMap<usize, Vec<usize>>,
        subtree_distance_sums: &mut Vec<usize>,
        subtree_sizes: &mut Vec<usize>,
        distance_sums: &mut Vec<usize>
    ) {
        let n = subtree_sizes.len();
        let mut visited = vec![false; n];

        Self::reroot_visit(0, None, &mut visited, edges, subtree_distance_sums, subtree_sizes, distance_sums);
    }

    fn reroot_visit(
        vertex: usize,
        parent: Option<usize>,
        visited: &mut Vec<bool>,
        edges: &HashMap<usize, Vec<usize>>,
        subtree_distance_sums: &mut Vec<usize>,
        subtree_sizes: &mut Vec<usize>,
        distance_sums: &mut Vec<usize>
    ) {
        let n = subtree_sizes.len();
        visited[vertex] = true;

        if let Some(p) = parent {
            distance_sums[vertex] = distance_sums[p] - 2 * subtree_sizes[vertex] + n;
        } else {
            distance_sums[vertex] = subtree_distance_sums[vertex];
        }

        for &neighbour in edges.get(&vertex).unwrap_or(&vec![]).iter() {
            if visited[neighbour] {
                continue;
            }

            Self::reroot_visit(neighbour, Some(vertex), visited, edges, subtree_distance_sums, subtree_sizes, distance_sums);
        }
    }
}

public class Solution
{
    public int MinOperations(int[] nums, int k)
    {
        int xor = nums[0];
        for (int i = 1; i < nums.Length; i++)
        {
            xor ^= nums[i];
        }
        xor ^= k;

        int result = 0;
        while (xor > 0)
        {
            xor &= xor - 1;
            result++;
        }

        return result;
    }
}

var minOperations = function(nums, k) {
    for (const i of nums) {
        k ^= i;
    }
    return [...k.toString(2)].filter(it => it === '1').length;
};

impl Solution {
    pub fn min_operations(nums: Vec<i32>, k: i32) -> i32 {
        let diff = k ^ nums.into_iter().reduce(|a, b| a ^ b).unwrap_or(0);
        diff.count_ones() as i32
    }
}

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        result = 0
        xor = 0
        for num in nums:
            xor ^= num
        
        while xor > 0 or k > 0:
            if xor & 1 != k & 1:
                result += 1
            xor >>= 1
            k >>= 1
        
        return result

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        xorN = 0
        for i in nums:
            xorN ^= i
       
        xorN ^= k
        res = 0
        while xorN != 0:
            xorN = (xorN & (xorN - 1))
            res += 1
        return res

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        return reduce(xor, nums, k).bit_count()

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        binaryNums = [format(x, 'b') for x in nums]
        countMap = {}
        maxSize = 0
        for binaryNum in binaryNums:
            size = len(binaryNum)
            if size > maxSize:
                maxSize = size
            for idx in range(size):
                if binaryNum[size - idx - 1] == '1':
                    countMap[idx] = countMap.get(idx, 0) + 1
        binaryK = format(k, 'b')
        size = len(binaryK)
        result = 0
        for idx in range(size):
            if int(binaryK[size - idx - 1]) != countMap.get(idx, 0) % 2:
                result += 1
        for idx in range(size, maxSize):
            if countMap.get(idx, 0) % 2:
                result += 1
        return result

return reduce(lambda acc, x: acc ^ x, nums, k).bit_count()

class Solution {
    public int minOperations(int[] nums, int k) {
        for (int num : nums) {
            k = k ^ num;
        }
        return Integer.bitCount(k);
    }
}

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        tmp = 0
        for num in nums:
            tmp = tmp ^ num # ^ is bitwise XOR
            
        tmp = tmp ^ k
        
        count = 0
        while tmp != 0:
            count += tmp % 2
            tmp //= 2
            
        return count