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

class Solution {
    final long MOD = 1_000_000_007;
    public int numberOfStableArrays(int zero, int one, int limit) {
        long[][] dp0 = new long[zero + 1][one + 1];
        long[][] dp1 = new long[zero + 1][one + 1];
        for (int i = 0; i <= Math.min(zero, limit); i++) dp0[i][0] = 1;
        for (int i = 0; i <= Math.min(one, limit); i++) dp1[0][i] = 1;
        for (int i = 1; i <= zero; i++) {
            for (int j = 1; j <= one; j++) {
                if (i > limit) {
                    dp0[i][j] = dp0[i - 1][j] + dp1[i - 1][j] - dp1[i - limit - 1][j];
                } else {
                    dp0[i][j] = dp0[i - 1][j] + dp1[i - 1][j];
                }
                dp0[i][j] = (dp0[i][j] % MOD + MOD) % MOD;
                if (j > limit) {
                    dp1[i][j] = dp0[i][j - 1] + dp1[i][j - 1] - dp0[i][j - limit - 1];
                } else {
                    dp1[i][j] = dp0[i][j - 1] + dp1[i][j - 1];
                }
                dp1[i][j] = (dp1[i][j] % MOD + MOD) % MOD;
            }
        }
        return (int) ((dp0[zero][one] + dp1[zero][one]) % MOD);
    }
}

public class Solution
{
    public int NumberOfStableArrays(int zero, int one, int limit)
    {
        long MOD = 1000000007;
        long[,,] dp = new long[zero + 1, one + 1, 2];
        for(int i=1;i<= Math.Min(zero, limit); i++)
            dp[i, 0, 0] = 1;
        for (int j = 1; j <= Math.Min(one, limit); j++)
            dp[0, j, 1] = 1;
        for(int i=1;i<=zero;i++)
            for(int j=1;j<=one;j++)
            {
                long c0 = MOD + dp[i - 1, j, 0] + dp[i - 1, j, 1];
                if (i>limit)
                {
                    c0 -= dp[i - limit - 1 , j, 1];
                }
                dp[i, j, 0] = c0 % MOD;
                long c1 = MOD + dp[i, j - 1, 0] + dp[i, j - 1, 1];
                if (j>limit)
                {
                    c1 -= dp[i, j - limit - 1 , 0];
                }
                dp[i,j,1]= c1 % MOD;
            }
        return (int)((dp[zero, one, 0] + dp[zero, one, 1]) % MOD);
    }
}

public class Solution {
    public int BitwiseComplement(int n) {
    if(n==0) return 1;
    int mask = 1;
    while (mask <= n)
        mask <<= 1;
    mask -= 1;
    return n ^ mask;
    }
}

class Solution:
    def bitwiseComplement(self, n: int) -> int:
        if n == 0:
            return 1

        temp = n
        length = 0
        while temp > 0:
            length += 1
            temp >>= 1

        return n ^ (2**(length) - 1)

class Solution:
    def bitwiseComplement(self, n: int) -> int:
        number = bin(n)[2:]
        print(number)
        strs = ""
        for i in range(len(number)):
            strs += "0" if number[i] == "1" else "1"
        return int(strs,2)

func bitwiseComplement(n int) int {
    if n == 0 {
        return 1
    }

    sum := 0
    N := n
    for N > 0 {
        sum = sum<<1 + 1
        N >>= 1
    }
    return sum - n
}

function bitwiseComplement(n: number): number {
    if (n === 0) return 1;
    let k = 0, x = n;
    while (x > 0) {
        x>>= 1;
        k++
    }
    let mask = (1 << k) - 1;
    return (~n) & mask
};

class UnionFind:
    def __init__(self, size):
        self.root = []
        self.components = size
        for i in range(size):
            self.root.append(i)

        self.ranks = [0]*size

    def find(self, x):
        while self.root[x] != x:
            x = self.root[x]

        return x
   
    def connected(self, x, y):
        return self.find(x) == self.find(y)
   
    def union(self, x, y):
        if self.connected(x, y):
            return False

        self.components -= 1
        rootX = self.find(x)
        rootY = self.find(y)
        if self.ranks[rootX] < self.ranks[rootY]:
            self.root[rootX] = rootY
        elif self.ranks[rootY] < self.ranks[rootX]:
            self.root[rootY] = rootX
        else:
            self.root[rootX] = rootY
            self.ranks[rootY] += 1
       
        return True

