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

Hi các bác, mình có implement theo cách bên dưới, fail test case cuối nhưng đang chưa tìm ra là vấn đề sai nằm ở đâu. Mình nhờ mọi người check hộ ạ.

JavaScript:
/**
 * @param {number[]} difficulty
 * @param {number[]} profit
 * @param {number[]} worker
 * @return {number}
 */
var maxProfitAssignment = function (difficulty, profit, worker) {
    let curMax = 0;
    let m = {};
    for (let i = 0; i < difficulty.length; i++) {
        m[difficulty[i]] = profit[i];
    }
    const sortedDif = difficulty.sort((a, b) => a - b);
    const t = [];
    for (let i = 0; i < sortedDif.length; i++) {
        if (m[sortedDif[i]] > curMax) {
            curMax = m[sortedDif[i]]
            t.push(sortedDif[i])
        } else {
            continue;
        }
    }
    function binarySearchMaxLE(dif, num) {
        let low = 0, high = dif.length - 1;
        let result = null;
        while (low <= high) {
            let mid = Math.floor((low + high) / 2);
            if (dif[mid] <= num) {
                result = dif[mid];
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return result;
    }
    let r = 0;
    for (const w of worker) {
        const p = binarySearchMaxLE(t, w);
        r += p ? m[p] : 0;
    }
 
    return r;
};

NUJ0lzI.png
m[difficulty i ] = profit i ; trùng difficulty -> pair sai profit
 
JavaScript:
/**
 * @param {number[]} difficulty
 * @param {number[]} profit
 * @param {number[]} worker
 * @return {number}
 */
var maxProfitAssignment = function (difficulty, profit, worker) {
    let curMax = 0;
    let m = {};
    for (let i = 0; i < difficulty.length; i++) {
        m[difficulty[i]] = Math.max(profit[i], m[difficulty[i]] || 0);
    }
    const sortedDif = difficulty.sort((a, b) => a - b);
    const t = [];
    for (let i = 0; i < sortedDif.length; i++) {
        if (m[sortedDif[i]] > curMax) {
            curMax = m[sortedDif[i]]
            t.push(sortedDif[i])
        } else {
            continue;
        }
    }
    function binarySearchMaxLE(dif, num) {
        let low = 0, high = dif.length - 1;
        let result = null;
        while (low <= high) {
            let mid = Math.floor((low + high) / 2);
            if (dif[mid] <= num) {
                result = dif[mid];
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return result;
    }
    let r = 0;
    for (const w of worker) {
        const p = binarySearchMaxLE(t, w);
        r += p ? m[p] : 0;
    }
    
    return r;
};
 
JavaScript:
function maxProfitAssignment(difficulty: number[], profit: number[], worker: number[]): number {
    const combineData = difficulty.map((d, i) => [d, profit[i]]);
    combineData.sort((a, b) => b[1] - a[1]);
    worker.sort((a, b) => b - a);

    let workerIdx = 0;
    let result = 0;
    let diffIdx = 0;

    while (workerIdx < worker.length && diffIdx < combineData.length) {
        if (worker[workerIdx] >= combineData[diffIdx][0]) {
            result += combineData[diffIdx][1];
            workerIdx++;
        } else {
            diffIdx++;
        }
    }
    return result;
};

Tiếp tục là 2-pointers
 
ngồi hơn tiếng đồng hồ cuối cùng cũng giải được, chưa học algo giải mấy bài này đau đầu quá
f2ebfe3.jpg

Python:
class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        dicts = {}
        len_profit = len(profit)
        for i in range(0, len_profit):
            if difficulty[i] not in dicts:
                dicts[difficulty[i]] = profit[i]
            elif profit[i] > dicts.get(difficulty[i]):
                dicts[difficulty[i]] = profit[i]
        difficulty.sort()
        worker.sort()
        ans, tmp, t = 0, 0, 0

        for i in worker:
            while t < len_profit:
                if i >= difficulty[t]:
                    tmp = max(tmp, dicts[difficulty[t]])
                    t += 1
                else:
                    break
            ans += tmp
        return ans
 
ngồi hơn tiếng đồng hồ cuối cùng cũng giải được, chưa học algo giải mấy bài này đau đầu quá
f2ebfe3.jpg

Python:
class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        dicts = {}
        len_profit = len(profit)
        for i in range(0, len_profit):
            if difficulty[i] not in dicts:
                dicts[difficulty[i]] = profit[i]
            elif profit[i] > dicts.get(difficulty[i]):
                dicts[difficulty[i]] = profit[i]
        difficulty.sort()
        worker.sort()
        ans, tmp, t = 0, 0, 0

        for i in worker:
            while t < len_profit:
                if i >= difficulty[t]:
                    tmp = max(tmp, dicts[difficulty[t]])
                    t += 1
                else:
                    break
            ans += tmp
        return ans
Bác giỏi quá, chưa học mà đã biết giải rồi, bác học ở nguồn nào v cho em xin với
 
Code:
class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        n = len(difficulty)
        listProfit = {}
        for i in range(n): listProfit[profit[i]] = min(difficulty[i] , listProfit.get(profit[i] , int(1e9)))
        pq = []
        for p in profit:
            heapq.heappush(pq , -p)

        worker.sort(reverse=True)

        res = 0
        for w in worker:
            while pq and listProfit[pq[0] * -1] > w: heapq.heappop(pq)
            if pq: res += pq[0] * -1
        
        return res
dùng PQ thấy hơi chậm :cry:
 
Code:
class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        n = len(difficulty)
        listProfit = {}
        for i in range(n): listProfit[profit[i]] = min(difficulty[i] , listProfit.get(profit[i] , int(1e9)))
        pq = []
        for p in profit:
            heapq.heappush(pq , -p)

        worker.sort(reverse=True)

        res = 0
        for w in worker:
            while pq and listProfit[pq[0] * -1] > w: heapq.heappop(pq)
            if pq: res += pq[0] * -1
       
        return res
dùng PQ thấy hơi chậm :cry:
pq là priority queue phải không fen?
 
Chạy được là được :confident:
C#:
public class Solution
{
    public int MaxProfitAssignment(int[] difficulty, int[] profit, int[] worker)
    {
        int maxProfit = 0;
        int index = 0;
        List<(int profits, int diff)> store = new List<(int profits, int diff)>();

        for (int i = 0; i < profit.Length; i++)
        {
            store.Add((profit[i], difficulty[i]));
        }

        store.Sort((a, b) => a.profits - b.profits);

        while (index < worker.Length)
        {
            for (int i = store.Count - 1; i >= 0; i--)
            {
                if (worker[index] >= store[i].diff)
                {
                    maxProfit += store[i].profits;
                    break;
                }
            }

            index++;
        }

        return maxProfit;
    }
}
 
Java:
class Solution {
    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int len = profit.length;
        int[][] arr = new int[len][2];
        for(int i = 0; i < len;i++){
            arr[i][0] = profit[i];
            arr[i][1] = difficulty[i];
        }
        Arrays.sort(arr,(a,b) -> a[0] - b[0]);
        int sum = 0;
        for(int j=0;j < worker.length;j++){
            int current = 0;
            for(int i=0;i < difficulty.length;i++) {
                if(arr[i][0]> current && arr[i][1] <=worker[j] ){
                    current = arr[i][0];
                }
            }
            sum+=current;
        }
        return sum;
    }
}
 
Last edited:
At the end of the day
Python:
class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        ans = 0
        jobs = sorted(zip(difficulty, profit))
        i = 0
        maxProfit = 0
        for skill in sorted(worker):
            while i < len(jobs) and jobs[i][0] <= skill:
                maxProfit = max(maxProfit, jobs[i][1])
                i += 1
            ans += maxProfit
        return ans
Python:
class LFUCache:

    def __init__(self, capacity: int):
        self.cap = capacity
        self.fre = Counter()
        self.minFre = 0
        self.cache = {}
        self.freGroup = defaultdict(OrderedDict)

    def incrFre(self, key):
        curFre = self.fre[key]
        del self.freGroup[curFre][key]
        if not self.freGroup[curFre]:
            del self.freGroup[curFre]
            if self.fre[key] == self.minFre:
                self.minFre += 1
        
        curFre = self.fre[key] = curFre + 1
        self.freGroup[curFre][key] = True

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        
        ans = self.cache[key]
        self.incrFre(key)
        return ans
    
    def evict(self):
        group = self.freGroup[self.minFre]
        toDeleteKey, _ = group.popitem(last=False)
        del self.cache[toDeleteKey]
        del self.fre[toDeleteKey]
        if not group:
            del self.freGroup[self.minFre]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache[key] = value
            self.incrFre(key)
            return
        
        if len(self.cache) == self.cap:
            self.evict()

        self.cache[key] = value
        self.minFre = 1
        self.fre[key] = 1
        self.freGroup[1][key] = True
 
Last edited:
Sắp được nửa năm rồi, chắc tới tháng 10 là lượm 300 days badge :ah:
Binary search on the answer
Python:
class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        n = len(bloomDay)
        def isPossible(target):
            bouquets = 0
            count = 0
            for i in range(n):
                if bloomDay[i] <= target:
                    count += 1
                    if count == k:
                        bouquets += 1
                        count = 0
                else:
                    count = 0

                if bouquets == m:
                    return True

            return False

        left = 1
        right = max(bloomDay)
        ans = -1
        while left <= right:
            mid = left + (right - left)//2
            if isPossible(mid):
                ans = mid
                right = mid - 1
            else:
                left = mid + 1

        return ans
 
Last edited:
Bài này là làm theo cái template BS của 1 idol leetcode nào đó
JavaScript:
function minDays(bloomDay: number[], m: number, k: number): number {
    const feasible = (days: number) => {
        let bon = 0, flow = 0;
        for (const bloom of bloomDay) {
            if (bloom > days) {
                flow = 0
            } else {
                bon+= ~~((flow + 1) / k);
                flow = (flow + 1) % k
            }
        }
        return bon >= m
    }

    let left = 0, right = 0;
    for (const bloom of bloomDay) {
        if (bloom > right) {
            right = bloom;
        }
    }
    if (m * k > bloomDay.length) {
        return -1;
    }

    while (left < right) {
        const mid = left + ~~((right - left) / 2);
        if (feasible(mid)) {
            right = mid
        } else {
            left = mid + 1;
        }
    }
    return left
};
 
Back
Top