堆结构常见题

1. 合并 k 个有序链表

给定 k 个有序链表，每个链表的元素值都按升序排列，请将它们合并为一个有序链表，并返回合并后的链表。

思路：

创建一个最小堆，将 k 个链表的头结点放入堆中。
取出堆顶的结点，将其指向的下一个结点放入堆中。

重复步骤 2，直到堆为空。

struct Cmp{ // 自定义比较规则
     bool operator()(const struct ListNode* a, const struct ListNode* b) const {
         return a->val > b->val;
     }
 };
ListNode* mergeKLists(vector<ListNode*>& lists) {
 ListNode* head = nullptr;
 ListNode* p = nullptr;
 priority_queue<ListNode*, vector<ListNode*>, Cmp> pq;
    
 for(auto& list : lists){ // 将 k 个链表的头结点放入堆中
     if(list != nullptr){
         pq.push(list);
     } 
 }
    
 if(pq.empty()){
     return nullptr;
 }
 head = pq.top(); // 取出堆顶结点
 p = head; // 第一个取出的堆顶为head
 pq.pop();
 if(head->next != nullptr){ 
     pq.push(head->next);  // 将堆顶结点指向的下一个结点放入堆中
 }

 while(!pq.empty()){ // 重复步骤 2，直到堆为空
     ListNode* top = pq.top();
     pq.pop();
     p->next = top; // 将取出的结点链接到p后面
     p = p->next; // p指向下一个结点
     if(top->next != nullptr){ 
         pq.push(top->next);  // 将取出的结点指向的下一个结点放入堆中
     }
 }

 return head;
}

2. 线段重合

每一个线段都有start和end两个数据项，表示这条线段在X轴上从start位置开始到end位置结束。给定一批线段，求所有重合区域中最多重合了几个线段，首尾相接的线段不算重合。例如：线段[1,2]和线段[2.3]不重合。线段[1,3]和线段[2,3]重合，重合区域为[2,3]。

思路：差分做法O(max_value)最简单，见此处。

最小堆做法：

将所有线段按照begin值升序排序。
遍历每条线段，当堆内元素个数大于0且堆顶元素小于等于当前线段的end值时，将堆顶元素弹出。将当前线段的end值放入堆中，并维护堆的大小（即答案）。
重复步骤2，直到所有线段遍历完，输出答案。

vector<pair<int, int>> line;
priority_queue<int, vector<int>, less<int>> heap;

bool cmp(pair<int, int> &a, pair<int, int> &b) { return a.first < b.first; }

void solve() {
    int n;
    cin >> n;
    line.resize(n);
    for (int i = 0; i < n; i++){
        cin >> line[i].first >> line[i].second;
    }
    sort(line.begin(), line.end(), cmp); // 步骤1：排序
    int ans = 0;
    for (int i = 0; i < n; i++){ // 步骤2：遍历每条线段
        while(heap.size() > 0 && heap.top() <= line[i].first){
            heap.pop();
        }
        heap.push(line[i].second);
        ans = max(ans, (int)heap.size());
    }
    cout << ans << endl;
}

3. 累加和减半的最少操作次数

思路：

先求出数组的累加和sum，并求出sum的二分之一diff。并将数组元素放入最大堆中。
贪心的将最大堆堆顶的元素减少一半，并将其放入最小堆中。diff减去top/2，ans加一。
重复步骤2，直到diff小于等于0。

int halveArray(vector<int> &nums) {
    priority_queue<double> pque;
    long long sum = 0;
    int ans = 0;
    for (auto num : nums) {
        sum += num;
        pque.push(num);
    }
    double diff = 1.0 * sum / 2;

    while (diff > 0) {
        double t = pque.top();
        pque.pop();
        t /= 2;
        diff -= t;
        ans++;
        pque.push(t);
    }
    return ans;
}

优化：由于double的精度问题，可以将num乘以2^20，转化为long long类型计算，这样就可以避免double的精度问题。

int halveArray(vector<int> &nums) {
    priority_queue<long long> pque;
    long long sum = 0;
    int ans = 0;
    for (auto num : nums) {
        long long temp = num; // 不要直接对num进行移位，可能会导致溢出
        temp <<= 20;
        sum += temp;
        pque.push(temp);
    }
    long long diff = sum / 2;

    while (diff > 0) {
        long long t = pque.top();
        pque.pop();
        t /= 2;
        diff -= t;
        ans++;
        pque.push(t);
    }
    return ans;
}

堆结构常见题

堆结构常见题

1. 合并 k 个有序链表

2. 线段重合

3. 累加和减半的最少操作次数

CATALOG

FEATURED TAGS

FRIENDS