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

function maxDistance(grid: number[][]): number {

    const directions: number[][] = [[-1, 0], [0, -1], [1, 0], [0, 1]]

    const isVisited = Array.from(Array(grid.length), () =>
        Array(grid.length).fill(false)
    );
    const queue: number[][] = [];
    for (let row = 0; row < grid.length; row++) {
        for (let col = 0; col < grid[0].length; col++) {
            if (grid[row][col] === 1) {
                queue.push([row, col]);
                isVisited[row][col] = true;
            }
        }
    }

    let dis = -1;
    while (queue.length > 0) {
        const currentLength = queue.length;

        for (let i = 0; i < currentLength; i++) {
            const [x, y] = queue.shift();

            for (const direction of directions) {
                const row = x + direction[0];
                const col = y + direction[1];
                if (row >= 0 && col >= 0 && row < grid.length && col < grid[0].length && !isVisited[row][col]
                ) {
                    queue.push([row, col]);
                    isVisited[row][col] = true;
                }
            }
        }
        dis++;
    }

    return dis === 0 ? -1 : dis;

};

/**
 * @param {number} n
 * @param {number[][]} redEdges
 * @param {number[][]} blueEdges
 * @return {number[]}
 */
var shortestAlternatingPaths = function(n, redEdges, blueEdges) {
    const nb = Array.from({ length: n }, () => [[], []]);
    const vis = Array.from({ length: n }, () => [false, false]);
    const ans = Array.from({ length: n }, () => Infinity);

    for (const [u, v] of redEdges) {
        nb[u][0].push(v);
    }

    for (const [u, v] of blueEdges) {
        nb[u][1].push(v);
    }

    const q = new Queue();
    q.enqueue([0, 0, 0]);
    q.enqueue([0, 1, 0]);
    while (!q.isEmpty()) {
        const [node, color, distance] = q.dequeue();
        if (vis[node][color]) {
            continue;
        }
        vis[node][color] = true;
        ans[node] = Math.min(ans[node], distance);
        for (const next of nb[node][color]) {
            q.enqueue([next, color ^ 1, distance + 1]);
        }
    }

    return ans.map(it => it === Infinity ? -1 : it);
};

public class Solution {
    public int[] ShortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
         var result = new int[n];
        for (int i = 0; i < n; i++)
        {
            result[i] = -1;
        }
        var graph = new List<List<Tuple<int, Color>>>(n);
        for (int i = 0; i < n; i++)
        {
            graph.Add(new List<Tuple<int, Color>>());
        }

        foreach (var edge in redEdges)
        {
            graph[edge[0]].Add(new Tuple<int, Color>(edge[1], Color.Red));
        }
        
        foreach (var edge in blueEdges)
        {
            graph[edge[0]].Add(new Tuple<int, Color>(edge[1], Color.Blue));
        }

        var queue = new Queue<Tuple<int, Color>>();
        queue.Enqueue(new Tuple<int, Color>(0, Color.White));
        var step = 0;
        while (queue.Count > 0)
        {
            var queueCount = queue.Count;
             for (int _ = 0; _ < queueCount; _++)
            {
                var item = queue.Dequeue();
                var prevColor = item.Item2;
                if (result[item.Item1] == -1)
                    result[item.Item1] = step;
                for (int i = 0; i < graph[item.Item1].Count; i++)
                {
                    var edgeColor = graph[item.Item1][i];
                    if (edgeColor.Item1 == -1 || edgeColor.Item2 == prevColor)
                        continue;
                    queue.Enqueue(new Tuple<int, Color>(edgeColor.Item1, edgeColor.Item2));
                    graph[item.Item1][i] = new Tuple<int, Color>(-1, edgeColor.Item2);
                }
            }
            step++;
        }
        return result;
    }
}

public enum Color
{
    White = 0,
    Red = 1,
    Blue = 2
}

