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

Multi-source BFS + Max Priority Queue Dijkstra

Code: 
use std::collections::*;
use std::cmp::*;

#[derive(Debug)]
struct Pair {
    indices: (usize, usize),
    safeness: i32
}

impl PartialEq for Pair {
    fn eq(&self, other: &Pair) -> bool {
        self.safeness.eq(&other.safeness)
    }
}

impl Eq for Pair {}

impl PartialOrd<Pair> for Pair {
    fn partial_cmp(&self, other: &Pair) -> Option<Ordering> {
        self.safeness.partial_cmp(&other.safeness)
    }
}

impl Ord for Pair {
    fn cmp(&self, other: &Pair) -> Ordering {
        self.safeness.cmp(&other.safeness)
    }
}

impl Solution {
    // 1. Use modified BFS to find min distance to any thief.
    // 2. Use modified Dijkstra to find max safeness factor of paths to (n - 1, n- 1).
    pub fn maximum_safeness_factor(mut grid: Vec<Vec<i32>>) -> i32 {
        let n = grid.len();
        let mut queue = VecDeque::new();

        for i in 0..n {
            for j in 0..n {
                if grid[i][j] == 1 {
                    queue.push_back((i, j));
                }
            }
        }

        while let Some((i, j)) = queue.pop_front() {
            if i > 0 && grid[i - 1][j] == 0 {
                grid[i - 1][j] = grid[i][j] + 1;
                queue.push_back((i - 1, j));
            }

            if j < n - 1 && grid[i][j + 1] == 0 {
                grid[i][j + 1] = grid[i][j] + 1;
                queue.push_back((i, j + 1));
            }

            if i < n - 1 && grid[i + 1][j] == 0 {
                grid[i + 1][j] = grid[i][j] + 1;
                queue.push_back((i + 1, j));
            }

            if j > 0 && grid[i][j - 1] == 0 {
                grid[i][j - 1] =  grid[i][j] + 1;
                queue.push_back((i, j - 1));
            }
        }

        let mut max_heap = BinaryHeap::new();
        let mut estimates = vec![vec![i32::MAX; n]; n];
        estimates[0][0] = grid[0][0];

        max_heap.push(
            Pair {
                indices: (0, 0),
                safeness: estimates[0][0]
            }
        );

        while let Some(
            Pair {
                indices: (i, j),
                safeness: safeness
            }
        ) = max_heap.pop() {
            if safeness < estimates[i][j] {
                continue;
            }

            if i == n - 1 && j == n - 1 {
                return safeness - 1;
            }

            if i > 0 && estimates[i - 1][j] == i32::MAX {
                estimates[i - 1][j] = estimates[i][j].min(grid[i - 1][j]);

                max_heap.push(
                    Pair {
                        indices: (i - 1, j),
                        safeness: estimates[i - 1][j]
                    }
                );
            }

            if j < n - 1 && estimates[i][j + 1] == i32::MAX {
                estimates[i][j + 1] = estimates[i][j].min(grid[i][j + 1]);

                max_heap.push(
                    Pair {
                        indices: (i, j + 1),
                        safeness: estimates[i][j + 1]
                    }
                );
            }

            if i < n - 1 && estimates[i + 1][j] == i32::MAX {
                estimates[i + 1][j] = estimates[i][j].min(grid[i + 1][j]);

                max_heap.push(
                    Pair {
                        indices: (i + 1, j),
                        safeness: estimates[i + 1][j]
                    }
                );
            }

            if j > 0 && estimates[i][j - 1] == i32::MAX {
                estimates[i][j - 1] = estimates[i][j].min(grid[i][j- 1]);

                max_heap.push(
                    Pair {
                        indices: (i, j - 1),
                        safeness: estimates[i][j - 1]
                    }
                );
            }
        }

        -1
    }
}

Code: 
use std::collections::*;
use std::cmp::*;
#[derive(Debug)]
struct Pair {
    indices: (usize, usize),
    safeness: i32
}
impl PartialEq for Pair {
    fn eq(&self, other: &Pair) -> bool {
        self.safeness.eq(&other.safeness)
    }
}
impl Eq for Pair {}
impl PartialOrd<Pair> for Pair {
    fn partial_cmp(&self, other: &Pair) -> Option<Ordering> {
        self.safeness.partial_cmp(&other.safeness)
    }
}
impl Ord for Pair {
    fn cmp(&self, other: &Pair) -> Ordering {
        self.safeness.cmp(&other.safeness)
    }
}
impl Solution {
    // 1. Use modified BFS to find min distance to any thief.
    // 2. Use modified Dijkstra to find max safeness factor of paths to (n - 1, n- 1).
    pub fn maximum_safeness_factor(mut grid: Vec<Vec<i32>>) -> i32 {
        let n = grid.len();
        let mut queue = VecDeque::new();
        let in_bounds = |r, c| { r < n && c < n};
        for i in 0..n {
            for j in 0..n {
                if grid[i][j] == 1 {
                    queue.push_back((i, j));
                }
            }
        }
        while let Some((i, j)) = queue.pop_front() {
            let neighbours = [(i - 1, j), (i, j + 1), (i + 1, j), (i, j - 1)];
            for (r, c) in neighbours {
                if in_bounds(r, c) && grid[r][c] == 0 {
                    grid[r][c] = grid[i][j] + 1;
                    queue.push_back((r, c));
                }
            }
        }
        let mut max_heap = BinaryHeap::new();
        let mut estimates = vec![vec![i32::MAX; n]; n];
        estimates[0][0] = grid[0][0];
        max_heap.push(
            Pair {
                indices: (0, 0),
                safeness: estimates[0][0]
            }
        );
        while let Some(
            Pair {
                indices: (i, j),
                safeness: safeness
            }
        ) = max_heap.pop() {
            if i == n - 1 && j == n - 1 {
                return safeness - 1;
            }
            let neighbours = [(i - 1, j), (i, j + 1), (i + 1, j), (i, j - 1)];
            for (r, c) in neighbours {
                if in_bounds(r, c) && estimates[r][c] == i32::MAX {
                    estimates[r][c] = estimates[i][j].min(grid[r][c]);
                    max_heap.push(
                        Pair {
                            indices: (r, c),
                            safeness: estimates[r][c]
                        }
                    );
                }
            }
        }
        -1
    }
}
 
