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

class Solution:

    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:
        adj = defaultdict(list)
        in_deg = Counter()
        out_deg = Counter()

        reversed_path = []

        def dfs(u):
            while len(adj[u]):
                v = adj[u].pop()
                dfs(v)
                reversed_path.append([u, v])

        for u, v in pairs:
            adj[u].append(v)
            out_deg[u] += 1
            in_deg[v] += 1
        
        s = next(iter(out_deg))
        for u in out_deg:
            if in_deg[u] < out_deg[u]:
                s = u

        dfs(s)

        return reversed_path[::-1]

var validArrangement = function (pairs) {
    const edge = {}, deg = {}, chain = [];
    for (const [s, e] of pairs) {
        (edge[s] ??= []).push(e);
        deg[s] = (deg[s] ?? 0) + 1;
        deg[e] = (deg[e] ?? 0) - 1;
        if (!deg[s]) {
            delete deg[s];
        }
        if (!deg[e]) {
            delete deg[e];
        }
    }
    const go = i => {
        while (edge[i]?.length > 0) {
            const j = edge[i].pop();
            go(j);
        }
        chain.push(i);
    };
    let { '1': s, '-1': e } = _.invert(deg);
    go(s >= 0 ? Number(s) : pairs[0][0]);
    const ans = [];
    for (let i = chain.length - 2; i >= 0; i--) {
        ans.push([chain[i + 1], chain[i]]);
    }
    return ans;
};

class Solution {
    public int[][] validArrangement(int[][] pairs) {
        int n = pairs.length, rs[][] = new int[n][2];
        if (n <= 1) return pairs;
        var hml = new HashMap<Integer, List<Integer>>();
        var hm = new HashMap<Integer, Integer>();
        for (var p : pairs) {
            hml.computeIfAbsent(p[0], k -> new ArrayList<>()).add(p[1]);
            hm.merge(p[0], 1, Integer::sum);
            hm.merge(p[1], -1, Integer::sum);
        }
        var beg = pairs[0][0];
        for (var e : hm.entrySet()) {
            if (e.getValue() == 1) {
                beg = e.getKey();
                break;
            }
        }
        var st = new ArrayDeque<Integer>();
        st.push(beg);
        var l = new ArrayList<Integer>();
        while (!st.isEmpty()) {
            int k = st.peek();
            if (hml.containsKey(k) && !hml.get(k).isEmpty()) { st.push(hml.get(k).remove(hml.get(k).size() - 1)); }
            else { l.add(st.pop()); }
        }
        for (int i = 0; i < n; i++) rs[i] = new int[] { l.get(n - i), l.get(n - 1 - i) };
        return rs;
    }
}

class Solution:
    def minimumTime(self, grid: List[List[int]]) -> int:
        if grid[0][1] > 1 and grid[1][0] > 1:
            return -1

        m, n, heap  = len(grid), len(grid[0]), [(0, 0, 0)]
     
        while heap:
            dis, x, y = heappop(heap)
            if (x, y) == (m - 1, n - 1): return dis
            for xx, yy in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                if m > xx > -1 < yy < n and grid[xx][yy] != -1:
                    heappush(heap, (dis + max(0, (grid[xx][yy] - dis) & ~1) + 1, xx, yy))
                    grid[xx][yy] = -1

class Solution:
    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:
        adj = defaultdict(list)
        outDeg, inDeg = defaultdict(int), defaultdict(int)

        for u, v in pairs:
            adj[u].append(v)
            outDeg[u] += 1
            inDeg[v] += 1
        
        stack = []
        for u in adj:
            if inDeg[u] == outDeg[u] - 1:
                stack.append(u)
                break
        if not stack:
            stack.append(pairs[0][0])

        vertexes = []
        while stack:
            u = stack[-1]
            if outDeg[u] == 0:
                vertexes.append(u)
                stack.pop()
            else:
                stack.append(adj[u][outDeg[u] - 1])
                outDeg[u] -= 1
                    
        return [[u, v] for (u, v) in zip(vertexes[:0:-1], vertexes[-2::-1])]