剑指 Offer II 073+076+078

狒狒吃香蕉

狒狒喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。

狒狒可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉，下一个小时才会开始吃另一堆的香蕉。

狒狒喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。

分析：

使用二分查找来解决。如果狒狒在 h 小时内吃掉所有香蕉的最小速度是每小时 k 个香蕉，则当吃香蕉的速度大于每小时 k 个香蕉时一定可以在 h 小时内吃掉所有香蕉，当吃香蕉的速度小于每小时 k 个香蕉时一定不能在 h 小时内吃掉所有香蕉。
由于每小时都要吃香蕉，即每小时至少吃 1 个香蕉，因此二分查找的下界是 1；由于每小时最多吃一堆香蕉，即每小时吃的香蕉数目不会超过最多的一堆中的香蕉数目，因此二分查找的上界是最多的一堆中的香蕉数目。

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int low = 1;
        int high = 0;
        for (int pile : piles) {
            high = Math.max(high, pile);
        }
        int k = high;
        while (low < high) {
            int speed = (high - low) / 2 + low;
            long time = getTime(piles, speed);
            if (time <= h) {
                k = speed;
                high = speed;
            } else {
                low = speed + 1;
            }
        }
        return k;
    }

    public long getTime(int[] piles, int speed) {
        long time = 0;
        for (int pile : piles) {
            int curTime = (pile + speed - 1) / speed;
            time += curTime;
        }
        return time;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

数组中第K大的数字

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

分析：

使用优先队列。定义优先队列为一个大顶堆，然后将数组添加到队列中，最后返回第K个数字。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int num : nums) pq.offer(num);
        while (k>1){
            pq.poll();
            k--;
        }
        return pq.peek();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

合并排序链表

给定一个链表数组，每个链表都已经按升序排列。

请将所有链表合并到一个升序链表中，返回合并后的链表。

分析：

首先想到的是顺序合并，两两合并，每次合并后返回一个链表再与下一个链表进行合并。
还有一种办法是采用优先队列，这种时间效率比较高。即先遍历了每个链表的每个节点的val，将其插入到队列中去，最后在利用循环构建一个合并后的排序链表。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] == null) continue;
            while (lists[i]!=null){
                pq.offer(lists[i].val);
                lists[i] = lists[i].next;
            }
        }
        ListNode head = new ListNode(0);
        ListNode node = head;
        while (!pq.isEmpty()){
            ListNode newnode = new ListNode(pq.poll());
            node.next = newnode;
            node = node.next;
        }
        return head.next;

    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23