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

class Solution:
    def maxIceCream(self, costs: List[int], coins: int) -> int:
        costs.sort()
        cumsum = 0
        if costs[0] > coins: return 0
        for i, cost in enumerate(costs):
            cumsum += costs[i]
            if cumsum > coins:
                return i
        return i + 1

class Solution {
    public int maxNumberOfBalloons(String text) {
        char[] freq = new char[26];

        for (char ch: text.toCharArray())
            freq[ch - 'a']++;

        int min = Integer.MAX_VALUE;

        for (char ch: "balon".toCharArray())
            if (ch == 'l' || ch == 'o')
                min = Math.min(min, freq[ch - 'a'] / 2);
            else
                min = Math.min(min, freq[ch - 'a']);

        return min;
    }
}

public class Solution {
    public int MaxNumberOfBalloons(string text) {
        int[]c = new int[26];
        foreach(var i in text)
            c[i-'a']++;
        int rtn=0;
        while(true)
        {   
            foreach(var i in "balloon")
                if(--c[i-'a']<0)
                    return rtn;
            rtn++;
        }
        return rtn;
    }
}

class Solution:
    def maxNumberOfBalloons(self, text: str) -> int:
        '''
        text = "nlaebolko"
        '''
        counter = Counter(text)
        dic = {
            "b": counter["b"],
            "a": counter["a"],
            "ll": counter["l"] // 2,
            "oo": counter["o"] // 2,
            "n": counter["n"],
            "s": counter["n"],
        }
        return min(dic.values())

function zigZagArrays(n: number, l: number, r: number): number {
    const MOD = 1e9 + 7;
    const D = r - l + 1;
    if (n === 1) return D;
    let dp0 = new Int32Array(D);
    let dp1 = new Int32Array(D);
  
    let nextDp0 = new Int32Array(D);
    let nextDp1 = new Int32Array(D);
    const pref0 = new Int32Array(D);
    const pref1 = new Int32Array(D);
    for (let val = 0; val < D; val++) {
        dp0[val] = (D - 1 - val) % MOD;
        dp1[val] = val % MOD;
    }
    for (let i = 3; i <= n; i++) {
        pref0[0] = dp0[0];
        pref1[0] = dp1[0];
        for (let val = 1; val < D; val++) {
            pref0[val] = (pref0[val - 1] + dp0[val]) % MOD;
            pref1[val] = (pref1[val - 1] + dp1[val]) % MOD;
        }
        for (let val = 0; val < D; val++) {
            if (val < D - 1) {
                let sum1 = pref1[D - 1] - pref1[val];
                if (sum1 < 0) sum1 += MOD;
                nextDp0[val] = sum1;
            } else {
                nextDp0[val] = 0;
            }
            if (val > 0) {
                nextDp1[val] = pref0[val - 1];
            } else {
                nextDp1[val] = 0;
            }
        }
        let temp0 = dp0;
        dp0 = nextDp0, nextDp0 = temp0;
        let temp1 = dp1;
        dp1 = nextDp1, nextDp1 = temp1;
    }
    let res = 0;
    for (let val = 0; val < D; val++) {
        res = (res + dp0[val] + dp1[val]) % MOD;
    }
    return res;
}

class Solution:
    def zigZagArrays(self, n: int, l: int, r: int) -> int:
        MOD = 10**9 + 7
        M = r-l+1
        dp = [1]*M
        for _ in range(n - 1):
            prefix=0
            for i in range(M):
                dp[i],prefix = prefix,(prefix+dp[i])%MOD
            dp.reverse()
        return (sum(dp)*2)%MOD

class Solution:
    def zigZagArrays(self, n: int, l: int, r: int) -> int:
        up = [0]*(r+2)
        down = [0]*(r+2)
        for i in range(l,r+1):
            up[i]=1
            down[i]=1
        modulo = 10**9+7
        for _ in range(1,n):
            cur_up = [0]*(r+2)
            cur_down = [0]*(r+2)
            for i in range(l,r+1):
                cur_up[i]=(cur_up[i-1]+down[i-1]) % modulo
            for i in range(r,l-1,-1):
                cur_down[i]=(cur_down[i+1]+up[i+1]) % modulo
            up = cur_up
            down = cur_down
        return (sum(up)+sum(down)) % modulo

class Solution:
    def zigZagArrays(self, n: int, l: int, r: int) -> int:
        def matmul(A,B):
            C = [[0]*m for _ in range(m)]
            for i in range(m):
                for j in range(m):
                    for k in range(m):
                        C[i][j]+=(A[i][k]*B[k][j])%modulo
            return C
        def matvec(A,v):
            res = [0]*m
            for i in range(m):
                for j in range(m):
                    res[i]+=A[i][j]*v[j]
            return res
        def matpow(A,n):
            res = [[0]*m for _ in range(m)]
            for i in range(m):
                res[i][i]=1
            cur = A
            for j in range(n.bit_length()+1):
                if n & (1<<j):
                    res = matmul(res,cur)
                    print(j)
                cur = matmul(cur,cur)
                print(cur)
            return res
        m = (r-l+1)
        modulo = 10**9+7
        board = [[0]*m for _ in range(m)]
        
        for i in range(m):
            for j in range(i):
                board[i][j]=1
        board_rev = [[0]*m for _ in range(m)]
        for i in range(m):
            for j in range(i+1,m):
                board_rev[i][j]=1
        n-=1
        A= matmul(board,board_rev)
        v = [1]*m
        A = matpow(A,n//2)
        if n%2==1:
            A = matmul(A,board)
        res = matvec(A,v)
        return (2*sum(res)) % modulo

function countMajoritySubarrays(nums: number[], target: number): number {
    const n = nums.length;
    const arr = new Array<number>(n * 2 + 1).fill(0);
    arr[n] = 1;
    let count = n, res = 0, sum = 0;
    for (let i = 0; i < n; ++i) {
        if (nums[i] === target) {
            sum += arr[count];
            count++;
            arr[count]++;
        } else {
            count--;
            sum -= arr[count];
            arr[count]++;
        }
        res += sum;
    }
    return res;
}

class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        max_num=max(nums)
        count=Counter(nums)
        if 1 in count:
            ans=count[1]-(count[1]%2==0)
        else:
            ans=1
        for num in nums:
            if num==1:
                continue
            length=0
            x=num
            while x<=max_num and x in count and count[x]>=2:
                length+=2
                x*=x
            ans=max(ans,length+(1 if x in count else -1))
        return ans

class Solution:
    def numOfStrings(self, patterns: List[str], word: str) -> int:
        res = 0
        for p in patterns:
            if p in word:
                res += 1
        return res