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

class Solution:
    def numberOfBeautifulIntegers(self, low: int, high: int, k: int) -> int:
        @lru_cache(maxsize=None)
        def solve(s: str, tight: bool = True, i: int = 0, odd: int = 0, even: int = 0, modk: int = 0, leading_zero: bool = True) -> int:
            if i == len(s):
                return odd == even and modk == 0
           
            res = 0
            limit = int(s[i]) if tight else 9
            for j in range(limit + 1):
                new_tight = tight and int(s[i]) == j
                new_odd = odd + (j % 2 == 1)
                new_even = even + (j % 2 == 0)
                new_modk = (10 * modk + j) % k
                if leading_zero and j == 0:
                    res += solve(s, False, i + 1, 0, 0, 0, True)
                else:
                    res += solve(s, new_tight, i + 1, new_odd, new_even, new_modk, False)
                               
            return res
        return solve(str(high)) - solve(str(low - 1))

class Solution {
public:
    int maximizeTheProfit(int n, vector<vector<int>>& offers) {
        sort(begin(offers), end(offers), [](const auto& a, const auto& b){
            return a[0] < b[0];
        });
        
        int no = offers.size(), res = 0;
        for(int i = no - 1; i >= 0; --i){
            int j = upper_bound(begin(offers) + i + 1, end(offers), offers[i][1],
                [&](int v, const auto& x){return v < x[0];}) - begin(offers);
            if (j < no) offers[i][2] += offers[j][2];
            if (i < no - 1)
                offers[i][2] = max(offers[i][2], offers[i + 1][2] );
            res = max(res, offers[i][2]);            
        }
        return res;
    }
};

function repeatedSubstringPattern(s: string): boolean {
    const n = s.length;
    if (n <= 1) {
        return false;
    }
    const table: number[] = Array(n).fill(0);
    let prefixLen = 0;
    let longestPrefixSuffix = 0;
    for (let i = 1; i < n; i++) {
        while (prefixLen > 0 && s[i] !== s[prefixLen]) {
            prefixLen = table[prefixLen - 1];
        }
        if (s[i] === s[prefixLen]) {
            prefixLen++;
        }
        table[i] = prefixLen;
        longestPrefixSuffix = prefixLen;
    }
    if (n % (n - longestPrefixSuffix) === 0 && longestPrefixSuffix > 0) {
        return true;
    }
    return false;
}

public bool RepeatedSubstringPattern(string s)
{
    int n = s.Length, m = n / 2, i, j, k;
    if (n == 1)
        return false;

    for (i = 1; i <= m; ++i)
        if (n % i == 0)
        {
            k = n - i;
            for (j = 0; j < k; ++j)
                if (s[j] != s[j + i])
                    break;
            if (j == k)
                return true;
        }

    return false;
}

struct Solution {
    bool repeatedSubstringPattern(string_view s) {
        for (size_t i = 1; i <= s.size() / 2; ++i) {
            if (s.size() % i != 0) continue;
            const auto sub = s.substr(0, i);
            bool isRepeated = true;
            for (size_t j = i; isRepeated && j < s.size(); j += i)
                if (s.substr(j, i) != sub) isRepeated = false;
            if (isRepeated) return true;
        }
        return false;
    }
};

const isPrime = n => {
    for (let i = 2; i <= Math.sqrt(n); i++) {
        if (n % i === 0) {
            return false;
        }
    }

    return true;
}

/**
 * @param {string} s
 * @return {boolean}
 */
var repeatedSubstringPattern = function(s) {
    for (let i = 2; i <= s.length; i++) {
        if (s.length % i !== 0 || !isPrime(i)) {
            continue;
        }

        const l = s.length / i;

        if (s.substring(0, l).repeat(i) === s) {
            return true;
        }
    }

    return false;
};