【每日Leetcode】堆系列(二)

文摘   职场   2024-07-10 16:37   上海  
【1167. 连接木棍的最低费用

你有一些长度为正整数的木棍。这些长度以数组 sticks 的形式给出, sticks[i] 是第 i 个木棍的长度。

你可以通过支付 x + y 的成本将任意两个长度为 x 和 y 的木棍连接成一个木棍。你必须连接所有的木棍,直到剩下一个木棍。

返回以这种方式将所有给定的木棍连接成一个木棍的 最小成本 。

来源:力扣(LeetCode)

链接:https://leetcode.cn/problems/minimum-cost-to-connect-sticks/description/

class Solution {public:    int connectSticks(vector<int>& sticks) {        int res = 0;        priority_queue<int, vector<int>, greater<int>> q;        for (int i = 0; i < sticks.size(); i++) {             q.push(sticks[i]);        }        while (q.size() > 1) {            int stick1 = q.top();            q.pop();            int stick2 = q.top();            q.pop();            int cost = stick1 + stick2;            res += cost;            q.push(cost);        }        return res;    }};


【253. 会议室 II之堆解法

给你一个会议时间安排的数组 intervals ,每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ,返回 所需会议室的最小数量 。

来源:力扣(LeetCode)

链接:https://leetcode.cn/problems/meeting-rooms-ii/description/

class Solution {public:    /**     * @param intervals: an array of meeting time intervals     * @return: the minimum number of conference rooms required     */    bool static cmp(Interval& a, Interval& b) {        return a.start < b.start || (a.start == b.start && a.end < b.end);    }    int minMeetingRooms(vector<Interval> &intervals) {        if (intervals.empty()) return 0;        priority_queue<int, vector<int>, greater<int>> q;        sort(intervals.begin(), intervals.end(), cmp);        q.push(intervals[0].end);        for (int i = 1; i < intervals.size(); ++i) {            // if (intervals[i].start > q.top()) {            if (intervals[i].start >= q.top()) {                q.pop();            }            q.push(intervals[i].end);        }        return q.size();    }};


【480. 滑动窗口中位数】

中位数是有序序列最中间的那个数。如果序列的长度是偶数,则没有最中间的数;此时中位数是最中间的两个数的平均数。

例如:

  • [2,3,4],中位数是 3

  • [2,3],中位数是 (2 + 3) / 2 = 2.5

给你一个数组 nums,有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数,每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数,并输出由它们组成的数组。

来源:力扣(LeetCode)

链接:https://leetcode.cn/problems/sliding-window-median/description/

一开始就调整好堆大小,然后删掉哪个里面的就加到那个里面就行了。

class Solution {public:    vector<double> medianSlidingWindow(vector<int> &nums, int k) {        vector<double> result;        int n = nums.size();        if (n == 0)            return result;
multiset<int> max, min; for (int i = 0; i < k; ++i) { max.insert(nums[i]); } for (int i = 0; i < k / 2; ++i) { min.insert(*max.rbegin()); max.erase(max.lower_bound(*max.rbegin())); } for (int i = k; i < n; ++i) { if (max.size() > min.size()) result.push_back(*max.rbegin()); else result.push_back(*min.begin() / 2.0 + *max.rbegin() / 2.0); if (max.find(nums[i - k]) != max.end()) { max.erase(max.find(nums[i - k])); max.insert(nums[i]); } else { min.erase(min.find(nums[i - k])); min.insert(nums[i]); } if (!min.empty() && !max.empty() && *min.begin() < *max.rbegin()) { int tmp = *max.rbegin(); max.erase(max.lower_bound(*max.rbegin())); max.insert(*min.begin()); min.erase(min.begin()); min.insert(tmp); } } if (max.size() > min.size()) result.push_back(*max.rbegin()); else result.push_back(*min.begin() / 2.0 + *max.rbegin() / 2.0); return result; }};


【407. 接雨水 II】

给你一个 m x n 的矩阵,其中的值均为非负整数,代表二维高度图每个单元的高度,请计算图中形状最多能接多少体积的雨水。

来源:力扣(LeetCode)

链接:https://leetcode.cn/problems/trapping-rain-water-ii/description/

先确定木桶的外围,找到外围的最短板子后对其周围能填水的地方填水,然后更新木桶外围。

class Solution {public:    int trapRainWater(vector<vector<int>>& heightMap) {        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>,             greater<tuple<int, int, int>>> q;        int n = heightMap.size();        int m = heightMap[0].size();        int res = 0;        vector<vector<int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};        vector<vector<int>> visited(n, vector<int>(m, false));        for (int i = 0; i < n; ++i) {            q.emplace(heightMap[i][0], i, 0);            visited[i][0] = true;            q.emplace(heightMap[i][m - 1], i, m - 1);            visited[i][m - 1] = true;        }        for (int i = 0; i < m; ++i) {            q.emplace(heightMap[0][i], 0, i);            visited[0][i] = true;            q.emplace(heightMap[n - 1][i], n - 1, i);            visited[n - 1][i] = true;        }        while (!q.empty()) {            int val, x, y;            tie(val, x, y) = q.top();            q.pop();            for (int i = 0; i < 4; ++i) {                int nx = x + dir[i][0];                int ny = y + dir[i][1];                if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {                    int nh = max(heightMap[nx][ny], val);                    res += nh - heightMap[nx][ny];                    q.emplace(nh, nx, ny);                    visited[nx][ny] = true;                }            }        }        return res;    }};


Arrietty刷题日记
清华计算机系学霸带你刷Leetcode(求职面试/保研考研/转计算机行业...)