function shortestAlternatingPaths(n: number, redEdges: number[][], blueEdges: number[][]): number[] {
    const adj: Map<number, number[][]> = new Map()
    // create map: {node: [(neighbor, color)]}, 0 as red, 1 as blue
    for (const redEdge of redEdges) {
        if (adj.has(redEdge[0])) {
            const value = adj.get(redEdge[0]);
            value.push([redEdge[1], 0]);
            adj.set(redEdge[0], value)
        } else {
            adj.set(redEdge[0], [[redEdge[1], 0]])
        }
    }

    for (const blueEdge of blueEdges) {
        if (adj.has(blueEdge[0])) {
            const value = adj.get(blueEdge[0]);
            value.push([blueEdge[1], 1]);
            adj.set(blueEdge[0], value)
        } else {
            adj.set(blueEdge[0], [[blueEdge[1], 1]])
        }
    }


    // create an array with -1 is the default value
    const answer: number[] = new Array(n).fill(-1);
    answer[0] = 0;

    // create an aray visit: [(neighbor, color)]
    const visit = Array.from({ length: n }, () => Array(2).fill(false))
    visit[0][1] = true, visit[0][0] = true;

    // create a queue: [(currentNode, takenStepsToVisit, colorOfPreviousEdge]
    let queue: number[][] = [[0, 0, -1]];

    while (queue.length > 0) {
        //visit currend node and remove node out of queue
        const [currentNode, takenStepsToVisit, colorOfPreviousEdge] = queue.shift();

        if (!adj.has(currentNode)) {
            continue;
        }
        // visit adjacent nodes
        for (const [neighbor, color] of adj.get(currentNode)) {
            // if node has not been visited and color is not the same as the previous one push it to the queue
            if (!visit[neighbor][color] && color !== colorOfPreviousEdge) {
                if (answer[neighbor] === -1)
                    answer[neighbor] = 1 + takenStepsToVisit;
                visit[neighbor][color] = true;
                queue.push([neighbor, 1 + takenStepsToVisit, color]);
            }
        }
    }
    return answer;
};

class Solution {
    pair<int, int> dfs(vector<vector<int>> &g, int current, int parent, long long &ret, int seats) {
        int total_persons = 1, cars, per;
        for (auto next: g[current]) {
            if (next == parent) continue;
            tie(cars, per) = dfs(g, next, current, ret, seats);
            ret += cars;
            total_persons += per;
        }

        int new_cars = (total_persons % seats == 0)?(total_persons / seats):(total_persons / seats + 1);

        return make_pair(new_cars, total_persons);
    }

public:
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        int n = roads.size() + 1;
        vector<vector<int>> g(n);
        for (auto& r: roads) {
            g[r[0]].push_back(r[1]);
            g[r[1]].push_back(r[0]);
        }

        long long ret = 0;
        dfs(g, 0, -1, ret, seats);
        return ret;
    }
};

/**
 * @param {number[][]} roads
 * @param {number} seats
 * @return {number}
 */
var minimumFuelCost = function(roads, seats) {
    const nb = Array.from({ length: roads.length + 2 }, () => []);
    for (const [u, v] of roads) {
        nb[u].push(v);
        nb[v].push(u);
    }

    const dfs = (node, parent) => {
        let cost = 0, people = 1;
        for (const child of nb[node]) {
            if (child === parent) {
                continue;
            }

            const [childCost, childPeople] = dfs(child, node);
            cost += childCost;
            people += childPeople;
        }

        return [cost + (node === 0 ? 0 : Math.ceil(people / seats)), people];
    };

    return dfs(0, -1)[0];
};

function minimumFuelCost(roads: number[][], seats: number): number {
    let fuel = 0;
    const adj: Map<number, number[]> = new Map();
    // Store adjacent nodes
    for (const road of roads) {
        if (adj.has(road[0])) {
            const value = adj.get(road[0]);
            value.push(road[1]);
            adj.set(road[0], value)
        } else {
            adj.set(road[0], [road[1]])
        }

        if (adj.has(road[1])) {
            const value = adj.get(road[1]);
            value.push(road[0]);
            adj.set(road[1], value)
        } else {
            adj.set(road[1], [road[0]])
        }
    }
    // perform dfs traversal

    const dfs = (node: number, parent: number, adj: Map<number, number[]>, seats: number) => {
        let representatives = 1;
        if (!adj.has(node)) {
            return representatives;
        }
        for (const child of adj.get(node)) {
            if (child != parent) {
                representatives += dfs(child, node, adj, seats);
            }
        }
        if (node !== 0) {
            fuel += Math.ceil(representatives / seats);
        }
        return representatives;
    }

    dfs(0, -1, adj, seats);
    return fuel;
};

