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

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        res = []
        def dfs(node):
            if not node: return
            for c in node.children:
                dfs(c)
            res.append(node.val)
        
        dfs(root)
        return res

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        if not root: return []
        res = []
        stack = [root]
        while stack:
            node = stack.pop()
            res.append(node.val)
            for c in node.children: stack.append(c)
        res.reverse()
        return res

class Solution {
    public List<Integer> postorder(Node root) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        Stack<Node> stack = new Stack<Node>();
        if(root!=null)
            stack.add(root);
        while(!stack.isEmpty()){
            Node node = stack.peek();
            if(node.children!= null){
                List<Node> children= node.children;
                for(int i = children.size()-1;i>=0;i--){
                    stack.add(children.get(i));
                }
                node.children = null;
            }else
                list.add(stack.pop().val);
        }
        return list;
    }   
}

class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> list = new ArrayList<>();
        if (root == null)
            return list;
        
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty())
        {
            Node node = stack.pop();
            list.add(node.val);
            for (Node child : node.children)
                stack.push(child);
        }
        
        Collections.reverse(list);
        return list;
    }
}

class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        
        postorderHelper(root, result);
        return result;
    }
    
    private void postorderHelper(Node node, List<Integer> result) {
        if (node == null) return;

        for (Node child : node.children) {
            postorderHelper(child, result);
        }

        result.add(node.val);
    }
}

impl Solution {
    pub fn postorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        if let Some(root) = root {
            let [a, b] = &mut [Vec::new(), Vec::new()];
            a.push(root);

            while let Some(ref node) = a.pop() {
                b.push(Rc::clone(node));
                if let Some(ref left) = node.borrow().left {
                    a.push(Rc::clone(left));
                }
                if let Some(ref right) = node.borrow().right {
                    a.push(Rc::clone(right));
                }
            }
            b.reverse();
            b.into_iter().map(|node| node.borrow().val).collect()
        } else {
            Vec::new()
        }
    }
}

def postorder(node)
    stack = [node]
    result = []

    return result if node.nil?

    while !stack.empty? do
        top = stack.pop
        result.push(top.val)

        for child in top.children
            stack.push(child)
        end
    end

    result.reverse
end

function maxProbability(n: number, edges: number[][], succProb: number[], start: number, end: number): number {
    const adjList = {};
    const dists = new Array(n).fill(Number.MIN_SAFE_INTEGER);
    
    for (let i = 0; i < n; i++) {
        adjList[i] = [];
    }
    
    for (let i = 0; i < edges.length; i++) {
        const [u, v] = edges[i];
        const weight = succProb[i];
        
        adjList[u].push([v, weight]);
        adjList[v].push([u, weight]);
    }
    
    const maxHeap = new MaxPriorityQueue({ priority: x => x[1] });
    
    maxHeap.enqueue([ start, 1 ]);
    
    while (!maxHeap.isEmpty()) {
        const [ node, prob ] = maxHeap.dequeue().element;
        if (node === end) return prob;
        if (dists[node] > prob) continue;
        for (const [nei, weight] of adjList[node]) {
            if (prob * weight > dists[nei]) {
                dists[nei] = prob * weight;
                maxHeap.enqueue([nei, dists[nei]]);
            }
        }
    }
    
    return 0;
};

