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

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

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

文章目录

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

移除石子的最大得分★★

1753. 移除石子的最大得分

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

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

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

提示：

  • 1 <= a, b, c <= 105

【示例】

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

【解题思路】

方法一：排序

  1. class Solution {
  3.     public int maximumScore(int a, int b, int c) {
  5.         int score = 0;
  6.         int[] nums = {
  7.     a, b, c};
  8.         Arrays.sort(nums);
  9.         while (nums[0] > 0 || nums[1] > 0) {
  11.             nums[1]--;
  12.             nums[2]--;
  13.             score += 1;
  14.             Arrays.sort(nums);
  15.         }
  16.         return score;
  17.     }
  18. }

方法二：优先队列

  1. class Solution {
  3.     public int maximumScore(int a, int b, int c) {
  5.         int score = 0;
  6.         //大根堆
  7.         PriorityQueue<Integer> queue = new PriorityQueue<Integer>( (o1, o2) -> {
  9.             return o2 - o1;
  10.         });
  11.         queue.offer(a);
  12.         queue.offer(b);
  13.         queue.offer(c);
  14.         while (true) {
  16.             int max = queue.poll();
  17.             int mid = queue.poll();
  18.             if (mid == 0) {
  20.                 break;
  21.             }
  22.             score += 1;
  23.             queue.offer(mid - 1);
  24.             queue.offer(max - 1);
  25.         }
  26.         return score;
  27.     }
  28. }

方法三：数学

  1. class Solution {
  3.     public int maximumScore(int a, int b, int c) {
  5.         int[] nums = {
  6.     a, b, c};
  7.         Arrays.sort(nums);
  8.         if (nums[0] + nums[1] < nums[2]) {
  10.             return nums[0] + nums[1];
  11.         }
  12.         //和为偶数全全空，和为奇数剩一个
  13.         return (a + b + c) / 2;
  14.     }
  15. }

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

魔塔游戏★★

LCP 30. 魔塔游戏

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

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

提示：

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

【示例】

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

【解题思路】

贪心+优先队列

  • 计算数组和，若小于1则不能访问完，返回-1

  • 堆中保存打怪值（即负数），当当前生命值为负数时，从堆中出一个最小的（贪心思想，绝对值最大）放在数组末尾，调整值+1

    class Solution {

    1. public int magicTower(int[] nums) {
    3.     int sum = 1;
    4.     for (int num : nums) sum += num;
    5.     if (sum < 1) return -1;
    6.     long blood = 1;
    7.     int count = 0;
    8.     PriorityQueue<Integer> queue = new PriorityQueue<>();
    9.     for (int num : nums) {
    11.         blood += num;
    12.         if (num < 0) queue.offer(num);
    13.         if (blood < 1) {
    15.             while (blood < 1 && !queue.isEmpty()) {
    17.                 blood -= queue.poll();
    18.                 count++;
    19.             }
    20.         }
    21.     }
    22.     return count;
    23. }

    }

吃苹果的最大数目★★

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 才成立

【示例】

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

【解题思路】

堆

  1. class Solution {
  3.     public int eatenApples(int[] apples, int[] days) {
  5.         PriorityQueue<int[]> queue = new PriorityQueue<int[]>( (a, b) -> {
  7.             return a[0] - b[0];
  8.         });
  9.         int count = 0, i = 0;
  10.         while (true) {
  12.             if (i < apples.length) {
  14.                 queue.offer(new int[]{
  15.     days[i] + i, apples[i]});
  16.             } else if (i >= apples.length && queue.isEmpty()) {
  18.                 break;
  19.             }
  20.             //移除腐烂的苹果
  21.             while (!queue.isEmpty() && (queue.peek()[0] <= i || queue.peek()[1] == 0)) {
  23.                 queue.poll();
  24.             }
  25.             //吃苹果
  26.             if (!queue.isEmpty()) {
  28.                 count++;
  29.                 queue.peek()[1]--;
  30.             }
  31.             //天数+1
  32.             i++;
  33.         }
  34.         return count;
  35.     }
  36. }

合并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

【示例】

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

【解题思路】

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

优先队列：采用小根堆

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

  1. class Solution {
  3.     public ListNode mergeKLists(ListNode[] lists) {
  5.         if (lists == null || lists.length == 0) {
  7.             return null;
  8.         }
  10.         ListNode dummy = new ListNode(-1);
  11.         ListNode cur = dummy;
  12.         PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>((o1, o2) -> {
  14.             return o1.val - o2.val;
  15.         });
  17.         for (ListNode list : lists) {
  19.             if (list != null) {
  21.                 queue.offer(list);
  22.             }
  23.         }
  25.         while (!queue.isEmpty()) {
  27.             ListNode head = queue.poll();
  28.             cur.next = head;
  29.             if (head.next != null) {
  31.                 queue.offer(head.next);
  32.             }
  33.             cur = cur.next;
  34.         }
  36.         return dummy.next;
  37.     }
  38. }

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

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] 的排列

【示例】

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

【解题思路】