Last edited:
C++: 
    bool evaluateTree(TreeNode* root) {
        switch(root->val) {
            case 0: case 1: return root->val == 1;
            case 2: return evaluateTree(root->left) || evaluateTree(root->right);
            case 3: return evaluateTree(root->left) && evaluateTree(root->right);
        }
        return false;
    }
 
JavaScript: 
var evaluateTree = function(root) {
    var dfs = function (node) {
        if (!node.left && !node.right) return node.val;

        if (node.val == 2)
            return dfs(node.left) || dfs(node.right);
        else
            return dfs(node.left) && dfs(node.right);
    }

    return dfs(root);
};
 
C#: 
public class Solution
{
    public bool EvaluateTree(TreeNode root)
    {
        if (root.left == null && root.right == null)
        {
            return root.val == 1;
        }

        if (root.val == 2)
        {
            return EvaluateTree(root.left) | EvaluateTree(root.right);
        }

        return EvaluateTree(root.left) & EvaluateTree(root.right);
    }
}
Code:
 
Ez thiệt
JavaScript: 
function evaluateTree(root: TreeNode | null): boolean {
    const go = (node: TreeNode) => {
        if (!node) return false;
        if (!node.left && !node.right) return node.val;
        else return node.val === 2 ? go(node.left) || go(node.right) : go(node.left) && go(node.right)
    }
    return go(root);
};
 
Python: 
# 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
class Solution:
    def evaluateTree(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return False

        if root.val == 0:
            return False
        elif root.val == 1:
            return True
       
        # If the node is a non-leaf node, evaluate its children
        left_result = self.evaluateTree(root.left)
        right_result = self.evaluateTree(root.right)

        if root.val == 2:
            # Node represents OR operation
            return left_result or right_result
        elif root.val == 3:
            # Node represents AND operation
            return left_result and right_result
 
Java: 
class Solution {
    public boolean evaluateTree(TreeNode root) {
        if(root.left==null) return root.val==1?true:false;
        if(root.val==2) return (evaluateTree(root.left)|| evaluateTree(root.right));
        else return (evaluateTree(root.left)&& evaluateTree(root.right));
    }
}
 
C++: 
class Solution {
public:
  bool evaluateTree(TreeNode *root) {
    if (root->val == 2)
      return evaluateTree(root->left) || evaluateTree(root->right);
    if (root->val == 3)
      return evaluateTree(root->left) && evaluateTree(root->right);
    return root->val;
  }
};
 
PHP: 
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class Solution {

    /**
     * @param TreeNode $root
     * @return Boolean
     */
    function evaluateTree($root) {
        switch ($root->val) {
            case 2:
                return $this->evaluateTree($root->left) || $this->evaluateTree($root->right);
                break;
            case 3:
                return $this->evaluateTree($root->left) && $this->evaluateTree($root->right);
                break;
            default:
                return (boolean)$root->val;
        }
    }
}
 
C++: 
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool evaluateTree(TreeNode* root) {
        if(root -> left == NULL && root -> right == NULL) return root -> val;
        if(root -> val == 2) return evaluateTree(root->left) || evaluateTree(root->right);
        return evaluateTree(root->left) && evaluateTree(root->right);
    }
};
 
Python: 
class Solution:
    def evaluateTree(self, root: Optional[TreeNode]) -> bool:
        if root.val < 2:
            return root.val == 1
        
        left = self.evaluateTree(root.left)
        if (root.val == 2 and left == True) or (root.val == 3 and left == False):
            return left
        
        return self.evaluateTree(root.right)
 
