题解 | #牛群的合并# Java
牛群的合并
https://www.nowcoder.com/practice/d0cb24e1494e4f45a4b7d1a17db0daef
借助小根堆数据结构,每次选择最小的节点,如果最小的节点有下一个,就加进堆里面
- 掌握一下PriorityQueue借助Comparator初始化的方法
public class Solution { public ListNode mergeKLists (ListNode[] lists) { if (lists.length == 0) return null; PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() { public int compare(ListNode p1, ListNode p2) { return p1.val - p2.val; } }); for (ListNode ln : lists) { if (ln != null ) pq.add(ln); } ListNode dummy = new ListNode(-1), cur = dummy; while (!pq.isEmpty()) { ListNode tmp = pq.poll(); if (tmp.next != null) { pq.add(tmp.next); } cur.next = tmp; cur = cur.next; } return dummy.next; } }
算法题刷刷刷 文章被收录于专栏
数组、链表、栈、队列、堆、树、图等。 查找和排序:二分查找、线性查找、快速排序、归并排序、堆排序等。 动态规划:背包问题、最长公共子序列、最短路径 贪心算法:活动选择、霍夫曼编码 图:深度优先搜索、广度优先搜索、拓扑排序、最短路径算法(如 Dijkstra、Floyd-Warshall) 字符串操作:KMP 算法、正则表达式匹配 回溯算法:八皇后问题、0-1 背包问题 分治算法:归并排序、快速排序