每日算法-250422

每日算法 - 250422

---

1561. 你可以获得的最大硬币数目

题目

思路

贪心

解题过程

根据题意，我们想要获得最大的硬币数目。每次选择时，有三堆硬币：最大的一堆会被 Alice 拿走，最小的一堆会被 Bob 拿走，剩下的一堆（也就是第二大的）归我们。

为了最大化我们获得的硬币数，我们应该确保在每次选择中，我们拿到的都是当前可选的三堆里第二大的那一堆。同时，为了让这个第二大的尽可能大，我们应该让 Bob 拿走的那一堆尽可能小。

基于这个贪心策略，我们可以：

1. 将所有硬币堆 piles 从小到大排序。
2. 排序后，最大的硬币堆在数组末尾，最小的在数组开头。
3. 模拟选择过程：
   • Alice 总是拿走当前剩下的最大堆（数组末尾）。
   • 我们总是拿走当前剩下的第二大堆（数组次末尾）。
   • Bob 总是拿走当前剩下的最小堆（数组开头）。
4. 我们可以用三个指针（或索引）来模拟这个过程。或者更简单地，考虑排序后的数组 piles：
   • piles[n-1] 归 Alice。
   • piles[n-2] 归我们。
   • piles[0] 归 Bob。
   • 下一轮：piles[n-3] 归 Alice，piles[n-4] 归我们，piles[1] 归 Bob。
   • 以此类推，我们总是获得索引为 n-2, n-4, n-6, ... 的硬币堆，直到我们选了 n/3 堆为止。

具体的实现可以用一个循环：让我们的指针 j 从 n-2 开始，每次 j -= 2；让 Bob 的指针 k 从 0 开始，每次 k++。循环条件是 j > k，确保我们的索引大于 Bob 的索引，表示还有足够的堆可供分配。

复杂度

• 时间复杂度: O(N log N)

  主要开销在于对 piles 数组进行排序。遍历过程是 O(N)。

• 空间复杂度: O(log N) or O(N)

  取决于排序算法使用的额外空间。如果只考虑我们自己使用的额外空间，可以认为是 O(1)。

Code

class Solution {public int maxCoins(int[] piles) {// 对硬币堆进行排序Arrays.sort(piles);int n = piles.length;int sum = 0;for (int j = n - 2, k = 0; k < n / 3; j -= 2, k++) {sum += piles[j];}return sum;}
}

---

3462. 提取至多 K 个元素的最大总和

题目

思路

贪心

解题过程

题目要求从二维网格 grid 中提取最多 k 个元素，使得它们的总和最大。有一个限制条件：对于第 i 行 grid[i]，最多只能提取 limits[i] 个元素。

贪心策略是显而易见的：我们应该优先选择整个网格中数值最大的那些元素，但同时要遵守每行的提取数量限制。

实现步骤：

1. 遍历 grid 的每一行 i。
2. 对于当前行 grid[i]，找到其中数值最大的 limits[i] 个元素（如果该行元素不足 limits[i] 个，则取所有元素）。可以通过排序当前行，然后选取最大的 limits[i] 个来实现。
3. 将从所有行中选出的这些“候选”元素收集到一个列表或数组（例如 nums）中。
4. 对收集到的所有候选元素 nums 进行排序。
5. 从排序后的 nums 中选取最大的 k 个元素（如果 nums 中的元素总数少于 k，则取所有元素）。
6. 计算这 k 个（或更少）元素之和，即为最大总和。

注意：总和可能很大，需要使用 long 类型存储。

复杂度

• 时间复杂度: O(R * C log C + T log T)

  1. 遍历每一行并排序：R 行，每行排序需要 O(C log C)。总计 O(R * C log C)。
  2. 收集元素：将 T 个元素放入 nums 数组，耗时 O(T)。
  3. 对 nums 数组排序：数组大小为 T，排序需要 O(T log T)。
  4. 求和：取前 k 个元素求和，需要 O(k) 或 O(T) 时间。
     整体复杂度由行排序和最终排序决定。

• 空间复杂度: O(T) or O(R * C)

  主要需要一个数组 nums 来存储所有选出的候选元素，其大小最多为 R * C。

Code

class Solution {private int len = 0;public long maxSum(int[][] grid, int[] limits, int k) {int n = grid.length, m = grid[0].length;int size = n * m;int[] nums = new int[size];for (int i = 0; i < grid.length; i++) {getMaxValue(grid[i], nums, limits[i]);}Arrays.sort(nums);long sum = 0;while (k != 0) {sum += nums[size - 1];size--;k--;}return sum;}private void getMaxValue(int[] arr, int[] nums, int limit) {Arrays.sort(arr);for (int i = arr.length - 1; i >= 0 && limit > 0; i--) {nums[len++] = arr[i];limit--;}}
}

---

2226. 每个小孩最多能分到多少糖果（复习）

题目

这是第二次写这道题了，写的还不错，就是在处理可以获得的糖果数时没有处理数据可能溢出的问题。
详情请见 每日算法-250410

Code

class Solution {public int maximumCandies(int[] candies, long k) {int left = 1, right = 10000001;while (left <= right) {int mid = left + (right - left) / 2;if (check(candies, mid, k)) {// 够分left = mid + 1;} else {right = mid - 1;}}return right;}private boolean check(int[] arr, int num, long k) {long sum = 0;for (int x : arr) {sum += x / num;}return sum >= k;}
}