方法一：优先队列

  1. class Solution {
  3.     public int swimInWater(int[][] grid) {
  5.         int n = grid.length;
  6.         int[][] dp = new int[n][n];
  7.         int[] dirs = {
  8.     -1, 0, 1, 0, -1};
  9.         //堆中的三元组[i, j, height]即下标和高度
  10.         PriorityQueue<int[]> heap = new PriorityQueue<int[]>((o1, o2) -> {
  12.             return o1[2] - o2[2];
  13.         });
  15.         //初始化
  16.         for (int[] p : dp) {
  18.             Arrays.fill(p, 10000);
  19.         }
  20.         dp[0][0] = grid[0][0];
  21.         heap.offer(new int[]{
  22.     0, 0, grid[0][0]});
  24.         while (!heap.isEmpty()) {
  26.             int[] cur = heap.poll();
  27.             int x = cur[0], y = cur[1];
  28.             if (x == n - 1 && y == n - 1) {
  30.                 break;
  31.             }
  33.             for (int i = 0; i < 4; i++) {
  35.                 int posx = x + dirs[i];
  36.                 int posy = y + dirs[i + 1];
  37.                 if (posx >= 0 && posx < n && posy >= 0 && posy < n) {
  39.                     int h = Math.max(grid[posx][posy], dp[x][y]);
  40.                     if (h < dp[posx][posy]) {
  42.                         dp[posx][posy] = h;
  43.                         heap.offer(new int[]{
  44.     posx, posy, h});
  45.                     }
  46.                 }
  47.             }
  48.         }
  50.         return dp[n - 1][n - 1];
  51.     }
  52. }

方法二：并查集

  1. class Solution {
  3.     public int swimInWater(int[][] grid) {
  5.         int N = grid.length;
  6.         int len = N * N;
  7.         int[] index = new int[len];
  8.         for (int i = 0; i < N; i++) {
  10.             for (int j = 0; j < N; j++) {
  12.                 index[grid[i][j]] = i * N + j;
  13.             }
  14.         }
  15.         int[] dirs = {
  16.     -1, 0, 1, 0, -1};
  17.         UnionFind uf = new UnionFind(len);
  19.         for (int i = 0; i < len; i++) {
  21.             int x = index[i] / N;
  22.             int y = index[i] % N;
  24.             for (int j = 0; j < 4; j++) {
  26.                 int posX = x + dirs[j];
  27.                 int posY = y + dirs[j + 1];
  28.                 if (check(posX, posY, N) && grid[posX][posY] <= i) {
  30.                     uf.union(index[i], posX * N + posY);
  31.                 }
  32.             }
  33.             if (uf.connected(0, len - 1)) {
  35.                 return i;
  36.             }
  37.         }
  39.         return -1;
  40.     }
  42.     private boolean check (int x, int y, int N) {
  44.         return x >= 0 && x < N && y >= 0 && y < N;
  45.     }
  47.     private class UnionFind {
  49.         //使用路径压缩的加权quick_union算法
  50.         private int[] id;    //父链接数组
  51.         private int[] sz;    //根节点所对应分量大小
  52.         private int count;   //连通分量数量
  54.         UnionFind(int N) {
  56.             count = N;
  57.             id = new int[N];
  58.             sz = new int[N];
  59.             for (int i = 0; i < N; i++) {
  61.                 id[i] = i;
  62.                 sz[i] = 1;
  63.             }
  64.         }
  66.         public int count() {
  68.             return count;
  69.         }
  71.         public boolean connected(int p, int q) {
  73.             return find(p) == find(q);
  74.         }
  76.         public int find(int p) {
  78.             if (p == id[p]) return p;
  79.             id[p] = find(id[p]);
  80.             return id[p];
  81.         }
  83.         public void union(int p, int q) {
  85.             int pRoot = find(p);
  86.             int qRoot = find(q);
  87.             if (pRoot == qRoot) {
  89.                 return;
  90.             }
  91.             if (sz[pRoot] >= sz[qRoot]) {
  93.                 id[qRoot] = pRoot;
  94.                 sz[pRoot] += sz[qRoot];
  95.             } else {
  97.                 id[pRoot] = qRoot;
  98.                 sz[qRoot] += sz[pRoot];
  99.             }
  100.             count--;
  101.         }
  103.     }
  104. }

简单版并查集模板

  1. class UnionFind {
  3.         private int[] id;    //父链接数组
  5.         UnionFind(int N) {
  7.             id = new int[N];
  8.             for (int i = 0; i < N; i++) {
  10.                 id[i] = i;
  11.             }
  12.         }
  14.         public boolean connected(int p, int q) {
  16.             return find(p) == find(q);
  17.         }
  19.         public int find(int p) {
  21.             if (p == id[p]) return p;
  22.             id[p] = find(id[p]);
  23.             return id[p];
  24.         }
  26.         public void union(int p, int q) {
  28.             int pRoot = find(p);
  29.             int qRoot = find(q);
  30.             if (pRoot == qRoot) {
  32.                 return;
  33.             }
  34.             id[qRoot] = pRoot;
  35.         }
  37.     }

参考官方题解

发表评论

表情：
评论列表 （有 0 条评论，191人围观）

还没有评论，来说两句吧...

相关阅读