keyword : maximum, minimum
heap: 走訪過的資料中，可以快速取出最大/最小的數值。
給你一個字串s，good的定義是字串內char出現的頻率都不一樣。試問最少要刪除多少char才可以使s變成good。
- 刪除最少的char，表示s是最長的good string。
- 從Greedy的角度來說，我從最大freq的char開始取，遇到相同freq的char就少1，這樣就可以得到最大的good string。
- 使用max-heap來排序。每次都從最大freq的char來取。
- 使用maxAllow來記錄目前最大的freq是多少。
- 因為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)
給你一個課程列表vector<vector<int>> courses，其中courses[i][0]表示課程持續的時間，courses[i][1]表示可以修這門課的最後時間。每一個時間只能修一門課，試問最多可以修多少課。
- 從Greedy的角度來說，越早結束的課要先修，如果超過時間，則退選需要最長時間的課，因為這樣有越多時間可以修更多課。
- 越早結束的課要先修 –> 使用sort依據lastday對課程排序。
- 退選需要最長時間的課 –> 使用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;
}
};
給你幾個袋子，每個袋子有最大容量和已經放進去的rocks，並且給你一些額外的additionalRocks，試問最多可以裝買多少袋子。
- 問題是要裝滿最多的袋子。所以從快滿的袋子開始裝，就可以達到最多的袋子。
- 使用priority_queue(min-heap)來存放每個袋子剩多少裝滿的數值。
- 每次都取最小數值出來計算。
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;
}
- 目標是找到加最少次的油，就可以到達終點。
因為車子有油桶無限大，加最少次–> 每次都加最多的那一個。
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;
}
給你n個工程師，每個工程師都有自己的speed和efficiency。從中選出最多k個工程師，有最大的performance。其中performance的定義為
performance = sum(speed) * min(efficiency)
- 因為最低的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);
}
};
// 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;
}
- 當hp < 1的時候，必須從過去經過會損傷的，選一個最大的出來 -> greedy point.
- 既然是從過去會損傷的選一個最大的 => priority_queue
- 必須先推入，再判斷，因為當前的也有可能跳過。
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;
}
};
- 參考lee215答案
- 先使用ladders，
- 沒了ladders再使用bricks
- 如果bricks不夠，就從之前使用過ladders選一個最小的出來
- 因為高度差小使用ladders太浪費了
- 為什麼先使用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)
}
};
leetcode 刷題
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe