【LeetCode】﹝堆ி﹞移除石子的最大得分，吃苹果的最大数目等

傷城~ 2022-10-21 11:42 116阅读 0赞

## 【LeetCode】﹝堆ி﹞移除石子的最大得分，吃苹果的最大数目等 ##

### 文章目录 ###

*   *  【LeetCode】﹝堆ி﹞移除石子的最大得分，吃苹果的最大数目等
     *   *  移除石子的最大得分★★
         *  魔塔游戏★★
         *  吃苹果的最大数目★★
         *  合并K个升序链表★★★
         *  水位上升的泳池中游泳★★★

### 移除石子的最大得分★★ ###

[1753. 移除石子的最大得分][1753.]

【**题目**】你正在玩一个单人游戏，面前放置着大小分别为 `a`、`b` 和 `c` 的 三堆 石子。

每回合你都要从两个 不同的非空堆 中取出一颗石子，并在得分上加 `1` 分。当存在 两个或更多 的空堆时，游戏停止。

给你三个整数 `a` 、`b` 和 `c` ，返回可以得到的 最大分数 。

**提示：**

*  `1 <= a, b, c <= 105`

【**示例**】

输入：a = 2, b = 4, c = 6
    输出：6
    解释：石子起始状态是 (2, 4, 6) ，最优的一组操作是：
    - 从第一和第三堆取，石子状态现在是 (1, 4, 5)
    - 从第一和第三堆取，石子状态现在是 (0, 4, 4)
    - 从第二和第三堆取，石子状态现在是 (0, 3, 3)
    - 从第二和第三堆取，石子状态现在是 (0, 2, 2)
    - 从第二和第三堆取，石子状态现在是 (0, 1, 1)
    - 从第二和第三堆取，石子状态现在是 (0, 0, 0)
    总分：6 分 。

【**解题思路**】

方法一：排序

class Solution {
        
        public int maximumScore(int a, int b, int c) {
        
            int score = 0;
            int[] nums = {
        a, b, c};
            Arrays.sort(nums);
            while (nums[0] > 0 || nums[1] > 0) {
        
                nums[1]--;
                nums[2]--;
                score += 1;
                Arrays.sort(nums);
            }
            return score;
        }
    }

方法二：优先队列

class Solution {
        
        public int maximumScore(int a, int b, int c) {
        
            int score = 0;
            //大根堆
            PriorityQueue<Integer> queue = new PriorityQueue<Integer>( (o1, o2) -> {
        
                return o2 - o1;
            });
            queue.offer(a);
            queue.offer(b);
            queue.offer(c);
            while (true) {
        
                int max = queue.poll();
                int mid = queue.poll();
                if (mid == 0) {
        
                    break;
                }
                score += 1;
                queue.offer(mid - 1);
                queue.offer(max - 1);
            }
            return score;
        }
    }

方法三：数学

class Solution {
        
        public int maximumScore(int a, int b, int c) {
        
            int[] nums = {
        a, b, c};
            Arrays.sort(nums);
            if (nums[0] + nums[1] < nums[2]) {
        
                return nums[0] + nums[1];
            }
            //和为偶数全全空，和为奇数剩一个
            return (a + b + c) / 2;
        }
    }

> 参考热评@班长夏四果题解

--------------------

### 魔塔游戏★★ ###

[LCP 30. 魔塔游戏][LCP 30.]

【**题目**】小扣当前位于魔塔游戏第一层，共有 `N` 个房间，编号为 `0 ~ N-1`。每个房间的补血道具/怪物对于血量影响记于数组 `nums`，其中正数表示道具补血数值，即血量增加对应数值；负数表示怪物造成伤害值，即血量减少对应数值；0 表示房间对血量无影响。

小扣初始血量为 `1`，且无上限。假定小扣原计划按房间编号升序访问所有房间补血/打怪，为保证血量始终为正值，小扣需对房间访问顺序进行调整，每次仅能将一个怪物房间（负数的房间）**调整至访问顺序末尾**。请返回小扣最少需要调整几次，才能顺利访问所有房间。若调整顺序也无法访问完全部房间，请返回 `-1`。

**提示：**

*  `1 <= nums.length <= 10^5`
 *  `-10^5 <= nums[i] <= 10^5`

【**示例**】

输入：nums = [100,100,100,-250,-60,-140,-50,-50,100,150]
    输出：1
    解释：初始血量为 1。至少需要将 nums[3] 调整至访问顺序末尾以满足要求
    ---------------------------------------------------------
    输入：nums = [-200,-300,400,0]
    输出：-1
    解释：调整访问顺序也无法完成全部房间的访问

【**解题思路**】

贪心+优先队列

*  计算数组和，若小于1则不能访问完，返回`-1`
 *  堆中保存打怪值（即负数），当当前生命值为负数时，从堆中出一个最小的（贪心思想，绝对值最大）放在数组末尾，调整值+1

class Solution {
        
        public int magicTower(int[] nums) {
        
            int sum = 1;
            for (int num : nums) sum += num;
            if (sum < 1) return -1;
            long blood = 1;
            int count = 0;
            PriorityQueue<Integer> queue = new PriorityQueue<>();
            for (int num : nums) {
        
                blood += num;
                if (num < 0) queue.offer(num);
                if (blood < 1) {
        
                    while (blood < 1 && !queue.isEmpty()) {
        
                        blood -= queue.poll();
                        count++;
                    }
                }
            }
            return count;
        }
    }

--------------------

### 吃苹果的最大数目★★ ###

[1705. 吃苹果的最大数目][1705.]

【**题目**】有一棵特殊的苹果树，一连 `n` 天，每天都可以长出若干个苹果。在第 `i` 天，树上会长出 `apples[i]` 个苹果，这些苹果将会在 `days[i]` 天后（也就是说，第 `i + days[i]` 天时）腐烂，变得无法食用。也可能有那么几天，树上不会长出新的苹果，此时用 `apples[i] == 0` 且 `days[i] == 0` 表示。

你打算每天 最多 吃一个苹果来保证营养均衡。注意，你可以在这 `n` 天之后继续吃苹果。

给你两个长度为 `n` 的整数数组 `days` 和 `apples` ，返回你可以吃掉的苹果的最大数目。

提示：

*  `apples.length == n`
 *  `days.length == n`
 *  `1 <= n <= 2 * 104`
 *  `0 <= apples[i], days[i] <= 2 * 104`
 *  只有在 `apples[i] = 0` 时，`days[i] = 0` 才成立

【**示例**】

输入：apples = [1,2,3,5,2], days = [3,2,1,4,2]
    输出：7
    解释：你可以吃掉 7 个苹果：
    - 第一天，你吃掉第一天长出来的苹果。
    - 第二天，你吃掉一个第二天长出来的苹果。
    - 第三天，你吃掉一个第二天长出来的苹果。过了这一天，第三天长出来的苹果就已经腐烂了。
    - 第四天到第七天，你吃的都是第四天长出来的苹果。

【**解题思路**】

堆

class Solution {
        
        public int eatenApples(int[] apples, int[] days) {
        
            PriorityQueue<int[]> queue = new PriorityQueue<int[]>( (a, b) -> {
        
                return a[0] - b[0];
            });
            int count = 0, i = 0;
            while (true) {
        
                if (i < apples.length) {
        
                    queue.offer(new int[]{
        days[i] + i, apples[i]});
                } else if (i >= apples.length && queue.isEmpty()) {
        
                    break;
                }
                //移除腐烂的苹果
                while (!queue.isEmpty() && (queue.peek()[0] <= i || queue.peek()[1] == 0)) {
        
                    queue.poll();
                }
                //吃苹果
                if (!queue.isEmpty()) {
        
                    count++;
                    queue.peek()[1]--;
                }
                //天数+1
                i++;
            }
            return count;
        }
    }

--------------------

### 合并K个升序链表★★★ ###

[23. 合并K个升序链表][23. _K]

【**题目**】给你一个链表数组，每个链表都已经按升序排列。

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

**提示**：

*  `k == lists.length`
 *  `0 <= k <= 10^4`
 *  `0 <= lists[i].length <= 500`
 *  `-10^4 <= lists[i][j] <= 10^4`
 *  `lists[i] 按 升序 排列`
 *  `lists[i].length 的总和不超过 10^4`

【**示例**】

输入：lists = [[1,4,5],[1,3,4],[2,6]]
    输出：[1,1,2,3,4,4,5,6]
    解释：链表数组如下：
    [
      1->4->5,
      1->3->4,
      2->6
    ]
    将它们合并到一个有序链表中得到。
    1->1->2->3->4->4->5->6

【**解题思路**】

归并排序的解法见往期博客[【LeetCode】﹝归并思想ி﹞逆序对、翻转对、排序链表、合并K个升序链表][LeetCode_K]

**优先队列**：采用小根堆

将链表的头结点加入队列中，每次选最小的，最后将指针后移一位加入优先队列，若空则不必加入。

class Solution {
        
        public ListNode mergeKLists(ListNode[] lists) {
        
            if (lists == null || lists.length == 0) {
        
                return null;
            }
            
            ListNode dummy = new ListNode(-1);
            ListNode cur = dummy;
            PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>((o1, o2) -> {
        
                return o1.val - o2.val;
            });
    
            for (ListNode list : lists) {
        
                if (list != null) {
        
                    queue.offer(list);
                }
            }
    
            while (!queue.isEmpty()) {
        
                ListNode head = queue.poll();
                cur.next = head;
                if (head.next != null) {
        
                    queue.offer(head.next);
                }
                cur = cur.next;
            }
    
            return dummy.next;
        }
    }

--------------------

### 水位上升的泳池中游泳★★★ ###

[778. 水位上升的泳池中游泳][778.]

【**题目**】在一个 `N x N` 的坐标方格 `grid` 中，每一个方格的值 `grid[i][j]` 表示在位置 `(i,j)` 的平台高度。

现在开始下雨了。当时间为 `t` 时，此时雨水导致水池中任意位置的水位为 `t` 。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。

你从坐标方格的左上平台 `(0，0)` 出发。最少耗时多久你才能到达坐标方格的右下平台 `(N-1, N-1)`？

**提示:**

1.  `2 <= N <= 50`
2.  `grid[i][j]` 是 `[0, ..., N*N - 1]` 的排列

【**示例**】

输入: [[0,2],[1,3]]
    输出: 3
    解释:
    时间为0时，你位于坐标方格的位置为 (0, 0)。
    此时你不能游向任意方向，因为四个相邻方向平台的高度都大于当前时间为 0 时的水位。
    等时间到达 3 时，你才可以游向平台 (1, 1). 因为此时的水位是 3，坐标方格中的平台没有比水位 3 更高的，所以你可以游向坐标方格中的任意位置

【**解题思路**】

方法一：优先队列

class Solution {
        
        public int swimInWater(int[][] grid) {
        
            int n = grid.length;
            int[][] dp = new int[n][n];
            int[] dirs = {
        -1, 0, 1, 0, -1};
            //堆中的三元组[i, j, height]即下标和高度
            PriorityQueue<int[]> heap = new PriorityQueue<int[]>((o1, o2) -> {
        
                return o1[2] - o2[2];
            });
    
            //初始化
            for (int[] p : dp) {
        
                Arrays.fill(p, 10000);
            }
            dp[0][0] = grid[0][0];
            heap.offer(new int[]{
        0, 0, grid[0][0]});
    
            while (!heap.isEmpty()) {
        
                int[] cur = heap.poll();
                int x = cur[0], y = cur[1];
                if (x == n - 1 && y == n - 1) {
        
                    break;
                }
    
                for (int i = 0; i < 4; i++) {
        
                    int posx = x + dirs[i];
                    int posy = y + dirs[i + 1];
                    if (posx >= 0 && posx < n && posy >= 0 && posy < n) {
        
                        int h = Math.max(grid[posx][posy], dp[x][y]);
                        if (h < dp[posx][posy]) {
        
                            dp[posx][posy] = h;
                            heap.offer(new int[]{
        posx, posy, h});
                        }
                    }
                }
            }
    
            return dp[n - 1][n - 1];
        }
    }