class Solution:
    def maxStability(self, n: int, edges: List[List[int]], k: int) -> int:
        connectedEdges = []
        maxHeap = []
        uf = UnionFind(n)
        ans = inf
        mustEdgesCount = 0
        for u, v, s, must in edges:
            if must:
                mustEdgesCount += 1
                ans = min(ans, s)
                uf.union(u, v)
            else:
                heapq.heappush(maxHeap, (-s, u, v))

        while maxHeap:
            s, u, v = heapq.heappop(maxHeap)
            s*=-1
            if not uf.connected(u, v):
                uf.union(u, v)
                connectedEdges.append(s)

        if uf.components != 1 or len(connectedEdges) + mustEdgesCount >= n:
            return -1

        connectedEdges.sort()
        for i in range(len(connectedEdges)):
            if i < k:
                ans = min(ans, connectedEdges[i]*2)
            else:
                ans = min(ans, connectedEdges[i])

        return ans

class Solution:
    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:
        preMask = [0] * n
        for pre, nxt in relations:
            pre -= 1
            nxt -= 1
            preMask[nxt] |= (1 << pre)

        target = 2**n - 1
        @lru_cache(None)
        def dp(mask):
            if mask == target:
                return 0

            candidates = []
            ans = inf
            for course in range(n):
                if (mask >> course) & 1:
                    continue
                    
                if (preMask[course] & mask) == preMask[course]:
                    candidates.append(course)

            for comb in itertools.combinations(candidates, min(len(candidates), k)):
                newMask = mask
                for c in comb:
                    newMask |= (1 << c)

                ans = min(ans, 1 + dp(newMask))

            return ans

        result = dp(0)
        dp.cache_clear()
        return result

class Solution:
    def maxStability(self, n: int, edges: List[List[int]], k: int) -> int:
        def check(cost):
            def find_parent(u):
                if parent[u]==u:
                    return u
                parent[u] = find_parent(parent[u])
                return parent[u]
            def join(u,v):
                if tree_size[u]<tree_size[v]:
                    tree_size[u]+=tree_size[v]
                    parent[v]=u
                else:
                    tree_size[v]+=tree_size[u]
                    parent[u]=v
            n_component = n
            parent = [i for i in range(n)]
            tree_size = [1]*n
            n_upgrade = k
            for u,v,c,m in edges:
                if m == 1:
                    if c<cost:
                        return False
                    u = find_parent(u)
                    v = find_parent(v)
                    if u!=v:
                        n_component -=1
                        join(u,v)
                    else:
                        return False
            for u,v,c,m in edges:
                if m == 0:
                    u = find_parent(u)
                    v = find_parent(v)
                    if u!=v:
                        if c>=cost:
                            n_component -=1
                            join(u,v)
                        elif n_upgrade>0 and 2*c>=cost:
                            n_component -=1
                            n_upgrade -=1
                            join(u,v)
            return n_component == 1

        edges.sort(key= lambda x: x[2])
        edges = edges[::-1]
        if check(0) == False:
            return -1
        l = 0
        h = 2*edges[0][2]
        while l<=h:
            m = (l+h)//2
            if check(m):
                l=m+1
            else:
                h=m-1
        return l-1