tuevi_abcxyz said:
Python: 
# 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
class Solution:
    def evaluateTree(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return False

        if root.val == 0:
            return False
        elif root.val == 1:
            return True
      
        # If the node is a non-leaf node, evaluate its children
        left_result = self.evaluateTree(root.left)
        right_result = self.evaluateTree(root.right)

        if root.val == 2:
            # Node represents OR operation
            return left_result or right_result
        elif root.val == 3:
            # Node represents AND operation
            return left_result and right_result
Click to expand...
ko cần đệ quy tiếp ở nhánh phải trong TH nhánh trái True và phép Or, hay false và phép And.
 
Easy recursion
Python: 
class Solution:
    def evaluateTree(self, root: Optional[TreeNode]) -> bool:
        operatorMap = {
            2: lambda a, b: a or b,
            3: lambda a, b: a and b
        }
        def dfs(root):
            if not root.left and not root.right:
                return bool(root.val)
            operator = operatorMap[root.val]
            return operator(dfs(root.left), dfs(root.right))
        
        return dfs(root)
 
Iterative post-order
Python: 
class Solution:
    def evaluateTree(self, root: Optional[TreeNode]) -> bool:
        operatorMap = {
            2: lambda a, b: a or b,
            3: lambda a, b: a and b
        }
        
        st = [root]
        resultMap = {}
        while st:
            node = st[-1]
            # a leaf
            if not node.left:
                resultMap[node] = bool(node.val)
                st.pop()
                continue

            #the node's children have not been evaluated yet
            if node.left not in resultMap:
                st.append(node.right)
                st.append(node.left)
                continue
            
            #the node's children have been evaluated
            nodeOperator = operatorMap[node.val]
            resultMap[node] = nodeOperator(resultMap.pop(node.left), resultMap.pop(node.right))
            st.pop()

        return resultMap[root]
 
Python: 
# 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
class Solution:
    def evaluateTree(self, root: Optional[TreeNode]) -> bool:
        if root.val == 1: return True
        if root.val == 0: return False
        left , right = False , False
        if root.left: left = self.evaluateTree(root.left)
        if root.right: right = self.evaluateTree(root.right)

        if left == right:return left
       
        if root.val == 3: return False

        return True

:ah:
 
C++: 
class Solution {
public:
    bool evaluateTree(TreeNode* root) {
      if(!root->left && !root->right) return root->val;
      if(root->val == 2) return (evaluateTree(root->left) || evaluateTree(root->right));
      else return (evaluateTree(root->left) && evaluateTree(root->right));
    }
};
 
Java: 
class Solution {
    public boolean evaluateTree(TreeNode root) {
        if (root.left == null && root.right == null) return root.val == 1;
        if (root.val == 2) return evaluateTree(root.left) || evaluateTree(root.right);
        return evaluateTree(root.left) && evaluateTree(root.right);
    }
}
 
C#: 
/
public class Solution {
    public void PostOrder(TreeNode root)
    {
        if(root.left != null)
            PostOrder(root.left);
        if(root.right != null)
            PostOrder(root.right);
        if(root.val == 2)
        {
            if(root.left.val == 1 || root.right.val == 1)
                root.val = 1;
            else
                root.val = 0;
        }
        else if(root.val == 3)
        {
            if(root.left.val == 1 && root.right.val == 1)
                root.val = 1;
            else
                root.val = 0;
        }
    }
    public bool EvaluateTree(TreeNode root) {
        PostOrder(root);
        if(root.val == 0)
            return false;
        else
            return true;
    }
}
 
Ăn ngay cái edge case node là target, còn hơi non :ah:
Python: 
# 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
class Solution:
    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:
        def dfs(node):
            if node == None:
                return False

            if dfs(node.left):
                node.left = None

            if dfs(node.right):
                node.right = None

            if node.left == None and node.right == None and node.val == target:
                return True

        dummy = TreeNode(-1, root)
        dfs(dummy)
        return dummy.left
 
Python: 
class Solution:
    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:
        

        def canRemove(node, target):
            return node.left is None and node.right is None and node.val == target
        
        def dfs(parent, curr, isLeft, target):
            if curr is None:
                return
            
            dfs(curr, curr.left, True, target)
            dfs(curr, curr.right, False, target)
            if canRemove(curr, target):
                if isLeft:
                    parent.left = None
                else:
                    parent.right = None
        
        dfs(root, root.left, True, target)
        dfs(root, root.right, False, target)
        if canRemove(root, target):
            return None

        return root
 

Similar threads

Duy1122
kiến thức Phân biệt Encrypt và Hashing
Replies
15
Views
797
langdangbendoi
langdangbendoi
Xuan Ha Thu Dong
thảo luận [Review] Cuộc sống và công việc Dev ở Hà Lan. Làm thế nào để tìm việc ở HL và châu Âu nói chung?
4 5 6
Replies
101
Views
8K
Willas
Willas
hatayquelua
thắc mắc Cần kiến thức gì để được nhận thực tập Dev
3 4 5
Replies
87
Views
5K
BaoC3H1
BaoC3H1
freezer0604
  • Locked
Động lực để 'phượt' mỗi ngày gần 30, 40 km đến công ty làm việc
13 14 15
Replies
288
Views
20K
yb123123
yb123123
MasterchiefsReborn
Tác dụng bất ngờ của việc đi chân trần mỗi ngày
Replies
18
Views
1K
Nacuto
Nacuto

Share this page

Back
Top