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

class Solution {
   public:
    int minSpeedOnTime(std::vector<int>& dist, double hour) {
        int lo = 1, hi = INT_MAX - 1;
        int res = -1;
        while (lo <= hi) {
            int mi = lo + (hi - lo) / 2;
            double h = requireHours(dist, mi);
            if (h <= hour) {
                res = mi;
                hi = mi - 1;
            } else
                lo = mi + 1;
        }
        return res;
    }
   private:
    double requireHours(std::vector<int>& dist, int speed) {
        double h = 0;
        int n = dist.size();
        for (int i = 0; i < n - 1; ++i) h += dist[i] / speed + ((dist[i] % speed) > 0);
        return h + (double)dist[n - 1] / speed;
    }
};

class Solution {
public:
    bool check(long long x, vector<int>& pins, int n){
        long long S = 0;
        for (auto& pin : pins){
            S += min(1LL * pin, x);
        }
        return S >= x * n;
    }
    long long maxRunTime(int n, vector<int>& pins) {
        long long lo = 0, hi = (long long)1e14 / n;
        while (lo < hi){
            long long mid = (lo + hi + 1) / 2;
            if (check(mid,pins,n)) lo = mid;
            else hi = mid - 1;
        }
        return lo;
    }
};

var maxRunTime = function(n, batteries) {
    const go = time => {
        let sum = 0;
        for (const b of batteries) {
            sum += Math.min(time, b);
            if (sum >= time * n) {
                return true;
            }
        }
        return false;
    };
    let l = 0, r = 1e14 + 1;
    while (l < r) {
        const m = Math.trunc((l + r) / 2);
        if (go(m)) {
            l = m + 1;
        } else {
            r = m;
        }
    }
    return l - 1;
};

using ll = long long;
class Solution {
public:
    long long maxRunTime(int n, vector<int>& batteries) {
        ll l=1,r=1e14;
        sort(batteries.begin(),batteries.end());
        while(l<=r)
        {
            ll m=(l+r)>>1;
            auto it=lower_bound(batteries.begin(),batteries.end(),m);
            if(n-(batteries.end()-it)<=0||accumulate(batteries.begin(),it,0ll)/(n-(batteries.end()-it))>=m)
            {
                l=m+1;
            }
            else
            {
                r=m-1;
            }
        }
        return l-1;
    }

};

class Solution {
   public:
    long long maxRunTime(int n, std::vector<int>& batteries) {
        long long lo = 1;
        long long hi = std::accumulate(batteries.begin(), batteries.end(), 0LL) / n;  // O(k)
        if (n == 1) return hi;
        int k = batteries.size();
        std::sort(batteries.begin(), batteries.end());  // O(klogk)
        std::vector<long long> accTime(k + 1);
        for (int i = 0; i < k; ++i) accTime[i + 1] = accTime[i] + batteries[i];  // O(k)
        while (lo < hi) {
            long long mi = (hi + lo + 1) / 2;
            int j = std::upper_bound(batteries.begin(), batteries.end(), mi) - batteries.begin();  // O(logk)
            long long maxAvaTime = accTime[j] + (k - j) * mi;
            if (mi * n <= maxAvaTime) lo = mi;
            else hi = mi - 1;
        }
        return lo;
    }
};

class Solution {
public:
    int dp[20][20];
    int get_score(vector<int>& a, int l, int r){
        if (l > r) return 0;
        if (l == r) return a[l];
        if (dp[l][r]) return dp[l][r];
        return dp[l][r] = max(a[l] + min(get_score(a,l+2,r),get_score(a,l+1,r-1)),
            a[r] + min(get_score(a,l,r-2), get_score(a,l+1,r-1)));
    }   
    bool PredictTheWinner(vector<int>& a) {
        int sum = accumulate(a.begin(),a.end(),0);
        return 2 * get_score(a,0,a.size()-1) >= sum;
    }
};

