- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我正在尝试使用堆来解决“合并 K 个列表”的问题,即合并 k 个已排序的链表并将其作为一个已排序的列表返回。通常我创建一个最小堆来存储所有列表节点并使用预定义函数 LessThanLinkedList() 进行比较。但是我发现第 62 行和第 75 行中的 pop_heap() 操作永远不起作用。它不会删除堆的顶部,尽管我使用预定义的比较函数作为参数。以下是我的代码。我正在使用 visual studio 2010 作为 IDE。有人知道原因吗?非常感谢您的帮助!
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <list>
#include <numeric>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
using namespace std;
class Solution {
public:
static bool LessThanLinkedList( const ListNode * l1, const ListNode * l2)
{
return( l1->val > l2->val );
}
ListNode *mergeKLists(vector<ListNode *> &lists) {
int idx;
bool ball_list_null;
ListNode * pNode;
ListNode *new_head;
ball_list_null = true;
for( idx = 0; idx < lists.size(); idx++ )
{
if( NULL != lists[idx] )
{
ball_list_null = false;
break;
}
}
if( true == ball_list_null )
return(NULL);
vector< ListNode* > list_heap;
for( idx = 0; idx < lists.size(); idx++ )
{
if( NULL != lists[idx] )
{
pNode = lists[idx];
while( NULL != pNode )
{
list_heap.push_back( pNode );
pNode = pNode->next;
}
}
}
make_heap( list_heap.begin(), list_heap.end(), LessThanLinkedList );
if(list_heap.size() > 0)
{
new_head = list_heap[0];
pop_heap( list_heap.begin(), list_heap.end(), LessThanLinkedList );//not work
}
if( list_heap.size() == 0 )
{
new_head->next = NULL;
}
else
{
pNode = new_head;
while( list_heap.size() >0 )
{
pNode->next = list_heap[0];
pop_heap( list_heap.begin(), list_heap.end(), LessThanLinkedList ); // not work
pNode = pNode->next ;
}
pNode->next = NULL;
}
return( new_head );
}
};
void main()
{
Solution xpfsln;
ListNode *l1,*l2,*l3,*l4,*l5,*l6,*l7,*head;
l1 = new ListNode(1);
l2 = new ListNode(2);
l3 = new ListNode(3);
l1->next = l2;
l2->next = l3;
l3->next = NULL;
vector<ListNode *> list_vec;
list_vec.push_back(l1);
head = xpfsln.mergeKLists( list_vec );
}
最佳答案
pop_heap
不会从容器中移除元素。它不能,因为它甚至不能访问容器,只能访问它的元素。它所做的(当然假设 [begin, end)
形成一个有效的非空堆)是重新排列元素,使得堆的第一个元素移动到范围的最后一个元素, 并将 [begin, end-1)
保留为有效堆。如果你想真正从容器中删除元素,你只需要在调用 pop_heap
之后删除容器的最后一个元素(例如调用 pop_back()
) >.
pop_heap( list_heap.begin(), list_heap.end(), LessThanLinkedList );
list_heap.pop_back();
关于C++ STL pop_heap 不工作,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26495293/
我正在尝试使用堆来解决“合并 K 个列表”的问题,即合并 k 个已排序的链表并将其作为一个已排序的列表返回。通常我创建一个最小堆来存储所有列表节点并使用预定义函数 LessThanLinkedList
我有一个带有函数的 Node 类 static bool HasGreaterF(const Node& a, const Node& b); static bool HasGreaterF(cons
我需要使用堆,所以我搜索了 STL,但它似乎不起作用,我写了一些代码来解释我的意思: #include #include #include #include struct data {
我必须将一些 C++ 代码转换为 Python 以进行部署,目前正在努力实现 C++ STL 堆数据结构。 我目前在 Python 中实现了以下类: class Heap: def __init__(
我想维护一个有效负载为 MoveConstructible 的堆(因为它们在内部包含一个 std::unique_ptr。)虽然 documentation建议对象必须是 MoveAssignable
我是一名优秀的程序员,十分优秀!