当前位置: 首页 > article >正文

leetcode hot100-34 合并K个升序链表

方法一:分治法(相当于对暴力法的优化)

class Solution {
private:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummyhead = new ListNode(0);
        ListNode* cur = dummyhead;
        while (list1 && list2) {
            if (list1->val < list2->val) {
                cur->next = list1;
                list1 = list1->next;
            } else {
                cur->next = list2;
                list2 = list2->next;
            }
            cur = cur->next;
        }
        cur->next = list1 ? list1 : list2;
        return dummyhead->next;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists, int i, int j) {
        int m = j - i;
        // 计算当前范围 [i, j) 之间的链表数量
        if (m == 0) {
            return nullptr; // 注意输入的 lists 可能是空的
        }
        if (m == 1) {
            return lists[i]; // 无需合并,直接返回
        }
        ListNode* left = mergeKLists(lists, i, i + m / 2);
        ListNode* right = mergeKLists(lists, i + m / 2, j);
        return mergeTwoLists(left, right);
    }

public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return mergeKLists(lists, 0, lists.size());
    }
};

输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]

mergeKLists(0, 3)
├── mergeKLists(0, 1) → 返回 lists[0] (1 -> 4 -> 5)
└── mergeKLists(1, 3)
    ├── mergeKLists(1, 2) → 返回 lists[1] (1 -> 3 -> 4)
    ├── mergeKLists(2, 3) → 返回 lists[2] (2 -> 6)
    └── mergeTwoLists(lists[1], lists[2]) → (1 -> 2 -> 3 -> 4 -> 6)
└── mergeTwoLists(lists[0], merge(lists[1], lists[2])) → (1 -> 1-> 2 -> 3 -> 4 -> 4-> 5 -> 6)

方法二:最小堆 / 优先级队列 priority_queue 

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto cmp = [](const ListNode* a, const ListNode* b) {
            return a->val > b->val;
        };

        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq;

        for (auto head : lists) {
            if (head) {
                pq.push(head);
            }
        }

        ListNode* dummyhead = new ListNode(0);
        ListNode* cur = dummyhead;
        while (!pq.empty()) {
            ListNode* node = pq.top();
            pq.pop();
            if (node->next) {
                pq.push(node->next);
            }
            cur->next = node;
            cur = cur->next;
        }
        ListNode* newhead = dummyhead->next;
        delete dummyhead;
        return newhead;
    }
};

这里使用 Lambda 表达式,Lambda 表达式把函数看作对象。Lambda 表达式可以像对象一样使用,比如可以将它们赋给变量和作为参数传递,还可以像函数一样对其求值。Lambda 表达式本质上与函数声明非常类似。Lambda 表达式具体形式如下:

[capture](parameters)->return-type{

body

};

[捕获列表](参数列表) -> 返回类型 {
    // 函数体
};

其中:

  • [捕获列表]:捕获外部变量的方式([] 表示不捕获任何变量,[=] 表示按值捕获,[&] 表示按引用捕获)。

  • (参数列表):定义传递给 Lambda 的参数(类似普通函数的参数)。

  • -> 返回类型(可选):指定返回值类型(可以省略,由编译器推导)。

  • { 函数体 }:函数的具体实现。

这道题目中:

(1)定义 Lambda

[](ListNode* a, ListNode* b) { return a->val > b->val; }

(2)decltype(cmp) 用于自动推导 cmp 的类型,因为lambda没有名字。这样 priority_queue 就能正确使用 cmp进行排序。

(3)初始化 priority_queue,

priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);

  • ListNode* 是存储的数据类型。

  • vector<ListNode*> 是底层实现(默认 vector)。

  • decltype(cmp) 指定比较器的类型,pq(cmp) 传入 cmp 作为构造函数参数。

当然也可以使用operator() 仿函数,对 () 进行重载

struct compare {
        bool operator()(ListNode* a, ListNode* b) { 
            return a->val > b->val; 
        }
    };


priority_queue<ListNode*, vector<ListNode*>, compare> pq;
class Solution {
public:
    struct cmp {
        bool operator()(ListNode* a, ListNode* b) { 
            return a->val > b->val; 
        }
    };
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
        for (auto head : lists) {
            if (head) {
                pq.push(head);
            }
        }
        ListNode* dummyhead = new ListNode(0);
        ListNode* cur = dummyhead;
        while (!pq.empty()) {
            ListNode* node = pq.top();
            pq.pop();
            if (node->next) {
                pq.push(node->next);
            }
            cur->next = node;
            cur = cur->next;
        }
        ListNode* newhead = dummyhead->next;
        delete dummyhead;
        return newhead;
    }
};

operator() vs 普通函数

你可能会问:为什么不用普通函数,而要用 operator()

(1)普通函数:

bool myCompare(ListNode* a, ListNode* b) {
    return a->val > b->val;
}

priority_queue<ListNode*, vector<ListNode*>, decltype(&myCompare)> pq(myCompare);

 也可以,但 myCompare 需要用 &myCompare 传递,略显繁琐。使用 &myCompare,表示传递的是函数指针

(2)使用 operator()(仿函数):

struct compare {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val;
    }
};
priority_queue<ListNode*, vector<ListNode*>, compare> pq;

 更简洁priority_queue 直接使用 compare 作为类型

(3)使用 lambda(C++11):

auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);

 最简洁,省去 struct compare 定义,适用于单次使用。

 

 

 


http://www.kler.cn/a/558304.html

相关文章:

  • Swiper插件的运用和学习
  • 自动驾驶与智慧交通:未来城市的交通革命即将来临
  • 基于YOLO11深度学习的运动鞋品牌检测与识别系统【python源码+Pyqt5界面+数据集+训练代码】
  • EquinoxProject:一个适合学习DDD、CQRS、Event Sourcing等技术.Net Web框架搭建开源项目
  • 【落羽的落羽 数据结构篇】树、二叉树
  • 请解释 Vue 中的生命周期钩子,不同阶段触发的钩子函数及其用途是什么?
  • .NET周刊【2月第2期 2025-02-09】
  • Docker Mysql 数据迁移
  • 1.24作业
  • 技术总结汇总
  • 在工业生产中,物料搬运环节至关重要,搬运机器人开启新篇章
  • 【Quest开发】全身跟踪(一)
  • 【深度学习】Python多线程/多进程在神经网络模型的应用实战
  • 中文Build a Large Language Model (From Scratch) 免费获取全文
  • LLM增强的RLHF框架,用多模态人类反馈提升自动驾驶安全性!
  • mysql----查询,
  • 数据链路层分析
  • [Android]让APP进入后台后不被杀掉(保活)
  • 小游戏-记忆卡牌
  • Golang中如何正确close channel