有入了Surface Book了的么？# PDA - 掌中宝
s*w
1 楼
不知道为啥，我的 heap 时灵时不灵的？请看下面的 code 和输出显示
#include
#include
#include
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int v):val(v),next(NULL) {}
};
bool minHeapPredicate(ListNode* lhs,ListNode* rhs) {
return lhs->val > rhs->val;
}
class Solution {
public:
ListNode *mergeKLists(vector lists) {
ListNode *retHead = NULL, *retTail = NULL;
// store values and nodes into heap
vector heads;
for(int i = 0;i < lists.size();++i)
if(lists[i])
heads.push_back(lists[i]);
make_heap(heads.begin(),heads.end(),minHeapPredicate);
// loop through all elements
while(!heads.empty()) {
// extract the min from heap
pop_heap(heads.begin(),heads.end());
ListNode* tmp = heads.back();
heads.pop_back();
// update the list pointer
ListNode *tmp2 = tmp->next;
if(tmp2) {
heads.push_back(tmp2);
cout << "before heapifying, the heap has: ";
for(int i=0;i
cout << endl;
push_heap(heads.begin(),heads.end(),minHeapPredicate);
cout << "after heapifying, the heap has: ";
for(int i=0;i
cout << endl;
}
// store tmp to ret
cout << "tmp=" << tmp->val << endl;
tmp->next = NULL;
if(retHead == NULL) {
retHead = tmp;
retTail = tmp;
} else {
retTail->next = tmp;
retTail = tmp;
}
}
return retHead;
}
};
void printList(ListNode *p) {
while(p) {
cout << p->val << "->";
p = p->next;
}
cout << endl;
}
int main() {
ListNode *p1 = new ListNode(-1);
ListNode *p2 = new ListNode(1);
p1->next = p2;
ListNode *p4 = new ListNode(-3);
ListNode *p5 = new ListNode(1);
ListNode *p6 = new ListNode(4);
p4->next = p5;
p5->next = p6;
ListNode *p7 = new ListNode(-2);
ListNode *p8 = new ListNode(-1);
ListNode *p9 = new ListNode(0);
ListNode *p10 = new ListNode(2);
p7->next = p8;
p8->next = p9;
p9->next = p10;
printList(p1);
printList(p4);
printList(p7);
vector vl;
vl.push_back(p1);
vl.push_back(p4);
vl.push_back(p7);
Solution s;
ListNode *ret = s.mergeKLists(vl);
printList(p1);
printList(p4);
printList(p7);
printList(ret);
}
outputs as follows:
-1->1->
-3->1->4->
-2->-1->0->2->
-3->1->4->
-1->1->
-2->-1->0->2->
now extracting min from heap: -3
before heapifying, the heap has: -2 -1 1
after heapifying, the heap has: -2 -1 1
-2->-1->0->2->
-1->1->
1->4->
now extracting min from heap: -2
before heapifying, the heap has: 1 -1 -1
after heapifying, the heap has: -1 -1 1
-1->0->2->
-1->1->
1->4->
now extracting min from heap: -1
before heapifying, the heap has: 1 -1 0
after heapifying, the heap has: 0 -1 1
0->2->
-1->1->
1->4->
now extracting min from heap: 0
before heapifying, the heap has: 1 -1 2
after heapifying, the heap has: 1 -1 2
1->4->
-1->1->
2->
now extracting min from heap: 1
before heapifying, the heap has: 2 -1 4
after heapifying, the heap has: 2 -1 4
2->
-1->1->
4->
now extracting min from heap: 2
4->
-1->1->
now extracting min from heap: 4
-1->1->
now extracting min from heap: -1
before heapifying, the heap has: 1
after heapifying, the heap has: 1
1->
now extracting min from heap: 1
-1->1->
-3->-2->-1->0->1->2->4->-1->1->
-2->-1->0->1->2->4->-1->1->
-3->-2->-1->0->1->2->4->-1->1->
#include
#include
#include
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int v):val(v),next(NULL) {}
};
bool minHeapPredicate(ListNode* lhs,ListNode* rhs) {
return lhs->val > rhs->val;
}
class Solution {
public:
ListNode *mergeKLists(vector
ListNode *retHead = NULL, *retTail = NULL;
// store values and nodes into heap
vector
for(int i = 0;i < lists.size();++i)
if(lists[i])
heads.push_back(lists[i]);
make_heap(heads.begin(),heads.end(),minHeapPredicate);
// loop through all elements
while(!heads.empty()) {
// extract the min from heap
pop_heap(heads.begin(),heads.end());
ListNode* tmp = heads.back();
heads.pop_back();
// update the list pointer
ListNode *tmp2 = tmp->next;
if(tmp2) {
heads.push_back(tmp2);
cout << "before heapifying, the heap has: ";
for(int i=0;i
cout << endl;
push_heap(heads.begin(),heads.end(),minHeapPredicate);
cout << "after heapifying, the heap has: ";
for(int i=0;i
cout << endl;
}
// store tmp to ret
cout << "tmp=" << tmp->val << endl;
tmp->next = NULL;
if(retHead == NULL) {
retHead = tmp;
retTail = tmp;
} else {
retTail->next = tmp;
retTail = tmp;
}
}
return retHead;
}
};
void printList(ListNode *p) {
while(p) {
cout << p->val << "->";
p = p->next;
}
cout << endl;
}
int main() {
ListNode *p1 = new ListNode(-1);
ListNode *p2 = new ListNode(1);
p1->next = p2;
ListNode *p4 = new ListNode(-3);
ListNode *p5 = new ListNode(1);
ListNode *p6 = new ListNode(4);
p4->next = p5;
p5->next = p6;
ListNode *p7 = new ListNode(-2);
ListNode *p8 = new ListNode(-1);
ListNode *p9 = new ListNode(0);
ListNode *p10 = new ListNode(2);
p7->next = p8;
p8->next = p9;
p9->next = p10;
printList(p1);
printList(p4);
printList(p7);
vector
vl.push_back(p1);
vl.push_back(p4);
vl.push_back(p7);
Solution s;
ListNode *ret = s.mergeKLists(vl);
printList(p1);
printList(p4);
printList(p7);
printList(ret);
}
outputs as follows:
-1->1->
-3->1->4->
-2->-1->0->2->
-3->1->4->
-1->1->
-2->-1->0->2->
now extracting min from heap: -3
before heapifying, the heap has: -2 -1 1
after heapifying, the heap has: -2 -1 1
-2->-1->0->2->
-1->1->
1->4->
now extracting min from heap: -2
before heapifying, the heap has: 1 -1 -1
after heapifying, the heap has: -1 -1 1
-1->0->2->
-1->1->
1->4->
now extracting min from heap: -1
before heapifying, the heap has: 1 -1 0
after heapifying, the heap has: 0 -1 1
0->2->
-1->1->
1->4->
now extracting min from heap: 0
before heapifying, the heap has: 1 -1 2
after heapifying, the heap has: 1 -1 2
1->4->
-1->1->
2->
now extracting min from heap: 1
before heapifying, the heap has: 2 -1 4
after heapifying, the heap has: 2 -1 4
2->
-1->1->
4->
now extracting min from heap: 2
4->
-1->1->
now extracting min from heap: 4
-1->1->
now extracting min from heap: -1
before heapifying, the heap has: 1
after heapifying, the heap has: 1
1->
now extracting min from heap: 1
-1->1->
-3->-2->-1->0->1->2->4->-1->1->
-2->-1->0->1->2->4->-1->1->
-3->-2->-1->0->1->2->4->-1->1->
