每日算法-250417

每日算法 - 20250417

记录今天的算法学习过程，包含三道 LeetCode 题目。

---

1005. K 次取反后最大化的数组和

题目

思路

贪心

解题过程

想要获得最大的数组和，我们的目标是尽可能地增大数组元素的总和。一种有效的贪心策略是：每次选择数组中绝对值最大的负数进行取反。如果数组中没有负数了，或者 k 次操作还未用完，我们就应该选择数组中绝对值最小的数（此时必然是正数或0）进行反复取反，直到 k 次操作用尽。

为了方便找到最小值，我们可以先将数组排序。

1. 对数组 nums 进行升序排序。
2. 遍历排序后的数组，遇到负数 nums[i] 就将其取反 (nums[i] = -nums[i])，同时消耗一次操作 (k--)。继续这个过程直到 k 耗尽或者遍历完所有负数。
3. 如果在完成上述步骤后 k 仍然大于 0：
   • 这意味着数组中所有的数现在都是非负数。
   • 为了最大化数组和，我们应该对数组中绝对值最小的元素执行剩下的取反操作。因为每次取反都会改变其符号，如果 k 是偶数，那么无论我们对哪个元素操作 k 次，最终结果都相当于没有操作（因为偶数次取反等于自身），数组和不变。如果 k 是奇数，那么最终结果相当于对绝对值最小的元素进行了一次取反操作。
   • 因此，如果 k 是奇数，我们需要再次对（可能已经改变了顺序的）数组进行排序，找到新的最小值 nums[0]，并将其取反 (nums[0] = -nums[0])。如果 k 是偶数，则无需任何操作。
4. 最后，计算整个数组的和并返回。

复杂度

• 时间复杂度: O(N log N) - 主要由排序决定。如果 k 很大，排序可能需要执行两次。
• 空间复杂度: O(log N) or O(N) - 取决于排序算法使用的栈空间或辅助空间。通常认为是 O(1) 的额外空间（不计输入输出和递归栈）。

Code

class Solution {public int largestSumAfterKNegations(int[] nums, int k) {Arrays.sort(nums);int i = 0;while (k != 0 && i < nums.length) {if (nums[i] > 0) {break;}nums[i] = -nums[i];i++;k--;}if (k % 2 != 0) {Arrays.sort(nums);nums[0] = -nums[0];}int sum = 0;for (int x : nums) {sum += x;}return sum;}
}

---

1833. 雪糕的最大数量

题目

思路

贪心

解题过程

想要用有限的钱 (coins) 买到尽可能多的雪糕，最直观的策略就是优先购买价格最低的雪糕。这是一种典型的贪心策略：局部最优（每次都买当前能买得起的最便宜的）可以导出全局最优（买到最多的雪糕数量）。

1. 首先，将雪糕的价格数组 costs 从小到大排序。
2. 然后，从价格最低的雪糕开始，依次尝试购买。维护一个计数器 ret 记录购买的数量。
3. 遍历排序后的 costs 数组。对于当前的雪糕价格 costs[i]：
   • 如果 coins >= costs[i]，说明可以购买，那么就扣除相应的花费 (coins -= costs[i])，并将购买数量 ret 加一。
   • 如果 coins < costs[i]，说明钱不够买当前及更贵的雪糕了，停止购买。
4. 返回最终的购买数量 ret。

复杂度

• 时间复杂度: O(N log N) - 主要由排序决定。
• 空间复杂度: O(log N) or O(N) - 取决于排序算法。通常认为是 O(1) 的额外空间。

Code

class Solution {public int maxIceCream(int[] arr, int coins) {Arrays.sort(arr);if (arr[0] > coins) {return 0;}int ret = 0;for (; ret < arr.length; ret++) {coins -= arr[ret];if (coins < 0) {return ret;}}return ret;}
}

---

1385. 两个数组间的距离值（复习）

题目

复习反思

这是第二次做这道题。这次在思考过程中，对于题目要求的理解出现了偏差：没有完全搞清楚“对于 arr1[i]，只要 arr2 中存在任何一个元素 arr2[j] 满足 |arr1[i] - arr2[j]| <= d，那么 arr1[i] 就不满足距离值的要求”。这个关键点没弄明白，导致在考虑二分查找时不知道具体要查找的目标是什么，这是一个需要注意的错误。

实际上，只要理解了这一点——我们需要检查 arr2 中是否存在位于 [arr1[i] - d, arr1[i] + d] 区间内的元素——问题就清晰了。通过对 arr2 排序，我们可以使用二分查找来高效地判断这个区间内是否存在 arr2 的元素。

详细题解请见之前的笔记：每日算法-250407

Code

class Solution {public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {Arrays.sort(arr2);int ret = 0, index = 0;for (int x : arr1) {index = check(arr2, x - d);if (index == arr2.length || arr2[index] > x + d) {ret++;}}return ret;}private int check(int[] arr, int t) {int left = 0, right = arr.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] < t) {left = mid + 1;} else {right = mid - 1;}}return left;}
}

---