class Solution {
public:
struct Status {
int val;
ListNode *ptr;
bool operator < (const Status &rhs) const {
return val > rhs.val;
}
};
priority_queue <Status> q;
ListNode* mergeKLists(vector<ListNode*>& lists) {
for (auto node: lists) {
if (node) q.push({node->val, node});
}
ListNode head, *tail = &head;
while (!q.empty()) {
auto f = q.top(); q.pop();
tail->next = f.ptr;
tail = tail->next;
if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});
}
return head.next;
}
};
这是力扣上原题的使用优先队列合并法,来个负责任的大佬,回答我几个问题
问:bool operator < (const Status &rhs) const {return val > rhs.val; }既然是return val>rhs.val,为什么不写成bool operator>,这个重载有什么意义呢
问:bool operator<能对Status &rhs有什么作用
问:if (node) q.push({node->val, node});为什么不直接写成q.push(node->val),这是个什么结构
问:struct里int val;ListNode *ptr;bool operator < (const Status &rhs) const,三个变量有什么关联呢,我感觉ptr和val完全没有任何交集啊,这三个量,在这个函数里是怎么互相作用的
问:为什么官方解答要特地用优先级队列priorityqueue呢,我还是想不明白
问:ptr谁给他赋值的呢,从头到尾被赋值的不只有q和f和tail吗,ptr在struct里起到什么角色啊
来个认真负责任的大佬,希望能仔细举例一下符号重载
std::priority_queue
模板类等第三个模板参数Compare
默认是std::less
,std::priority_queue<Status> q
则要求Status
结构体必须提供operator<
比较运算符。当然你也可以使用别的严格弱序比较函数对象,那么你就必须在实例化std::priority_queue
时提供第三个模板参数Status::operator<
只是比较两个Status结构体,这里的作用是让q
优先队列按Status::value
降序排列q
队列里的值是Status
结构体,插入的话须提供一个Status
结构体,q.push({node->value, node})
这里是用初始化列表构建一个Status
结构体,这是C++11语法val
和ptr
是在每次push
时赋值的。