Leetcode刷題學習筆記 – Greedy + heap

Introduce

keyword : maximum, minimum

1. 排序，這樣才可以從最小或是最大開始取。(sort)
2. 判斷取這個之後符不符合條件
3. 再取下一個 (Greedy)
4. 把取過的結果丟進heap裡面，因為如果以後需要可以拿出來用。(從過去的數值中，選一個最大/最小的數值出來)(heap)

heap: 走訪過的資料中，可以快速取出最大/最小的數值。

1647. Minimum Deletions to Make Character Frequencies Unique

給你一個字串s，good的定義是字串內char出現的頻率都不一樣。試問最少要刪除多少char才可以使s變成good。

1. 刪除最少的char，表示s是最長的good string。
2. 從Greedy的角度來說，我從最大freq的char開始取，遇到相同freq的char就少1，這樣就可以得到最大的good string。
3. 使用max-heap來排序。每次都從最大freq的char來取。
4. 使用maxAllow來記錄目前最大的freq是多少。
5. 因為heap是拿來排序用，也可以使用sort來排序。

int minDeletions(string s) {
    vector<int> freq(26);
    for(auto& c : s) freq[c - 'a']++;
    priority_queue<int> pq(freq.begin(), freq.end());
    int rtn = 0, maxAllow = s.size();
    while(!pq.empty()) {
        int val = pq.top();
        if(val == 0) break;
        if(val >= maxAllow) {
            rtn += val - maxAllow;
            // 更新val到maxAllow
            // 為了下面的式子可以更general一點
            val = maxAllow; 
        }
        // 因為val已經用過了，所以取val - 1
        // maxAllow不能低於0
        maxAllow = max(0, val - 1); 
        pq.pop();
    }
    return rtn;
}

time complexity : O(N) + O(KlogK) + O(KlogK)
space complexity : O(1) 不管s長度為何皆為vector<int>(26)

630. Course Schedule III

給你一個課程列表vector<vector<int>> courses，其中courses[i][0]表示課程持續的時間，courses[i][1]表示可以修這門課的最後時間。每一個時間只能修一門課，試問最多可以修多少課。

1. 從Greedy的角度來說，越早結束的課要先修，如果超過時間，則退選需要最長時間的課，因為這樣有越多時間可以修更多課。
2. 越早結束的課要先修 –> 使用sort依據lastday對課程排序。
3. 退選需要最長時間的課 –> 使用max-heap來記錄修過的課中最長duration的課。

class Solution {
    enum state {duration, lastday};
public:
    int scheduleCourse(vector<vector<int>>& courses) {
        sort(courses.begin(), courses.end(), [&](vector<int>& a, vector<int>& b){
            return a[1] < b[1];    
        });
        int rtn = 0, cur = 0;
        priority_queue<int> pq;
        for(int i = 0; i < courses.size(); ++i) {
            cur += courses[i][duration]; // 修這門課
            pq.push(courses[i][duration]); // 紀錄修過的課
            // 如果修這門課會超過lastday
            if(cur > courses[i][lastday]) {
                // 退選目前duration最長的課
                cur -= pq.top();    
                pq.pop();
            } else
                rtn++;
        }
        return rtn;
    }
};

2279. Maximum Bags With Full Capacity of Rocks

給你幾個袋子，每個袋子有最大容量和已經放進去的rocks，並且給你一些額外的additionalRocks，試問最多可以裝買多少袋子。

1. 問題是要裝滿最多的袋子。所以從快滿的袋子開始裝，就可以達到最多的袋子。
2. 使用priority_queue(min-heap)來存放每個袋子剩多少裝滿的數值。
3. 每次都取最小數值出來計算。

int maximumBags(vector<int>& capacity, vector<int>& rocks, int additionalRocks) {
    priority_queue<int, vector<int>, greater<int>> pq;
    int ans = 0;
    int sz = capacity.size();
    for(int i = 0; i < sz; ++i) {
        int diff = capacity[i] - rocks[i];
        if(diff == 0) ans++;
        else pq.push(diff);
    }
    while(!pq.empty() && additionalRocks) {
        int v = pq.top(); pq.pop();
        if(additionalRocks >= v) {
            ans++;
            additionalRocks -= v;
        } else
            break;
    }
    return ans;
}

871. Minimum Number of Refueling Stops

1. 目標是找到加最少次的油，就可以到達終點。
   因為車子有油桶無限大，加最少次–> 每次都加最多的那一個。

