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

class Solution:
    def minimumCost(self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int:
        
        @lru_cache(None)
        def dp(x0, y0, x1, y1):
            if x1 - x0 == 1 and y1 - y0 == 1:
                return 0
            
            res = 10**9
            for x in range(x0, x1-1):
                res = min(res, dp(x0, y0, x+1, y1) + dp(x+1, y0, x1, y1) + horizontalCut[x])
            
            for y in range(y0, y1-1):
                res = min(res, dp(x0, y0, x1, y+1) + dp(x0, y+1, x1, y1) + verticalCut[y])
            
            return res
        
        return dp(0, 0, m, n)

class Solution {
public:
    int findChampion(int n, vector<vector<int>>& edges) {
        unordered_set<int> cnt;
        for (int i = 0; i < n; i++) {
            cnt.insert(i);
        }
        for (auto& edge : edges) {
            if (cnt.find(edge[1]) != cnt.end()) {
                cnt.erase(edge[1]);
            }
        }
        if (cnt.size() == 0 || cnt.size() >= 2) return -1;
        return *cnt.begin();
    }
};

class Solution {

    /**
     * @param Integer $n
     * @param Integer[][] $edges
     * @return Integer
     */
    function findChampion($n, $edges) {
        if ($n == 1 && count($edges) == 0) return 0;

        $winners = [];
        $losers = [];

        foreach ($edges as $e) {
            $w = $e[0];
            $l = $e[1];

            $winners[$w] = $w;
            $losers[$l] = $l;

            if (isset($winners[$l])) {
                $losers[$l] = $l;
                unset($winners[$l]);
            }

            if (isset($losers[$w])) {
                unset($winners[$w]);
            }
        }

        if (count($winners) + count($losers) != $n) return -1;
        
        return count($winners) > 1 ? -1 : end($winners);
    }
}

class Solution:
    def findChampion(self, n: int, edges: List[List[int]]) -> int:
        indegree = [0]*n
        count = n
        for f, t in edges:
            indegree[t] += 1
            if indegree[t] == 1:
                count -= 1

        if count != 1:
            return -1

        for i in range(n):
            if indegree[i] == 0:
                return i

class Solution2924 {
    func findChampion(_ n: Int, _ edges: [[Int]]) -> Int {
        if edges.isEmpty && n <= 1 {
          return 0
        }
        var counter: [Int: Int] = [:]
        for i in 0..<n {
          counter[i, default: 0] += 0
        }
        for edge in edges {
          counter[edge[1], default: 0] += 1
        }

        let f = counter.filter { entry in entry.value == 0 }
        if f.count > 1 {
          return -1
        } else {
          return f.first?.key ?? -1
        }
    }
}

class Solution {
    public int findChampion(int n, int[][] edges) {
        Set<Integer> champ = new HashSet();
        for(int i =0 ; i < n ; i++){
            champ.add(i);
        }
        for(int[] edge:edges){
            int a = edge[0];
            int b = edge[1];
            if(champ.contains(b)){
                champ.remove(b);
            }
        }
        if(champ.size()>1 || champ.size()==0) return-1;
        int ans =-1;
        for(int num:champ){
            ans=num;
        }
        return ans;

    }
}

class Solution:
    def findChampion(self, n: int, edges: List[List[int]]) -> int:
        mp = {}
        for x , y in edges:
            mp[y] = x
        champion = -1
        cnt = 0
        for i in range(n):
            if i not in mp:
                champion = i
                cnt += 1
        return champion if cnt == 1 else -1

var findChampion = function(n, edges) {
    const isWeaker = Array(n).fill(false);
    for (const [u, v] of edges) {
        isWeaker[v] = true;
    }
    const u = isWeaker.indexOf(false), v = isWeaker.lastIndexOf(false);
    return u === v ? u : -1;
};

class Solution:
    def findChampion(self, n: int, edges: List[List[int]]) -> int:
        strongs = set(e for e in range(n))
        for a, b in edges:
            strongs.discard(b)
               
        if len(strongs) == 1:
            return strongs.pop()
       
        return -1

public class Solution {
    public int FindChampion(int n, int[][] edges)
    {
        var res = new bool[n];
        Array.Fill(res, true);
        foreach (var pair in edges)
        {
            res[pair[1]] = false;
        }

        if (res.Count(a => a) > 1) return -1;
        return Array.IndexOf(res, true);
    }
}

var findChampion = function(n, edges) {
    const adjList = new Map();
    for(const [from, to] of edges){
        const currentList = adjList.get(from) ?? [];
        currentList.push(to);
        adjList.set(from, currentList);
    }
    const isBeatable = Array(n).fill(false);
    for(let i = 0; i < n; i++){
        if(isBeatable[i]) continue;
        const queue = [i];
        let level = 0;
        while(queue.length > 0){
            const levelSize = queue.length;
            for(let j = 0; j < levelSize; j++){
                const node = queue.shift();
                if(level > 0) isBeatable[node] = true;
                const adjNodes = adjList.get(node);
                if(!adjNodes) continue;
                for(const adjNode of adjNodes){
                    if(isBeatable[adjNode]) continue;
                    queue.push(adjNode);
                }
            }
            level++;
        }
    }
    let firstUnbeatable = isBeatable.indexOf(false);
    let lastUnbeatable = isBeatable.lastIndexOf(false);
    return firstUnbeatable !== lastUnbeatable ? -1 : firstUnbeatable;
};

class Solution:
    def findChampion(self, n: int, edges: List[List[int]]) -> int:
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)

        def bfs(node):
            cnt = 0
            q = deque([node])
            visited = {node}
            
            while q:
                curr = q.popleft()
                cnt += 1

                for nei in graph[curr]:
                    if nei not in visited:
                        q.append(nei)
                        visited.add(nei)

            return cnt == n
        
        champs = [i for i in range(n) if bfs(i)]
        
        return champs[0] if len(champs) == 1 else -1