g***j
发帖数: 1275 | 1 做leedcode上面的关于k-way merge的题目，题目是
Merge k sorted linked lists and return it as one sorted list.
如下的code通过不了，似乎是因为我在priority_queue里面用了指针
std::priority_queue, CompareNode> myQ;
因为如果我改成
std::priority_queue, CompareNode> myQ;
并且把其他的相关->都改了dot之后，就可以全部通过了。
我用debug跟踪，发现myQ.pop()之后，虽然myQ.size()表小了，但是myQ.top()的内容
没有发生变化。
请问，这里面的trick是什么？难道这里不能用Node*么？如果是这样的，还有什么
container不能用Node*的？
大牛帮我解释一下好么？
class Pair{
public:
ListNode* node;
int index;
};
class CompareNode: public std::binary_function{
public:
bool operator()(const Pair* p, const Pair* q) const {
return p->node->val > q->node->val;
}
};
class Solution {
public:
ListNode *mergeKLists(vector &lists) {
if(lists.size() == 0) return NULL;
if(lists.size() == 1) return lists[0];
std::priority_queue, CompareNode> myQ;
vector iterators;
for(int i = 0; i < lists.size(); i++) {
iterators.push_back(lists[i]);
if( lists[i] ) {
Pair* newPair;
newPair->node = lists[i];
newPair->index = i;
iterators[i] = iterators[i]->next;
newPair->node->next = NULL;
myQ.push(newPair);
}
}
ListNode* result = NULL;
ListNode* tail = NULL;
while(!myQ.empty()) {
int index = 0;
if(!result) {
result = myQ.top()->node;
tail = result;
} else {
tail->next = myQ.top()->node;
tail = tail->next;
}
index = myQ.top()->index;
myQ.pop();
if(iterators[index]) {
Pair* newPair;
newPair->node = iterators[index];
newPair->index = index;
myQ.push(newPair);
iterators[index] = iterators[index]->next;
}
}
return result;
}
}; |
g***j
发帖数: 1275 | 2 这个code就可以全部test case都通过。改动就是指针和非指针的差别。
class Pair{
public:
ListNode* node;
int index;
};
class CompareNode: public std::binary_function{
public:
bool operator()(const Pair p, const Pair q) const {
return p.node->val > q.node->val;
}
};
class Solution {
public:
ListNode *mergeKLists(vector &lists) {
if(lists.size() == 0) return NULL;
if(lists.size() == 1) return lists[0];
std::priority_queue, CompareNode> myQ;
vector iterators;
for(int i = 0; i < lists.size(); i++) {
iterators.push_back(lists[i]);
if( lists[i] ) {
Pair newPair;
newPair.node = lists[i];
newPair.index = i;
iterators[i] = iterators[i]->next;
newPair.node->next = NULL;
myQ.push(newPair);
}
}
ListNode* result = NULL;
ListNode* tail = NULL;
while(!myQ.empty()) {
int index = 0;
if(!result) {
result = myQ.top().node;
tail = result;
} else {
tail->next = myQ.top().node;
tail = tail->next;
}
index = myQ.top().index;
myQ.pop();
if(iterators[index]) {
Pair newPair;
newPair.node = iterators[index];
newPair.index = index;
myQ.push(newPair);
iterators[index] = iterators[index]->next;
}
}
return result;
}
};
【在 g***j 的大作中提到】
: 做leedcode上面的关于k-way merge的题目，题目是
: Merge k sorted linked lists and return it as one sorted list.
: 如下的code通过不了，似乎是因为我在priority_queue里面用了指针
: std::priority_queue, CompareNode> myQ;
: 因为如果我改成
: std::priority_queue, CompareNode> myQ;
: 并且把其他的相关->都改了dot之后，就可以全部通过了。
: 我用debug跟踪，发现myQ.pop()之后，虽然myQ.size()表小了，但是myQ.top()的内容
: 没有发生变化。
: 请问，这里面的trick是什么？难道这里不能用Node*么？如果是这样的，还有什么
|
c****9
发帖数: 164 | 3 priority_queue 用指针的话，内部实现根据什么来做heap呢？ 指针本身没法比较
priority吧
比如vector queue stack这些container都不是用来比较的， map的话理论上用二叉树
实现，用指针做key似乎也不make sense. 请楼下拍砖 |
g***j
发帖数: 1275 | 4 我提供了CompareNode的比较的函数啊？
【在 c****9 的大作中提到】
: priority_queue 用指针的话，内部实现根据什么来做heap呢？ 指针本身没法比较
: priority吧
: 比如vector queue stack这些container都不是用来比较的， map的话理论上用二叉树
: 实现，用指针做key似乎也不make sense. 请楼下拍砖
|
h*******s
发帖数: 8454 | 5 没事儿就别用指针了吧
Pair* newPair; ...在这里分配内存先
newPair->node = iterators[index];
newPair->index = index;
【在 g***j 的大作中提到】
: 我提供了CompareNode的比较的函数啊？
|