enum st{pos, fuel};
int minRefuelStops(int target, int cur, vector<vector<int>>& s) {
    // cur : 目前最遠可以到達的位置
    // i   : 目前所在的gas stations
    // res : 結果
    int i = 0, res = 0;
    priority_queue<int>pq;
    while (cur < target) {
        for (; i < s.size() && s[i][pos] <= cur; ++i) // 把目前的油用完會遇到的加油站都推到pq
            pq.push(s[i][fuel]);
        if (pq.empty()) return -1;
        cur += pq.top(), pq.pop(); // 到目前遇到最多油的
        res++;
    }
    return res;
}

1383. Maximum Performance of a Team

給你n個工程師，每個工程師都有自己的speed和efficiency。從中選出最多k個工程師，有最大的performance。其中performance的定義為
performance = sum(speed) * min(efficiency)

1. 因為最低的efficienfy會決定群組的efficiency，所以對efficienfy排序。

class Solution {
public:
    // at most k : 最多只能有k個，因為speed為0~10^5均為正數
    // performance = sum(speed) * min(efficiency)，
    // 所以對efficiency排序，因為最小的efficiency決定了全部的efficiency
    int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
        vector<pair<int, int>> v;
        for(int i = 0; i < n; ++i) v.push_back(make_pair(efficiency[i], speed[i])); // O(N)
        sort(begin(v), end(v)); // efficiency從小到大, O(NlogN)
        long maxans = 0;
        long sum = 0;
        priority_queue<int, vector<int>, greater<int>> pq; //min-heap
        for(int i = n - 1; i >= 0; --i) { // O(NlogK)
            sum += v[i].second;
            pq.push(v[i].second);
            if(pq.size() > k) {
                sum -= pq.top();
                pq.pop();
            }
            maxans = max(maxans, sum * v[i].first);
        }
        // time  : O(N + NlogN + NlogK)
        // space : O(N + K)
        return maxans % static_cast<int>(1e9 + 7);
    }
};                                               

857. Minimum Cost to Hire K Workers

// quality : 工作時間，wage : 最低工資
double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
    vector<pair<double, int>> v; // 時薪，工作時間
    for(int i = 0; i < wage.size(); ++i) // O(N)
        v.push_back(make_pair((double)wage[i]/quality[i], quality[i]));
    sort(begin(v), end(v)); // O(NlogN)
    priority_queue<int> pq; //max-heap
    auto minans{DBL_MAX};
    int qsum{0};
    for(const auto& [r, q] : v) { // O(NlogK)
        qsum += q;
        pq.push(q);
        if(pq.size() > k) qsum -= pq.top(), pq.pop(); // 因為只要k個人，剔除最長工時的worker
        if(pq.size() == k) minans = min(minans, qsum * r); // 使用目前最高時薪付薪水
    }
    // time  : O(N + NlogN + NlogK) = O(NlogN)
    // space : O(N + N) = O(N)
    return minans;
}

LCP 30. 魔塔游戏

1. 當hp < 1的時候，必須從過去經過會損傷的，選一個最大的出來 -> greedy point.
2. 既然是從過去會損傷的選一個最大的 => priority_queue
3. 必須先推入，再判斷，因為當前的也有可能跳過。

class Solution {
public:
    int magicTower(vector<int>& nums) {
        long long total = accumulate(begin(nums), end(nums), 0LL);
        if(total + 1 <= 0) return -1;
        priority_queue<int> pq;
        long long blood{1}, ans{};
        for(auto& n : nums) {
            blood += n;
            // ***先推入，因為當前這個也會進入pq判斷***
            if(n < 0) pq.push(-n); 
            while(!pq.empty() && blood <= 0) {
                blood += pq.top();
                pq.pop();
                ans++;
            }
        }
        return ans;
    }
};

1642. Furthest Building You Can Reach

1. 參考lee215答案
2. 先使用ladders，
3. 沒了ladders再使用bricks
4. 如果bricks不夠，就從之前使用過ladders選一個最小的出來
5. 因為高度差小使用ladders太浪費了
6. 為什麼先使用ladders? 因為每個高度差都要用ladders和bricks來比較。先使用ladders最後在使用pq中的bricks會讓每個高度差兩種可能比較過。才可以得到最佳解。

class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
        int sz = heights.size();
        priority_queue<int> pq;// maxheap，但是推進去-d當成minheap使用
        for(int i = 0; i < sz - 1; ++i) { // O(NlogN)
            int d = heights[i + 1] - heights[i];
            if(d > 0) pq.push(-d); // 先使用ladders
            if(pq.size() > ladders) { // 超過最大的ladders
                bricks += pq.top(); // 改使用bricks
                pq.pop();
            }
            if(bricks < 0) return i;
        }
        return sz - 1;
        // time : O(NlogN)
        // space : O(N)
    }
};

tags: leetcode 刷題