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

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        int maxValue = Integer.MIN_VALUE;

        for (int i = 0; i < nums.size(); i++) {
            int value = nums.get(i).get(0);
            minHeap.offer(new int[]{value, i, 0});
            maxValue = Math.max(maxValue, value);
        }

        int rangeStart = 0, rangeEnd = Integer.MAX_VALUE;

        while (minHeap.size() == nums.size()) {
            int[] minElement = minHeap.poll();
            int minValue = minElement[0];

            if (maxValue - minValue < rangeEnd - rangeStart ||
                (maxValue - minValue == rangeEnd - rangeStart && minValue < rangeStart)) {
                rangeStart = minValue;
                rangeEnd = maxValue;
            }

            if (minElement[2] + 1 < nums.get(minElement[1]).size()) {
                int nextValue = nums.get(minElement[1]).get(minElement[2] + 1);
                minHeap.offer(new int[]{nextValue, minElement[1], minElement[2] + 1});
                maxValue = Math.max(maxValue, nextValue);
            } else {
                break;
            }
        }

        return new int[]{rangeStart, rangeEnd};
    }
}

class PItem {
public:   
    int val;
    int r;
    int c;

    PItem (int _val, int _r, int _c) {
        val = _val;
        r = _r;
        c = _c;
    }
};

class Compare {
public:
    bool operator() (PItem& x, PItem& y) {
        return x.val > y.val;
    }
};


class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        priority_queue<PItem, vector<PItem>, Compare> pq;
        int left = 0;
        int right = 1e9;
        int maxP = -1;
        int n = nums.size();

        for (int i = 0; i < n; i++) {
            maxP = max(maxP, nums[i][0]);
            PItem p(nums[i][0], i, 0);
            pq.push(p);
        }

        while (!pq.empty()) {
            PItem p = pq.top();
            pq.pop();
            if (maxP - p.val < right - left) {
                left = p.val;
                right = maxP;
            }

            if (p.c + 1 < nums[p.r].size()) {
                PItem p_next = PItem(nums[p.r][p.c+1], p.r, p.c + 1);
                maxP = max(maxP, nums[p.r][p.c+1]);
                pq.push(p_next);
            }
            else break;
        }
        return vector<int> {left, right};
    }
};

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        heap = []
        maxValue = -10 ** 6 - 1
        start, end, k = 0, 10 ** 6, len(nums)

        for i in range(k):
            heapq.heappush(heap, (nums[i][0], i, 0))
            if maxValue < nums[i][0]:
                maxValue = nums[i][0]

        while len(heap) == k:
            minValue, row, col = heapq.heappop(heap)
            if maxValue - minValue < end - start:
                start, end = minValue, maxValue
            
            if col + 1 < len(nums[row]):
                heapq.heappush(heap, (nums[row][col+1], row, col+1))
                if maxValue < nums[row][col+1]:
                    maxValue = nums[row][col+1]
        return [start, end]

class Solution:
    def maxKelements(self, nums: List[int], k: int) -> int:
        heap = []
        for num in nums:
            heapq.heappush(heap, -num)
        result = 0
        while k > 0:
            maxValue = -heapq.heappop(heap)
            result += maxValue
            newValue = math.ceil(maxValue / 3.0)
            heapq.heappush(heap, -newValue)
            k -= 1
        return result

class Solution {
public:
    long long maxKelements(vector<int>& nums, int k) {
        priority_queue<int> pq;

        for (int i = 0; i < nums.size(); i++) {
            pq.push(nums[i]);
        }

        long long ans = 0;

        while(k--) {
            int tmp = pq.top();
            ans += tmp;
            tmp = ceil(tmp / 3.0);
            pq.pop();
            pq.push(tmp);
        }

        return ans;
    }
};

function maxKelements(nums: number[], k: number): number {
    const pq = new MaxPriorityQueue();
    let res = 0;
    for (const num of nums) pq.enqueue(num);
    while(k--) {
        let el = pq.dequeue()!.element;
        res+= el;
        el = Math.ceil(el / 3);
        pq.enqueue(el);
    }
    return res;
};

class Solution {
    public long maxKelements(int[] nums, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
        for (int i : nums) {
            q.add(i);
        }
        long sum = 0;
        while(k-- > 0) {
            sum += q.peek();
            q.add((int) Math.ceil(q.poll() / 3.0));
        }
        return sum;
    }
}

class Solution {
public:
    long long maxKelements(vector<int>& nums, int k) {
        auto comp =  [](int x, int y) {return x < y;};
        priority_queue<int, vector<int>, decltype(comp) > pq;
        for (int num : nums) {
            pq.push(num);
        }

        long long res = 0;
        for (int i = 1; i <= k; i++) {
            int t = pq.top();
            // cout << t << "\n";
            pq.pop();
            res += t;
            pq.push(ceil(1.0*t/3));
        }
        return res;
    }
};

class Solution {
public:
    long long maxKelements(vector<int>& nums, int k) {
        priority_queue<long, vector<long>> q(nums.begin(), nums.end());
        long ret = 0;

        while (k--) {
            long t = q.top();
            ret += t;
            q.pop();
            q.push(ceil(t / 3.0));
        }

        return ret;
    }
};

class Solution {
    public long maxKelements(int[] nums, int k) {
        int n = nums.length;
        long score = 0l;
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        for (int num : nums) {
            pq.offer(num);
        }
        while (k > 0) {
            double max = (double) pq.poll();
            score += max;
            double res = max / 3.0;
            pq.offer((int) Math.ceil(res));
            k--;
        }
        return score;
    }
}