方法二：并查集

class Solution {
        
        public int swimInWater(int[][] grid) {
        
            int N = grid.length;
            int len = N * N;
            int[] index = new int[len];
            for (int i = 0; i < N; i++) {
        
                for (int j = 0; j < N; j++) {
        
                    index[grid[i][j]] = i * N + j;
                }
            }
            int[] dirs = {
        -1, 0, 1, 0, -1};
            UnionFind uf = new UnionFind(len);
            
            for (int i = 0; i < len; i++) {
        
                int x = index[i] / N;
                int y = index[i] % N;
    
                for (int j = 0; j < 4; j++) {
        
                    int posX = x + dirs[j];
                    int posY = y + dirs[j + 1];
                    if (check(posX, posY, N) && grid[posX][posY] <= i) {
        
                        uf.union(index[i], posX * N + posY);
                    }
                }
                if (uf.connected(0, len - 1)) {
        
                    return i;
                }
            }
    
            return -1;
        }
    
        private boolean check (int x, int y, int N) {
        
            return x >= 0 && x < N && y >= 0 && y < N;
        }
    
        private class UnionFind {
        
            //使用路径压缩的加权quick_union算法
            private int[] id;    //父链接数组
            private int[] sz;    //根节点所对应分量大小
            private int count;   //连通分量数量
    
            UnionFind(int N) {
        
                count = N;
                id = new int[N];
                sz = new int[N];
                for (int i = 0; i < N; i++) {
        
                    id[i] = i;
                    sz[i] = 1;
                }
            }
    
            public int count() {
        
                return count;
            }
    
            public boolean connected(int p, int q) {
        
                return find(p) == find(q);
            }
    
            public int find(int p) {
        
                if (p == id[p]) return p;
                id[p] = find(id[p]);
                return id[p];
            }
    
            public void union(int p, int q) {
        
                int pRoot = find(p);
                int qRoot = find(q);
                if (pRoot == qRoot) {
        
                    return;
                }
                if (sz[pRoot] >= sz[qRoot]) {
        
                    id[qRoot] = pRoot;
                    sz[pRoot] += sz[qRoot];
                } else {
        
                    id[pRoot] = qRoot;
                    sz[qRoot] += sz[pRoot];
                }
                count--;
            }
    
        }
    }

简单版并查集模板

class UnionFind {
        
            private int[] id;    //父链接数组
    
            UnionFind(int N) {
        
                id = new int[N];
                for (int i = 0; i < N; i++) {
        
                    id[i] = i;
                }
            }
    
            public boolean connected(int p, int q) {
        
                return find(p) == find(q);
            }
    
            public int find(int p) {
        
                if (p == id[p]) return p;
                id[p] = find(id[p]);
                return id[p];
            }
    
            public void union(int p, int q) {
        
                int pRoot = find(p);
                int qRoot = find(q);
                if (pRoot == qRoot) {
        
                    return;
                }
                id[qRoot] = pRoot;
            }
    
        }

> 参考官方题解

[1753.]: https://leetcode-cn.com/problems/maximum-score-from-removing-stones/
[LCP 30.]: https://leetcode-cn.com/problems/p0NxJO/
[1705.]: https://leetcode-cn.com/problems/maximum-number-of-eaten-apples/
[23. _K]: https://leetcode-cn.com/problems/merge-k-sorted-lists/
[LeetCode_K]: https://blog.csdn.net/weixin_44368437/article/details/111652321
[778.]: https://leetcode-cn.com/problems/swim-in-rising-water/