class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:
        prefix_sum = nums.copy()
        for index in range(1, len(nums)):
            prefix_sum[index] += prefix_sum[index - 1]

        def get_sub_sum(left, right):
            if left == 0:
                return prefix_sum[right]
            return prefix_sum[right] - prefix_sum[left - 1]

        @cache
        def get_optimal_score(left, right):
            if left == right:
                return nums[left]
            
            left_score = nums[left] + get_sub_sum(left + 1, right) - get_optimal_score(left + 1, right)
            right_score = nums[right] + get_sub_sum(left, right - 1) - get_optimal_score(left, right - 1)

            return max(left_score, right_score)
        
        first_player_score = get_optimal_score(0, len(nums)  - 1)
        second_player_score = prefix_sum[-1] - first_player_score

        return first_player_score >= second_player_score

function PredictTheWinner(nums: number[]): boolean {
    const n = nums.length;
    if (n % 2 === 0 || n === 1) return true;
    const memo = new Array(n).fill(0).map(e => Array(n).fill(-1))
    const go = (l: number, r: number): number => {
        if (memo[l][r] !== -1) return memo[l][r];
        if (l === r) return nums[l]
        const lScore = nums[l] - go(l + 1, r)
        const rScore = nums[r] - go(l, r-1)
        memo[l][r] = Math.max(lScore, rScore)
        return memo[l][r]
    }
    return go(0, n-1) >= 0;
};

var PredictTheWinner = function(nums) {
    const n = nums.length;
    const memo = [];
    const go = (i, j) => memo[i * (n + 1) + j] ??= (() => {
        if (i >= j) {
            return [0, 0];
        }
        const left = go(i + 1, j);
        const right = go(i, j - 1);
        return nums[i] + left[1] >= nums[j-1] + right[1]
            ? [left[1] + nums[i], left[0]]
            : [right[1] + nums[j-1], right[0]]
    })();
    const [one, two] = go(0, n);
    return one >= two;
};

enum Player : std::size_t
{
    one = 0,
    two
};

class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {

        int start{};
        int sz = nums.size();
        int end = sz - 1;
        int cur_sum{};

        std::vector<std::vector<std::vector<int>>> p_table(2, std::vector(sz, std::vector<int>(sz, -1)));
        for (int i = 0; i < sz; ++i)
        {
            p_table[Player::one][i][i] = nums[i];
            p_table[Player::two][i][i] = nums[i];
            cur_sum += nums[i];
            m_sum.emplace_back(cur_sum);
        }

        solve(p_table, start, end, Player::one);
        return p_table[Player::one][start][end] >= p_table[Player::two][start][end] ;
    }

private:
    int p1_sum{};
    int p2_sum{};
    std::vector<int> m_sum;

    void solve(std::vector<std::vector<std::vector<int>>>& p_table, int start, int end, Player player)
    {
        if (p_table[player][start][end] != -1)
            return;
        
        auto other = other_player(player);
        if (p_table[other][start + 1][end] == -1)
            solve(p_table, start + 1, end, other);
        if (p_table[other][start][end - 1] == -1)
            solve(p_table, start, end - 1, other);

        p_table[other][start][end] = std::min(p_table[other][start][end - 1], p_table[other][start + 1][end]);

        if (start > 0)
        {
            p_table[player][start][end] = m_sum[end] - m_sum[start - 1] - p_table[other][start][end];
        }
        else
        {
            p_table[player][start][end] = m_sum[end] - p_table[other][start][end];
        }

    }

    Player other_player(Player input)
    {
        if (input == Player::one)
            return Player::two;

        return Player::one;
    }
};

class Solution {
   public:
    bool PredictTheWinner(std::vector<int>& nums) {
        int n = nums.size();
        memo = std::vector<std::vector<int>>(n, std::vector<int>(n, -1));
        return recurse(nums, 0, n - 1) >= 0;
    }
   private:
    int recurse(std::vector<int>& nums, int first, int last, bool turn = true) {
        if (first > last) return 0;
        if (memo[first][last] != -1) return memo[first][last];
        if (turn)
            return memo[first][last] = std::max(nums[first] + recurse(nums, first + 1, last, false),
                                                nums[last] + recurse(nums, first, last - 1, false));
        return memo[first][last] = std::min(-nums[first] + recurse(nums, first + 1, last, true),
                                            -nums[last] + recurse(nums, first, last - 1, true));
    }
   private:
    std::vector<std::vector<int>> memo;
};