class Solution {
    private long ans = 0;
    public long minimumFuelCost(int[][] roads, int seats) {
        HashMap<Integer, ArrayList<Integer>> adj = new HashMap<>();
        for(int[] node : roads){
            adj.computeIfAbsent(node[0], key -> new ArrayList<>()).add(node[1]);
            adj.computeIfAbsent(node[1], key -> new ArrayList<>()).add(node[0]);
        }
        this.dfs(0, -1, adj, seats);
        return this.ans;
    }
    public int dfs(int curr, int parent, HashMap<Integer, ArrayList<Integer>> adj, int seats){
        int current_rep = 1;
        if(adj.get(curr) == null){
            return current_rep;
        }
        for(Integer i : adj.get(curr)){
            if(i.equals(parent)){
                continue;
            }
            current_rep += dfs(i, curr, adj, seats);
        }
        if(curr != 0){
            this.ans += (int)Math.ceil((double)current_rep / seats);
        }
        return current_rep;
    }
}

class Solution:
    def __init__(self):
        self.ans = 0

    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        adj = defaultdict()
        for node in roads:
            adj.setdefault(node[0], []).append(node[1])
            adj.setdefault(node[1], []).append(node[0])
        self.dfs(0, -1, adj, seats)
        return self.ans
    
    def dfs(self, curr, parent, adj, seats) -> int:
        current_rep = 1
        if curr >= len(adj):
            return current_rep
        for i in adj[curr]:
            if i == parent:
                continue
            current_rep += self.dfs(i, curr, adj, seats)
        if curr != 0:
            self.ans += math.ceil(current_rep / seats)
        return current_rep

class Solution {
    int dimension;
    int maxCapacity;
    int[] capacity;
    int[] parent;
    List<Integer>[] adjList;
    int[] distance;
    boolean[] visited;
    List<Integer> leafNodes;
    long totalCost;


    public long minimumFuelCost(int[][] roads, int seats) {
        initialize(roads, seats);
        calculatePath();
        bfs();
        return totalCost;
    }

    private void bfs() {
        // reinit visited
        visited = new boolean[dimension];
        visited[0] = true;
        // element is node and height
        // element with bigger height should be processed first
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[1] - o1[1];
            }
        });
//        LinkedList<Integer> queue = new LinkedList<>();
        leafNodes.forEach(node -> {
            visited[node] = true;
            queue.offer(new int[]{node, distance[node]});
        });
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int currNode = curr[0];
            // if some child is not processed, we should not process parent
            boolean isGoodToGo = true;
                int currCapacity = capacity[currNode];
                // if current capacity is more than maxCapacity, it means there are more guests than seats, we need to add cost for max capacity
                while (currCapacity > maxCapacity) {
                    totalCost += distance[currNode];
                    currCapacity -= maxCapacity;
                }
                if (currNode != 0) totalCost++;

                int parentNode = parent[currNode];
                capacity[parentNode] += currCapacity;
                if (!visited[parentNode]) {
                    visited[parentNode] = true;
                    queue.offer(new int[]{parentNode, distance[parentNode]});
                }
        }
    }

    private void calculatePath() {
        dfs(0, 0, 0);
    }

    private void dfs(int parentNode, int node, int weight) {
        visited[node] = true;
        distance[node] = weight;
        parent[node] = parentNode;
        List<Integer> unvisitedNode = adjList[node].stream().filter(i -> !visited[i]).toList();
        if (unvisitedNode.isEmpty()) {
            leafNodes.add(node);
        } else {
            unvisitedNode.forEach(i -> dfs(node, i, weight + 1));
        }
    }

    private void initialize(int[][] roads, int seats) {
        // initialize adjacency list
        dimension = roads.length + 1;
        adjList = new ArrayList[dimension];
        IntStream.range(0, dimension).forEach(i -> adjList[i] = new ArrayList<>());
        IntStream.range(0, dimension - 1).forEach(i -> {
            int from = roads[i][0];
            int to = roads[i][1];
            adjList[from].add(to);
            adjList[to].add(from);
        });

        distance = new int[dimension];
        visited = new boolean[dimension];
        leafNodes = new ArrayList<>();
        this.maxCapacity = seats;
        totalCost = 0L;
        capacity = new int[dimension];
        IntStream.range(0, dimension).forEach(i -> capacity[i] = 1);
        parent = new int[dimension];
    }
}

function minimumFuelCost(roads: number[][], seats: number): number {
    let graph = Array(roads.length+1).fill(null);
    graph = graph.map(() => {return [] })
    for (let road of roads){
        graph[road[0]].push(road[1]);
        graph[road[1]].push(road[0]);
    }
    let result = 0 ;
    function dfs(node , parent){
        let people = 1;
        for(let child of graph[node]){
            if (child === parent) continue;
            people += dfs(child , node);
        }
        if(node != 0)
            result += Math.ceil(people/seats);
        return people;
    }
    dfs(0 , -1);
    return result;
};