每日算法刷题Day62:8.16:leetcode 堆8道题，用时2h30min

12. 2233. K次增加后的最大乘积(中等)

2233. K 次增加后的最大乘积 - 力扣（LeetCode）

思想

1.给你一个非负整数数组 nums 和一个整数 k 。每次操作，你可以选择 nums 中 任一 元素并将它 增加 1 。
请你返回 至多 k 次操作后，能得到的 nums的 最大乘积 。由于答案可能很大，请你将答案对 109 + 7 取余后返回。
2.贪心策略给最小的元素加1，理由如下:
以两个数a,b举例，若a>b,则a*(b+1)=ab+a>(a+1)*b=ab+b
多个数同乐
3.每次取最小元素，所以为小顶堆

代码

class Solution {
public:typedef long long ll;const int mod = 1e9 + 7;int maximumProduct(vector<int>& nums, int k) {int n = nums.size();priority_queue<ll, vector<ll>, greater<ll>> pq(nums.begin(),nums.end());while (k) {ll x = pq.top();pq.pop();pq.push(x + 1);--k;}ll res = 1;while (!pq.empty()) {ll x = pq.top();pq.pop();res = (res * x) % mod;}return res;}
};

13. 3296. 移山所需的最少秒数(中等,学习)

3296. 移山所需的最少秒数 - 力扣（LeetCode）

思想

1.给你一个整数 mountainHeight 表示山的高度。
同时给你一个整数数组 workerTimes，表示工人们的工作时间（单位：秒）。
工人们需要 同时 进行工作以 降低 山的高度。对于工人 i :

• 山的高度降低 x，需要花费 workerTimes[i] + workerTimes[i] * 2 + ... + workerTimes[i] * x 秒。例如：
  • 山的高度降低 1，需要 workerTimes[i] 秒。
  • 山的高度降低 2，需要 workerTimes[i] + workerTimes[i] * 2 秒，依此类推。
    返回一个整数，表示工人们使山的高度降低到 0 所需的 最少 秒数。
    2.首先肯定是最小堆，但是按什么排序要考虑清楚，现在所有的工人是并行操作的，所以是取总的最小值，不是累加。然后能取出来说明山的高度还得降，所以要考虑该工人之前的总耗时加上当前降低山的高度1的耗时，这个总耗时最低的放在堆顶，同时也是最终答案，保证了最终答案最小。所以得知道之前总耗时和当次耗时，当次耗时可以累加基准耗时得到，所以用结构体实现。

代码