class Solution:
    def maxProbability(self, N: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:
        n = len(edges)
        graph = defaultdict(list)
        for i in range(n):
            f, t = edges[i]
            graph[f].append((t, succProb[i]))
            graph[t].append((f, succProb[i]))
        pq = [(-1, start_node)]
        probs = [0]*N
        probs[start_node] = 1
        while pq:
            prob, vertex = heapq.heappop(pq)
            prob*=-1
            if vertex == end_node:
                return prob
            if prob < probs[vertex]:
                continue
        
            for neighbor, neighborProb in graph[vertex]:
                newProb = neighborProb*prob
                if newProb > probs[neighbor]:
                    probs[neighbor] = newProb
                    heapq.heappush(pq, (newProb*-1, neighbor))
        return 0

class Solution:
    def maxProbability(self, N: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:
        n = len(edges)
        graph = defaultdict(list)
        for i in range(n):
            s , e = edges[i]
            graph[s].append((succProb[i]  , e))
            graph[e].append((succProb[i]  , s))

        queue = [(-1.0 , start_node)]
        path = [0] * N
        path[start_node] = 1
        while queue:
            prob , node = heapq.heappop(queue)
            prob *= -1
            if node == end_node: return prob
            if prob < path[node]: continue

            for next_prob , nei in graph[node]:
                new_prob = next_prob * prob
                if new_prob > path[nei]:
                    path[nei] = new_prob
                    heapq.heappush(queue , (new_prob * -1 , nei))
        
        return path[end_node] if end_node in path else 0

use std::collections::BinaryHeap;
use std::cmp::Ordering;

#[derive(PartialEq)]
struct NN(f64);

impl Eq for NN {}

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

impl Ord for NN {
    fn cmp(&self, other: &Self) -> Ordering {
        self.partial_cmp(other).unwrap()
    }
}

impl Solution {
    pub fn max_probability(n: i32, edges: Vec<Vec<i32>>, succ_prob: Vec<f64>, start_node: i32, end_node: i32) -> f64 {
        let n = n as usize;
        let mut graph = vec![vec![]; n];

        for (edge, sp) in edges.into_iter().zip(succ_prob.into_iter()) {
            let (u, v) = (edge[0] as usize, edge[1] as usize);

            graph[u].push((v, sp));
            graph[v].push((u, sp));
        }

        let (source, target) = (start_node as usize, end_node as usize);

        let mut distances = vec![0.0; n];
        distances[source] = 1.0;

        let mut queue = BinaryHeap::new();
        queue.push((NN(0.0), source));

        while let Some((NN(estimate), vertex)) = queue.pop() {
            if vertex == target {
                return distances[target];
            }

            if estimate > (1.0 - distances[vertex]) {
                continue;
            }

            for &(neighbour, sp) in &graph[vertex] {
                let old_estimate = (1.0 - distances[neighbour]);
                let estimate_through_vertex = (1.0 - distances[vertex] * sp);

                if estimate_through_vertex < old_estimate {
                    distances[neighbour] = distances[vertex] * sp;

                    queue.push((NN(estimate_through_vertex), neighbour));
                }
            }
        }

        distances[target]
    }
}

class Solution {
    public double maxProbability(int n, int[][] edges, double[] succProb, int start_node, int end_node) {
        double[] min_dist = new double[n];
        min_dist[start_node] =1;
        List<List<double[]>> adjections = new ArrayList();
        for(int i =0 ; i < n ; i++){
            adjections.add(new ArrayList<double[]>());
        }
        int index =0;
        for(int[] edge : edges){
            adjections.get(edge[0]).add(new double[]{edge[1],succProb[index]});
            adjections.get(edge[1]).add(new double[]{edge[0],succProb[index]});
            index++;
        }
        Comparator<double[]> customComparator = new Comparator<double[]>() {
            @Override
            public int compare(double[] d1, double[] d2) {
                // Custom comparison logic (e.g., compare based on the first element)
                return Double.compare(d2[1], d1[1]);
            }
        };
        PriorityQueue<double[]> pq = new PriorityQueue(customComparator);
        pq.offer(new double[]{start_node, 1});
        Set<Integer> visited = new HashSet();
        while(!pq.isEmpty()){
            double[] d = pq.poll();
            int i= (int)d[0];
            while(visited.contains(i) && !pq.isEmpty()){
                d=pq.poll();
                i= (int)d[0];   
            }
            if(visited.contains(i)){
                break;
            }
            visited.add(i);
            double prob = d[1];
            for(double[] adj: adjections.get(i)){
                int j= (int)adj[0];
                double cur_prob = min_dist[j];
                double new_prob = prob* adj[1];
                if(new_prob>cur_prob){
                    min_dist[j]= new_prob;
                    pq.offer(new double[]{j, new_prob});
                }
                
            }
        }
        return min_dist[end_node];
    }
}

class Solution {
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        class Node {
            int node;
            double prob;
            
            Node(int node, double prob) {
                this.node = node;
                this.prob = prob;
            }
        }
        
        List<List<Node>> adjList = new ArrayList<>();
        for (int i = 0; i < n; i++)
            adjList.add(new ArrayList<>());
        for (int i = 0; i < edges.length; i++)
        {
            adjList.get(edges[i][0]).add(new Node(edges[i][1], succProb[i]));
            adjList.get(edges[i][1]).add(new Node(edges[i][0], succProb[i]));
        }
        
        double[] prob = new double[n];
        prob[start] = 1;
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> b.prob < a.prob ? -1 : 1);
        pq.add(new Node(start, prob[start]));
        while (!pq.isEmpty())
        {
            Node cur = pq.poll();
            if (cur.prob < prob[cur.node])
                continue;
            prob[cur.node] = cur.prob;
            for (Node v : adjList.get(cur.node))
                if (cur.prob * v.prob > prob[v.node])
                    pq.add(new Node(v.node, cur.prob * v.prob));
        }
        
        return prob[end];
    }
}