每日算法-250419

每日算法 - 2024年4月19日

记录今天完成的LeetCode算法题。

---

1710. 卡车上的最大单元数

题目描述

思路

贪心

解题过程

目标是最大化卡车可以装载的单元总数。根据贪心策略，我们应该优先装载单位体积（每个箱子）包含单元数 (numberOfUnitsPerBoxi) 最多的箱子。这样可以保证在有限的卡车容量下，获得尽可能多的单元数。

1. 排序：将 boxTypes 数组按照每个箱子的单元数 (boxType[1]) 进行降序排序。
2. 遍历装载：遍历排序后的 boxTypes 数组。
   • 对于每种类型的箱子，检查卡车剩余容量 truckSize。
   • 如果 truckSize 大于等于当前类型箱子的数量 (boxType[0])，则将所有该类型的箱子装上卡车。更新总单元数 sum，并减少 truckSize。
   • 如果 truckSize 小于当前类型箱子的数量，则只装载 truckSize 个该类型的箱子。更新总单元数 sum，此时卡车已满，可以直接结束遍历。
3. 返回最终计算得到的总单元数 sum。

复杂度分析

• 时间复杂度: O(N log N)，其中 N 是 boxTypes 的长度。主要开销在于对 boxTypes 数组的排序。
• 空间复杂度: O(log N) 或 O(N)，取决于排序算法使用的额外空间（例如，Java中 Arrays.sort 对对象数组通常使用归并排序或TimSort，可能需要 O(N) 的空间，或优化后接近 O(log N) 的递归栈空间）。

代码实现

class Solution {public int maximumUnits(int[][] boxTypes, int truckSize) {// 按一维数组第二个元素对二维数组进行降序排序Arrays.sort(boxTypes, (arr1, arr2) -> Integer.compare(arr2[1], arr1[1]));int sum = 0;for (int[] boxType : boxTypes) {if (truckSize >= boxType[0]) {sum += (boxType[0] * boxType[1]);} else {sum += (truckSize * boxType[1]);break;}truckSize -= boxType[0];}return sum;}
}

---

1338. 数组大小减半

题目描述

思路

贪心

解题过程

题目要求我们返回一个整数集合的最小大小，使得移除数组中所有属于该集合的整数后，数组的大小至少减半。根据贪心策略，我们应该优先移除出现次数最多的整数。每次移除当前频率最高的整数，可以最快地减少数组的元素数量，从而用最少的整数种类达到减半的目标。

1. 统计频率：使用哈希表（HashMap）统计数组 arr 中每个整数的出现次数。
2. 提取频率：将哈希表中所有不同的频率值提取到一个新的数组 values 中。
3. 排序频率：对 values 数组进行升序排序。
4. 贪心选择：初始化目标移除数量 n = arr.length / 2 和结果集合大小 ret = 0。从 values 数组的末尾（即最大频率）开始向前遍历。
   • 在每一步中，将当前频率 values[i] 从 n 中减去，表示移除了这么多元素。
   • 同时，将 ret 加 1，表示选择了一个新的整数加入到移除集合中。
   • 当 n 小于等于 0 时，说明移除的元素总数已达到或超过数组长度的一半，此时的 ret 就是所需的最小集合大小，停止遍历。
5. 返回 ret。

复杂度分析

• 时间复杂度: O(N log N)。统计频率需要 O(N)。将频率存入数组并排序需要 O(M log M)，其中 M 是数组中不同元素的数量（M <= N）。在最坏情况下 M 接近 N，所以总体复杂度为 O(N log N)。
• 空间复杂度: O(N)。哈希表和存储频率的数组 values 在最坏情况下可能需要存储 N 或接近 N 个条目/元素。

代码实现

class Solution {public int minSetSize(int[] arr) {Map<Integer, Integer> hash = new HashMap<>();for (int x : arr) {hash.put(x, hash.getOrDefault(x, 0) + 1);}int size = hash.size();int[] values = new int[size];int index = 0;for (int x : hash.values()) {values[index++] = x;}Arrays.sort(values);int n = arr.length / 2, ret = 0;for (int i = size - 1; i >= 0; i--) {n -= values[i];ret++;if (n <= 0) {break;}}return ret;}
}

---

3010. 将数组分成最小总代价的子数组 I

题目描述

思路

贪心

解题过程

题目要求将数组 nums 分成三个非空子数组，并最小化这三个子数组的第一个元素之和（即总代价）。

1. 固定第一个元素：根据规则，第一个子数组必须从 nums[0] 开始，所以 nums[0] 必然是总代价的一部分。
2. 寻找最小的另外两个元素：我们需要确定第二和第三个子数组的起始元素，使得它们的和加上 nums[0] 最小。这两个起始元素必须来自 nums 数组中索引 1 到 n-1 的部分。为了使总代价最小，我们只需要在 nums[1] 到 nums[n-1] 这个范围内找到两个值最小的元素即可。
3. 贪心选择：由于子数组可以只有一个元素，我们可以将 nums[1] 到 nums[n-1] 中最小的两个元素分别作为第二和第三个子数组的（唯一）元素。这样它们的代价就是这两个最小值。
4. 实现：因此，最优策略是：
   • 保留 nums[0] 作为代价的一部分。
   • 对数组 nums 从索引 1 到 nums.length - 1 的部分进行升序排序。
   • 总代价就是 nums[0] 加上排序后子数组的前两个元素，即 nums[0] + nums[1] + nums[2]（这里的 nums[1] 和 nums[2] 是排序后的结果）。

复杂度分析

• 时间复杂度: O(N log N)，其中 N 是 nums 的长度。主要开销在于对 nums 数组从索引 1 开始的子数组进行排序。
• 空间复杂度: O(log N) 或 O(N)，取决于排序算法使用的额外空间。

代码实现

class Solution {public int minimumCost(int[] nums) {Arrays.sort(nums, 1, nums.length);return nums[0] + nums[1] + nums[2];}
}