class Solution {
    final int MAX_STAB = 200000;
    class Edge {
        int u, v, s, must;
        public Edge(int u, int v, int s, int must) {
            this.u = u;
            this.v = v;
            this.s = s;
            this.must = must;
        }
        @Override
        public String toString() {
            return "Edge{"+ this.u + "," + this.v + "," + this.s + "," + this.must+"}";
        }
    }
    class DSU {
        List<Integer> parents;
        public DSU(List<Integer> parents) { this.parents = new ArrayList<>(parents); }
        public void insert(int x, int y) {
            int pX = find(x);
            int pY = find(y);
            if (pX != pY) parents.set(pX, pY);
        }
        public int find(int x) {
            if (parents.get(x) == x) return x;
            int root = find(parents.get(x));
            parents.set(x, root);
            return root;
        }
    }
    public int maxStability(int n, int[][] edges, int k) {
        if (edges.length < n - 1) return -1;
        List<Edge> edgesList = new ArrayList<>();
        for (int[] edge : edges) edgesList.add(new Edge(edge[0], edge[1], edge[2], edge[3]));
        List<Edge> must = new ArrayList<>();
        List<Edge> optional = new ArrayList<>();
        for (Edge edge : edgesList) {
            if (edge.must == 1) must.add(edge);
            else optional.add(edge);
        }
        if (must.size() > n - 1) return -1;
        Collections.sort(optional, (a, b) -> b.s - a.s);
        int select = 0, minStab = MAX_STAB;
        List<Integer> initParent = new ArrayList<>();
        for (int i = 0; i < n; i++) initParent.add(i);
        DSU initDSU = new DSU(initParent);
        for (Edge edge : must) {
            if (initDSU.find(edge.u) == initDSU.find(edge.v) || select >= n - 1) return -1;
            initDSU.insert(edge.u, edge.v);
            select++;
            minStab = Math.min(minStab, edge.s);
        }
        int l = 0, r = minStab, res = -1;
        while (l < r) {
            int m = l + ((r - l + 1) / 2);
            DSU dsu = new DSU(initDSU.parents);
            int sel = select, cnt2 = 0;
            for (Edge edge : optional) {
                if (dsu.find(edge.u) == dsu.find(edge.v)) continue;
                if (edge.s >= m) {
                    dsu.insert(edge.u, edge.v);
                    sel++;
                } else if (cnt2 < k && edge.s * 2 >= m) {
                    dsu.insert(edge.u, edge.v);
                    cnt2++;
                    sel++;
                } else break;
                if (sel >= n - 1) break;
            }
            if (sel != n - 1) r = m - 1;
            else res = l = m;
        }
        return res;
    }
}

public class Solution
{
    public long MinNumberOfSeconds(int mountainHeight, int[] workerTimes)
    {
        int n = workerTimes.Length;
        PriorityQueue<(int,long), long> q = new();
        for (int i = 0; i < n; i++)
        {
            q.Enqueue((i, workerTimes[i]), workerTimes[i]);
        }
        long[] time = new long[n];
        while(mountainHeight>0)
        {
            mountainHeight--;
            var (idx, cur_time) = q.Dequeue();
            time[idx] += cur_time;
            cur_time += workerTimes[idx];
            q.Enqueue((idx, cur_time),time[idx]+cur_time);
        }
        return time.Max();

    }
}

class Solution
{

    public long MinNumberOfSeconds(int mountainHeight, int[] workerTimes)
    {
        int maxWorkerTimes = workerTimes.Max();
        long l = 1;
        long r =(long)maxWorkerTimes * mountainHeight * (mountainHeight + 1) / 2;
        long ans = 0;

        bool isValid(long time)
        {
            int count = 0;
            foreach(var i in workerTimes )
            {
                var delta = 1 + (4 * 2 * (double)time)/i;
                var x = (-1 + (int)Math.Sqrt(delta)) / 2;
                count += x;
            }
            return count >= mountainHeight;

        }


        while (l <= r)
        {
            long mid = (l + r) / 2;
            if(isValid(mid))
            {
                ans = mid;
                r = mid-1;
            }
            else
            {
                l = mid+1;
            }
        }

        return ans;
    }
}

function minNumberOfSeconds(height: number, wt: number[]): number {
    let l = 1n;
    let r = BigInt(1e16);
    let res = r;

    const h = BigInt(height);

    while (l <= r) {
        const m = (l + r) / 2n;
        let cur = 0n;

        for (let time of wt) {
            let t = BigInt(time);
            let l1 = 0n, r1 = BigInt(2e5);
            let st = 0n;
            
            while (l1 <= r1) {
                const x = (l1 + r1) / 2n;
                const val = t * x * (x + 1n) / 2n;
                
                if (val <= m) {
                    st = x;
                    l1 = x + 1n;
                } else {
                    r1 = x - 1n;
                }
            }
            cur += st;
            if (cur >= h) break;
        }

        if (cur >= h) {
            res = m;
            r = m - 1n;
        } else {
            l = m + 1n;
        }
    }

    return Number(res);
}