leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0023.cpp (1445B)

0 // Naive solution, barely passed 1 class Solution { 2 public: 3 ListNode *mergeKLists(vector<ListNode *> &lists) { 4 ListNode *dummy, *tmp; 5 tmp = dummy = new ListNode; 6 7 while (true) { 8 int mini = INT_MAX, index = -1; 9 for (int i = 0; i < lists.size(); i++) { 10 if (lists[i] && lists[i]->val < mini) { 11 index = i; 12 mini = lists[i]->val; 13 } 14 } 15 if (index == -1) break; 16 ListNode *t = lists[index]; 17 lists[index] = lists[index]->next; 18 tmp = tmp->next = t; 19 } 20 return dummy->next; 21 } 22 }; 23 24 // Proper solution 25 class Solution { 26 typedef pair<int, int> pii; 27 28 public: 29 ListNode *mergeKLists(vector<ListNode *> &lists) { 30 ListNode *dummy, *tmp; 31 tmp = dummy = new ListNode; 32 33 auto cmp = [](const pii &a, const pii &b) { return a.first > b.first; }; 34 priority_queue<pii, vector<pii>, decltype(cmp)> pq(cmp); 35 for (int i = 0; i < lists.size(); i++) 36 if (lists[i]) pq.push({lists[i]->val, i}); 37 while (!pq.empty()) { 38 int index = pq.top().second; 39 pq.pop(); 40 ListNode *t = lists[index]; 41 lists[index] = lists[index]->next; 42 if (lists[index]) pq.push({lists[index]->val, index}); 43 tmp = tmp->next = t; 44 } 45 return dummy->next; 46 } 47 };