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

impl Solution {
    pub fn balance_bst(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        type Tree = Option<Rc<RefCell<TreeNode>>>;
        fn flatten(tree: &Tree) -> Vec<i32> {
            if let Some(node) = tree {
                let node = node.as_ref().borrow();
                [flatten(&node.left), vec![node.val], flatten(&node.right)].concat()
            } else {
                Vec::new()
            }
        }
        fn deflatten(nums: &[i32]) -> Tree {
            if nums.is_empty() {
                None
            } else {
                let mid = nums.len() / 2;
                Some(Rc::new(RefCell::new(TreeNode {
                    val: nums[mid],
                    left: deflatten(&nums[..mid]),
                    right: deflatten(&nums[mid + 1..]),
                })))
            }
        }

        deflatten(&flatten(&root))
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode balanceBST(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();

        collect(root, list);
        return buildBalanceBST(list, 0, list.size() - 1);
    }

    private void collect(TreeNode node, List<TreeNode> list) {
        if (node == null) return;

        collect(node.left, list);
        list.add(node);
        collect(node.right, list);
    }

    private TreeNode buildBalanceBST(List<TreeNode> list, int left, int right) {
        int mid = (left + right) / 2;

        if (left > right) return null;

        TreeNode root = list.get(mid);

        root.left = buildBalanceBST(list, left, mid - 1);
        root.right = buildBalanceBST(list, mid + 1, right);

        return root;
    }
}

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        for i in edges[0]:
            for j in edges[1]:
                if i == j:
                    return i

function findCenter(edges: number[][]): number {
    const map = new Map();
    for (const [from, to] of edges) {
        map.set(from, (map.get(from) || 0) + 1);
        map.set(to, (map.get(to) || 0) + 1);
    }
    for (const [key, value] of map.entries()) {
        if (value === map.size - 1) return key;
    }
    return -1;
};

class Solution {

    /**
     * @param Integer[][] $edges
     * @return Integer
     */
    function findCenter($edges) {
        $validCount = count($edges);
        $dict = [];
        foreach ($edges as $edge) {
            foreach ($edge as $n) {
                $dict[$n] = isset($dict[$n]) ? $dict[$n]+1 : 1;
                if ($dict[$n] == $validCount) return $n;
            }
        }
    }
}

use std::collections::*;

impl Solution {
    pub fn min_k_bit_flips(nums: Vec<i32>, k: i32) -> i32 {
        let (n, uk) = (nums.len(), k as usize);

        let (mut flip_queue, mut flip_state, mut result) = (VecDeque::new(), 0, 0);

        for (i, num) in nums.into_iter().enumerate() {
            if i >= uk {
                flip_state ^= flip_queue[0];
            }

            if flip_state == num {
                if i + uk > n {
                    return - 1;
                }

                flip_queue.push_back(1);
                flip_state ^= 1;
                result += 1;
            } else {
                flip_queue.push_back(0);
            }

            if flip_queue.len() > uk {
                flip_queue.pop_front();
            }
        }

        result
    }
}

use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    pub fn bst_to_gst(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        type Tree = Rc<RefCell<TreeNode>>;

        fn build_and_sum(node_option: Option<&Tree>, top_right_sum: i32) -> (Option<Tree>, i32) {
            match node_option {
                Some(node) => {
                    let val = node.borrow().val;

                    let mut new_node = TreeNode::new(val);

                    let (new_right, right_sum) =
                        build_and_sum(node.borrow().right.as_ref(), top_right_sum);

                    let (new_left, left_sum) =
                        build_and_sum(node.borrow().left.as_ref(), val + right_sum + top_right_sum);

                    new_node.val += right_sum + top_right_sum;
                    new_node.left = new_left;
                    new_node.right = new_right;

                    (
                        Some(Rc::new(RefCell::new(new_node))),
                        val + left_sum + right_sum
                    )
                },
                None => (None, 0)
            }
        }

        build_and_sum(root.as_ref(), 0).0
    }
}

use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    pub fn balance_bst(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        type Tree = Rc<RefCell<TreeNode>>;
        fn flatten(node_option: Option<&Tree>, vals: &mut Vec<i32>) {
            match node_option {
                Some(node) => {
                    flatten(node.borrow().left.as_ref(), vals);
                    vals.push(node.borrow().val);
                    flatten(node.borrow().right.as_ref(), vals);
                },
                None => ()
            }
            
        }

        fn build_balanced(vals: &[i32]) -> Option<Tree> {
            if vals.len() == 0 {
                return None;
            }

            let mid = vals.len() / 2;

            Some(Rc::new(RefCell::new(TreeNode {
                val: vals[mid],
                left: build_balanced(&vals[..mid]),
                right: build_balanced(&vals[(mid + 1)..])
            })))
        }

        let mut vals = vec![];
        flatten(root.as_ref(), &mut vals);

        build_balanced(&vals)
    }
}

use std::collections::*;

impl Solution {
    pub fn find_center(edges: Vec<Vec<i32>>) -> i32 {
        let mut edge_map = HashMap::new();

        for edge in edges {
            let u = edge[0];
            let v = edge[1];

            edge_map.entry(u).and_modify(|count| *count += 1).or_insert(1);

            edge_map.entry(v).and_modify(|count| *count += 1).or_insert(1);
        }

        let n = edge_map.len();

        for (vertex, count) in edge_map {
            if count == n - 1 {
                return vertex;
            }
        }

        -1
    }
}

impl Solution {
    pub fn find_center(edges: Vec<Vec<i32>>) -> i32 {
        return if edges[0][0] == edges[1][0] || edges[0][0] == edges[1][1] {
            edges[0][0]
        } else {
            edges[0][1]
        }
    }
}

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        for e in edges[0]:
            if e in edges[1]:
                return e

public class Solution {
    public int FindCenter(int[][] edges) {
        int max = 0;
        int result = 0;
        Dictionary<int, int> dict = new Dictionary<int, int>();
        for(int i = 0; i < edges.Length/2 + 1; i++)
        {
            for(int j = 0; j<2; j++)
            {
                if(dict.ContainsKey(edges[i][j]))
                {
                    dict[edges[i][j]]++;
                    if(dict[edges[i][j]] > max)
                        result = edges[i][j];
                }
                else
                {
                    dict.Add(edges[i][j], 1);
                }
            }
        }
        return result;
    }
}

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        mp = {}
        for [s , e] in edges:
            mp[s] = mp.get(s , 0) + 1
            mp[e] = mp.get(e , 0) + 1
       
        for k in mp:
            if mp[k] == len(edges): return k
       
        return -1

class Solution {
    public int findCenter(int[][] edges) {
        int n = edges.length;
        int [] vertexFreq = new int[n+2];
        for(int[] edge:edges){
            vertexFreq[edge[0]]++;
            vertexFreq[edge[1]]++;
        }
        for(int i =1 ; i < n+2;i++){
            if(vertexFreq[i]==n) return i;
        }
        return 1;
    }
}