LeetCode堆

23. 合并K个升序链表

两两合并：

class Solution {
    private ListNode merge(ListNode a, ListNode b) {
        if (a == null) {
            return b;
        }
        if (b == null) {
            return a;
        }
        if (a.val <= b.val) {
            a.next = merge(a.next, b);
            return a;
        } else {
            b.next = merge(a, b.next);
            return b;
        }
    }
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode res = null;
        for (ListNode node : lists) {
            res = merge(res, node);
        }
        return res;
    }
}

使用小根堆：

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        Queue<ListNode> q = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
        for (ListNode node : lists) {
            if (node != null) {
                q.add(node);
            }
        }
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (!q.isEmpty()) {
            ListNode front = q.poll();
            cur.next = front;
            cur = front;
            if (front.next != null) {
                q.offer(front.next);
            }
        }
        return dummy.next;
    }
}

215. 数组中的第K个最大元素

最经典的面试问题，在实际生活中也应用的非常广泛。
创建容量最大为k的大根堆，最后堆的最后一个元素就是topK。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Queue<Integer> q = new PriorityQueue<>(k, (o1, o2) -> o2 - o1);
        for (int i : nums) {
            q.add(i);
        }
        for (int i = 0; i < k - 1; i++) {
            q.poll();
        }
        return q.poll();
    }
}

264. 丑数 II

使用小根堆，保证每次出队的都是最小的。

class Solution {
    public int nthUglyNumber(int n) {
        int[] ugly = new int[1690];
        Set<Long> isVisit = new HashSet<>();
        Queue<Long> heap = new PriorityQueue<>();
        long curUgly, newUgly;
        int[] primes = {2, 3, 5};
        heap.offer(1L);
        isVisit.add(1L);
        for (int i = 0; i < 1690; i++) {
            curUgly = heap.poll();
            ugly[i] = (int) curUgly;
            for (int j : primes) {
                newUgly = curUgly * j;
                if (!isVisit.contains(newUgly)) {
                    isVisit.add(newUgly);
                    heap.offer(newUgly);
                }
            }
        }
        return ugly[n - 1];
    }
}