leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0023.cpp (1445B)

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