class Solution {
public:typedef long long ll;struct Node {ll total; // 总耗时ll next;  // 下一次降低1耗时ll base;  // 基础耗时Node(ll _total, ll _next, ll _base): total(_total), next(_next), base(_base) {}};struct cmp {bool operator()(const Node& a, const Node& b) {return a.total + a.next >b.total +b.next; // 最小堆堆顶为当前总耗时加上下一次耗时总和的最小值}};priority_queue<Node, vector<Node>, cmp> pq;long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {int n = workerTimes.size();for (int i = 0; i < n; ++i) {pq.push(Node(0, workerTimes[i], workerTimes[i]));}ll res = 0;while (mountainHeight) {auto tmp = pq.top();pq.pop();res = tmp.total + tmp.next;pq.push(Node(res, tmp.next + tmp.base, tmp.base));--mountainHeight;}return res;}
};

14. 1942. 最小未被占据椅子的编号(中等,学习)

1942. 最小未被占据椅子的编号 - 力扣（LeetCode）

思想

1.有 n 个朋友在举办一个派对，这些朋友从 0 到 n - 1 编号。派对里有 无数 张椅子，编号为 0 到 infinity 。当一个朋友到达派对时，他会占据 编号最小 且未被占据的椅子。

• 比方说，当一个朋友到达时，如果椅子 0 ，1 和 5 被占据了，那么他会占据 2 号椅子。
  当一个朋友离开派对时，他的椅子会立刻变成未占据状态。如果同一时刻有另一个朋友到达，可以立即占据这张椅子。
  给你一个下标从 0 开始的二维整数数组 times ，其中 times[i] = [arrivali, leavingi] 表示第 i 个朋友到达和离开的时刻，同时给你一个整数 targetFriend 。所有到达时间 互不相同 。
  请你返回编号为 targetFriend 的朋友占据的 椅子编号 。
  2.模拟题，首先肯定按到达时间升序遍历，当这个朋友来的时候，首先是之前的朋友的离开时间在当前朋友到达时间之前，则释放椅子，然后获得编号最小且未被占据的椅子，这个需要一个优先队列，然后再记录当前朋友的离开时间和座位号。接下来的问题就是你怎么遍历之前朋友的离开时间，然后判断是否在到达时间之前，因为也是按顺序的，所以也需要一个优先队列，按照离开时间最早的最小堆，同时要记录座位号，所以是个二元组即可。
  3.模拟题先想清楚一次的流程，然后思考这次流程中需要什么数据结构，具体为数据存什么，存取数据有什么特别的顺序，最后思考多次流程的遍历顺序。

代码

class Solution {
public:struct Node {int idx;int start;int end;Node(int _idx, int _start, int _end): idx(_idx), start(_start), end(_end) {}bool operator<(const Node& other) { return start < other.start; }};vector<Node> vec;typedef pair<int, int> PII;int smallestChair(vector<vector<int>>& times, int targetFriend) {int n = times.size();int res = 0;for (int i = 0; i < n; ++i) {vec.push_back(Node(i, times[i][0], times[i][1]));}sort(vec.begin(), vec.end());priority_queue<PII, vector<PII>, greater<PII>>pqEnd; // 离开时间-座位号，离开时间最小的小根堆priority_queue<int, vector<int>, greater<int>> pqSeat; // 座位号小根堆for (int i = 0; i < n; ++i)pqSeat.push(i);for (auto& t : vec) {// 先离开while (!pqEnd.empty() && pqEnd.top().first <= t.start) {pqSeat.push(pqEnd.top().second);pqEnd.pop();}int res = pqSeat.top();pqSeat.pop();if (t.idx == targetFriend)return res;pqEnd.push({t.end, res});}return -1;}
};

15. 1801. 积压订单中的订单总数(中等)

1801. 积压订单中的订单总数 - 力扣（LeetCode）

思想

1.给你一个二维整数数组 orders ，其中每个 orders[i] = [pricei, amounti, orderTypei] 表示有 amounti 笔类型为 orderTypei 、价格为 pricei 的订单。
订单类型 orderTypei 可以分为两种：

• 0 表示这是一批采购订单 buy
• 1 表示这是一批销售订单 sell
  注意，orders[i] 表示一批共计 amounti 笔的独立订单，这些订单的价格和类型相同。对于所有有效的 i ，由 orders[i] 表示的所有订单提交时间均早于 orders[i+1] 表示的所有订单。
  存在由未执行订单组成的 积压订单 。积压订单最初是空的。提交订单时，会发生以下情况：
• 如果该订单是一笔采购订单 buy ，则可以查看积压订单中价格 最低 的销售订单 sell 。如果该销售订单 sell 的价格 低于或等于 当前采购订单 buy 的价格，则匹配并执行这两笔订单，并将销售订单 sell 从积压订单中删除。否则，采购订单 buy 将会添加到积压订单中。
• 反之亦然，如果该订单是一笔销售订单 sell ，则可以查看积压订单中价格 最高 的采购订单 buy 。如果该采购订单 buy 的价格 高于或等于 当前销售订单 sell 的价格，则匹配并执行这两笔订单，并将采购订单 buy 从积压订单中删除。否则，销售订单 sell 将会添加到积压订单中。
  输入所有订单后，返回积压订单中的 订单总数 。由于数字可能很大，所以需要返回对 109 + 7 取余的结果。
  2.根据题意，销售订单是小根堆，采购订单是大根堆，然后按照题意模拟，但是注意堆中元素不单单只记录价格，不然同一个价格数量太多堆中元素太多内存太大，可以存价格-数量的二元组，然后来进行数量抵消。

代码

class Solution {
public:const int mod = 1e9 + 7;typedef long long ll;typedef pair<int, int> PII; // 价格-数量int getNumberOfBacklogOrders(vector<vector<int>>& orders) {int n = orders.size();priority_queue<PII, vector<PII>, greater<PII>> pqSell; // 销售订单priority_queue<PII> pqBuy;                             // 采购订单for (int i = 0; i < n; ++i) {int price = orders[i][0], amount = orders[i][1],type = orders[i][2];int tmp = amount;if (type == 0) {while (!pqSell.empty() && pqSell.top().first <= price &&tmp > 0) {int SellPrice = pqSell.top().first;int cnt = pqSell.top().second;pqSell.pop();if (cnt > tmp) {cnt -= tmp;tmp = 0;pqSell.push({SellPrice, cnt});} else {tmp -= cnt;}}if (tmp > 0)pqBuy.push({price, tmp});} else {while (!pqBuy.empty() && pqBuy.top().first >= price &&tmp > 0) {int BuyPrice = pqBuy.top().first;int cnt = pqBuy.top().second;pqBuy.pop();if (cnt > tmp) {cnt -= tmp;tmp = 0;pqBuy.push({BuyPrice, cnt});} else {tmp -= cnt;}}if (tmp > 0)pqSell.push({price, tmp});}}ll res = 0;while (!pqBuy.empty()) {res = (res + pqBuy.top().second) % mod;pqBuy.pop();}while (!pqSell.empty()) {res = (res + pqSell.top().second) % mod;pqSell.pop();}return res;}
};

16. 2406. 将区间分为最少组数(中等,学习)

2406. 将区间分为最少组数 - 力扣（LeetCode）

思想

1.给你一个二维整数数组 intervals ，其中 intervals[i] = [lefti, righti] 表示 闭 区间 [lefti, righti] 。
你需要将 intervals 划分为一个或者多个区间 组 ，每个区间 只 属于一个组，且同一个组中任意两个区间 不相交 。
请你返回 最少 需要划分成多少个组。
如果两个区间覆盖的范围有重叠（即至少有一个公共数字），那么我们称这两个区间是 相交 的。比方说区间 [1, 5] 和 [5, 8] 相交。
2.首先区间肯定是按left升序排序遍历，然后利用贪心思想，要让组数更少，即让当前区间尽可能地能纳入一个组，而不是新开一个组，而纳入一个组就是要找所有组里面目前最小的right,如果left>right，则能纳入一个组里面，所以找最小的right就是最小堆，堆中每个元素就是一个组当前的right,最终堆的大小就是组的大小。

代码

class Solution {
public:int minGroups(vector<vector<int>>& intervals) {int n = intervals.size();priority_queue<int, vector<int>, greater<int>> pq;sort(intervals.begin(), intervals.end());for (int i = 0; i < n; ++i) {int left = intervals[i][0], right = intervals[i][1];if (!pq.empty() && pq.top() < left)pq.pop(); // 区间不重合，归为一组pq.push(right);}return pq.size();}
};

17. 3478. 选出和最大的K个元素(中等)

3478. 选出和最大的 K 个元素 - 力扣（LeetCode）

思想

1.给你两个整数数组，nums1 和 nums2，长度均为 n，以及一个正整数 k 。
对从 0 到 n - 1 每个下标 i ，执行下述操作：

• 找出所有满足 nums1[j] 小于 nums1[i] 的下标 j 。
• 从这些下标对应的 nums2[j] 中选出 至多 k 个，并 最大化 这些值的总和作为结果。
  返回一个长度为 n 的数组 answer ，其中 answer[i] 表示对应下标 i 的结果。
  2.此题首先第一个难点是" 找出所有满足 nums1[j] 小于 nums1[i] 的下标 j ",遍历太耗时，故而想到按照nums1[i]升序排序，在它左边的就是比它小的，因为要用下标得到nums2[j]的值，故而需要一个值-下标的二元组，而nums2[j]需要找前K大的，所以是top-k问题，使用最小堆维护。
  但是一开始写完遇到一个问题，即多个nums1[i]=nums1[j]时，遍历j时最小堆里面不能纳入i，他们的答案应该一样，故想到分组循环，找到nums1[i]相等的[i,j)区间，对这个区间实施同一操作。

代码

class Solution {
public:typedef pair<int, int> PII; // 值-下标typedef long long ll;vector<long long> findMaxSum(vector<int>& nums1, vector<int>& nums2,int k) {int n = nums1.size();vector<long long> res(n, 0);vector<PII> vec;for (int i = 0; i < n; ++i) {vec.push_back({nums1[i], i});}sort(vec.begin(), vec.end());ll sum = 0;priority_queue<int, vector<int>, greater<int>> pq;int j = 0;for (int i = 0; i < n; i = j) {j = i + 1;while (j < n && vec[i].first == vec[j].first)++j;ll tmp = sum;// [i,j)for (int z = i; z < j; ++z) {int idx = vec[z].second;int val = nums2[idx];res[idx] = tmp;pq.push(val);sum += val;if (pq.size() > k) {sum -= pq.top();pq.pop();}}}return res;}
};

18. 2462. 雇佣K位工人的总代价(中等,左开右闭逻辑理顺,两个小根堆更快，学习)

2462. 雇佣 K 位工人的总代价 - 力扣（LeetCode）

思想

1.给你一个下标从 0 开始的整数数组 costs ，其中 costs[i] 是雇佣第 i 位工人的代价。
同时给你两个整数 k 和 candidates 。我们想根据以下规则恰好雇佣 k 位工人：

• 总共进行 k 轮雇佣，且每一轮恰好雇佣一位工人。
• 在每一轮雇佣中，从最前面 candidates 和最后面 candidates 人中选出代价最小的一位工人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。
  • 比方说，costs = [3,2,7,7,1,2] 且 candidates = 2 ，第一轮雇佣中，我们选择第 4 位工人，因为他的代价最小 [_3,2_,7,7,_**1**,2_] 。
  • 第二轮雇佣，我们选择第 1 位工人，因为他们的代价与第 4 位工人一样都是最小代价，而且下标更小，[_3,**2**_,7,_7,2_] 。注意每一轮雇佣后，剩余工人的下标可能会发生变化。
• 如果剩余员工数目不足 candidates 人，那么下一轮雇佣他们中代价最小的一人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。
• 一位工人只能被选择一次。
  返回雇佣恰好 k 位工人的总代价。
  2.可以用一个总堆(元素是包含下标的二元组，因为要区分处于哪个区间)或者两个小根堆(元素只有代价，更简单)模拟，然后再加上左右指针，只不过记得左指针开，右指针闭，两者处理顺序不一样
  3.但是两个小根堆更好，因为堆中元素越大，push操作越慢
  4.提前判断可以省很多事，通过判断candidates*2+k>n,则说明会产生元素重复，数组所有元素都要考虑，就变成求前top-k小元素的和了，同时可以省略下面idxL<idxR的判断

代码

class Solution {
public:typedef pair<int, int> PII; // 代价-下标typedef long long ll;long long totalCost(vector<int>& costs, int k, int candidates) {int n = costs.size();ll res = 0;priority_queue<PII, vector<PII>, greater<PII>> pq;int idxL = candidates, idxR = n - candidates;// [0,idxL),[idxR,n)if (idxL < idxR) {for (int i = 0; i < idxL; ++i)pq.push({costs[i], i});for (int i = idxR; i < n; ++i)pq.push({costs[i], i});} else {for (int i = 0; i < n; ++i)pq.push({costs[i], i});}while (k) {auto tmp = pq.top();pq.pop();int cost = tmp.first, idx = tmp.second;res += cost;if (idxL < idxR) {if (idx < idxL) {pq.push({costs[idxL], idxL});++idxL;} else if (idx >= idxR) {--idxR;pq.push({costs[idxR], idxR});}}--k;}return res;}
};

两个小根堆:

class Solution {
public:typedef long long ll;long long totalCost(vector<int>& costs, int k, int candidates) {int n = costs.size();ll res = 0;if (candidates * 2 + k > n) {// 找top-k小,大根堆priority_queue<int> pq;for (int i = 0; i < n; ++i) {pq.push(costs[i]);res += costs[i];if (pq.size() > k) {res -= pq.top();pq.pop();}}return res;}int idxL = candidates, idxR = n - candidates;priority_queue<int, vector<int>, greater<int>> pqL, pqR;// [0,idxL),[idxR,n)for (int i = 0; i < idxL; ++i)pqL.push(costs[i]);for (int i = idxR; i < n; ++i)pqR.push(costs[i]);while (k--) {if (pqL.top() <= pqR.top()) {res += pqL.top();pqL.pop();pqL.push(costs[idxL]);++idxL;} else {res += pqR.top();pqR.pop();--idxR;pqR.push(costs[idxR]);}}return res;}
};

19. 1834. 单线程CPU(中等,学习)

1834. 单线程 CPU - 力扣（LeetCode）

思想

1.给你一个二维数组 tasks ，用于表示 n​​​​​​ 项从 0 到 n - 1 编号的任务。其中 tasks[i] = [enqueueTimei, processingTimei] 意味着第 i​​​​​​​​​​ 项任务将会于 enqueueTimei 时进入任务队列，需要 processingTimei 的时长完成执行。
现有一个单线程 CPU ，同一时间只能执行 最多一项 任务，该 CPU 将会按照下述方式运行：

• 如果 CPU 空闲，且任务队列中没有需要执行的任务，则 CPU 保持空闲状态。
• 如果 CPU 空闲，但任务队列中有需要执行的任务，则 CPU 将会选择 执行时间最短 的任务开始执行。如果多个任务具有同样的最短执行时间，则选择下标最小的任务开始执行。
• 一旦某项任务开始执行，CPU 在 执行完整个任务 前都不会停止。
• CPU 可以在完成一项任务后，立即开始执行一项新任务。
  返回 CPU 处理任务的顺序。
  2.首先这题不能按照任务来遍历(注意，卡了好久)，因为CPU是一空闲就会取下一个待执行的任务执行，而不会等到下一个遍历的任务来。
  其次，不能按照时间累加遍历，因为太慢了，会超时。
  所以时间得跳着来。
• (1)当前无任务队列，时间跳到下一个待遍历的任务
• (2)当前有任务队列，则取出完成，然后时间直接跳到完成时间
• (3)任务首先入队列，因为时间是跳着来的，(2)的情况可能会有多个任务入队列，所以要用while循环

代码

class Solution {
public:typedef long long ll;struct Node {int start;int last;int idx;Node(int _start, int _last, int _idx): start(_start), last(_last), idx(_idx) {}bool operator<(const Node& other) { return start < other.start; }};struct cmp {bool operator()(const Node& a, const Node& b) {if (a.last != b.last)return a.last > b.last;elsereturn a.idx > b.idx;}};priority_queue<Node, vector<Node>, cmp> pq;vector<Node> vec;vector<int> getOrder(vector<vector<int>>& tasks) {int n = tasks.size();vector<int> res;for (int i = 0; i < n; ++i)vec.push_back(Node(tasks[i][0], tasks[i][1], i));sort(vec.begin(), vec.end());ll time = 0, i = 0;while (res.size() < n) {// time是跳跃的，所以可能之前有好多任务要入while (i < n && vec[i].start <= time) {pq.push(vec[i]);++i;}// 跳到下一个任务的入队时间if (pq.empty()) {time = vec[i].start;} else {auto tmp = pq.top();pq.pop();res.push_back(tmp.idx);time += 1LL * tmp.last; // 跳到结束时间}}return res;}
};