每日算法-250427

每日算法 - 2024年4月27日

记录今天学习和解决的LeetCode算法题。

561. 数组拆分 (Array Partition)

题目描述

思路

贪心

解题过程

问题的目标是最大化 n 个 min(a_i, b_i) 对的总和。
假设我们有一对数 (a, b) 且 a <= b，那么 min(a, b) = a。为了让总和最大化，我们应该尽可能地让每一对中的较小数 a 尽可能大。

考虑将数组 nums 排序。排序后，我们得到 nums[0] <= nums[1] <= nums[2] <= ... <= nums[2n-1]。
如果我们把 nums[0] 和 nums[1] 配对，min(nums[0], nums[1]) = nums[0]。
如果我们把 nums[2] 和 nums[3] 配对，min(nums[2], nums[3]) = nums[2]。
以此类推，将 nums[2i] 和 nums[2i+1] 配对，min(nums[2i], nums[2i+1]) = nums[2i]。

可以证明，这种配对方式（即排序后将相邻元素配对）可以得到最大的 min 值之和。直观地想，如果我们不这样配对，例如将 nums[0] 与 nums[2] 配对，那么 nums[1] 就必须与更大的数配对，这可能会导致 min 值变小。

因此，最优策略是：

1. 对数组 nums 进行升序排序。
2. 将排序后数组中下标为偶数（0, 2, 4, …）的元素加起来，即为最终答案。

复杂度

• 时间复杂度: $O(N\log N)$, 主要是排序所需的时间。
• 空间复杂度: $O(\log N)$ or $O(N)$, 取决于排序算法使用的额外空间（如果是原地排序，可以认为是 $O(1)$，但递归栈可能需要 $O(\log N)$）。通常计为 $O(1)$ 或 $O(\log N)$。

Code

class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int sum = 0;
        
        for (int i = 0; i < n; i += 2) {
            sum += nums[i];
        }

        return sum;
    }
}

2144. 打折购买糖果的最小开销 (Minimum Cost of Buying Candies With Discount)

题目描述

思路

贪心

解题过程

我们需要最小化购买糖果的总开销。优惠是“买二送一”，我们可以免费获得一组三个糖果中最便宜的那个。为了最大化优惠力度，我们应该让免费赠送的糖果尽可能昂贵。

贪心策略：

1. 将所有糖果按价格 cost 升序排序。
2. 从最贵的糖果开始考虑。每次选择当前最贵的三个糖果组成一组。
3. 在这一组中，我们支付价格最高和第二高的糖果的费用，价格第三高的糖果（也就是这一组里最便宜的）则免费获得。
4. 重复这个过程，直到所有糖果都被处理完。

具体实现：

1. 对 cost 数组进行排序。
2. 从数组末尾（最贵的糖果）开始，每三个元素为一组进行处理 (i = n-1, n-2, n-3, 然后 i = n-4, n-5, n-6, …)。
3. 在每组 (cost[i], cost[i-1], cost[i-2]) 中，我们将 cost[i] 和 cost[i-1] 加入总开销 sum，而 cost[i-2] 是免费的，所以跳过。
4. 注意处理边界情况：如果最后剩余的糖果不足三个（剩一个或两个），那么这些剩余的糖果都需要购买，因为无法触发“买二送一”的优惠。代码中的循环 i -= 3 和判断 i == 0 的情况处理了这一点。

复杂度

• 时间复杂度: $O(N\log N)$, 主要是排序所需的时间。
• 空间复杂度: $O(\log N)$ or $O(N)$, 取决于排序算法。

Code

class Solution {
    public int minimumCost(int[] cost) {
        int n = cost.length;
        if (n == 1) {
            return cost[0];
        } else if (n == 2) {
            return cost[0] + cost[1];
        }
        
        Arrays.sort(cost);
        
        int sum = 0;
        for (int i = n - 1; i >= 0; i -= 3) {
            sum += cost[i];
            if (i > 0) { 
                sum += cost[i - 1]; 
            }
        }
        return sum;
    }
}

3397. 执行操作后不同元素的最大数量 (Maximum Number of Distinct Elements After Operations)

题目描述

思路

贪心

解题过程

目标是经过操作后，数组中不同元素的数量最大化。每个元素 nums[i] 可以变为 [nums[i] - k, nums[i] + k] 区间内的任意整数。

为了使不同元素的数量尽可能多，我们希望相邻的元素尽可能不同。

贪心策略：

1. 排序: 首先对数组 nums 进行升序排序。这使得我们可以更容易地处理相邻元素。
2. 从右往左处理: 我们可以从数组的右端（最大值）开始向左处理。这样做的好处是，当我们决定 nums[i] 的新值时，nums[i+1] 的新值已经确定了，我们可以利用这个信息来最大化 nums[i] 和 nums[i+1] 不同的可能性。
3. 确定 nums[i] 的新值:
   • 对于 nums[n-1]（最大的元素），我们可以将其变为 nums[n-1] + k，使其尽可能大。
   • 对于 nums[i] (i < n-1)，我们希望它的新值 nums'[i] 满足：
     • nums[i] - k <= nums'[i] <= nums[i] + k (操作约束)
     • nums'[i] < nums'[i+1] (尽可能与右侧元素不同)
     • 为了给左边的元素 nums[i-1] 留出更多空间，我们希望 nums'[i] 尽可能大，但要小于 nums'[i+1]。
   • 因此，nums'[i] 的理想目标是 min(nums[i] + k, nums'[i+1] - 1)。
   • 同时，nums'[i] 不能小于 nums[i] - k。
   • 所以，最终 nums'[i] = Math.max(nums[i] - k, Math.min(nums[i] + k, nums'[i+1] - 1))。
   • 代码中 nums[i] 直接被修改后的值覆盖，x 是原始值 nums[i]，y 是 nums[i+1] 修改后的值减 1。
4. 计数: 在修改 nums[i] 后，检查 nums[i] < nums[i+1] 是否成立。如果成立，说明 i 和 i+1 位置的元素是不同的，计数器 ret 增加。
5. 结果: 循环结束后，ret 记录了有多少对相邻元素是不同的。不同元素的总数是 ret + 1（因为 n 个元素之间有 n-1 个间隙，ret 个不同间隙意味着 ret+1 个不同的段/元素）。

优化:
如果一个数 x 可以变成 [x-k, x+k] 区间内的数，这个区间的大小是 2k + 1。如果数组中所有 n 个元素都能被分配到不同的值，那么最大不同数就是 n。这种情况在 2k + 1 >= n 时是有可能实现的（即使所有原始 nums[i] 都相同，它们也可以分散成 n 个不同的数，只要可用的范围 2k+1 足够大）。因此，如果 2k + 1 >= n，我们可以直接返回 n。

复杂度

• 时间复杂度: $O(N\log N)$, 主要是排序所需的时间。贪心处理过程是 $O(N)$。
• 空间复杂度: $O(\log N)$ or $O(N)$, 取决于排序算法。

Code

class Solution {
    public int maxDistinctElements(int[] nums, int k) {
        int n = nums.length;
        if (k * 2 + 1 >= n) {
            return n;
        }
        Arrays.sort(nums);
        nums[n - 1] += k;
        int i = n - 2;
        int ret = 0;
        while (i >= 0) {
            int x = nums[i];
            int y = nums[i + 1] - 1;
            nums[i] = Math.max(Math.min(x + k, y), x - k);
            if (nums[i] < nums[i + 1]) {
                ret++;
            }
            i--;
        }
        return ret + 1;
    }
}