每日算法打卡 - 2025年4月25日

記錄今天完成的幾道 LeetCode 算法題，分享解題思路和代碼。

---

2178. 拆分成最多數目的正偶數之和

題目

解題思路

貪心算法

解題過程

題目要求我們將一個偶數 finalSum 拆分成盡可能多的 不同 正偶數之和。

為了使拆分出的數字數量最多，我們應該盡可能選擇小的偶數。因此，可以采用貪心策略：從最小的正偶數 2 開始，依次嘗試添加 4, 6, 8, …，并不斷更新剩余的 finalSum。

具體步驟如下：

1. 初始化一個空列表 ret 用于存放結果。
2. 首先判斷 finalSum 是否為偶數，如果不是，無法拆分，直接返回空列表。
3. 使用一個變量 i 從 2 開始，表示當前嘗試添加的偶數。
4. 進入循環，只要 finalSum 大于 0：
   a. 嘗試從 finalSum 中減去當前的偶數 i。
   b. 關鍵一步：檢查減去 i 后的 finalSum。如果 finalSum <= i，這意味著剩余的 finalSum 不足以讓我們在下一步添加 i+2（因為需要不同的偶數，且 i+2 > i >= finalSum），或者剛好等于 i（如果加上 i 會導致重復）。為了用盡 finalSum 并保證得到最多數量的偶數，我們將這個剩余的 finalSum 加到當前的 i 上，形成 i + finalSum_remaining。這個合并后的值將是最后一個加入列表的數。然后將 finalSum 設為 0，表示總和已完全分配。
   c. 將（可能被調整過的）i 添加到結果列表 ret 中。
   d. 將 i 增加 2，準備處理下一個偶數。
5. 當 finalSum 變為 0 時，循環結束，返回列表 ret。

這種方法確保了每次都取最小的可用偶數，從而最大化了偶數的數量，并且通過最后一步的合并操作保證了所有數都是不同的正偶數且總和恰好為 finalSum。

復雜度分析

• 時間復雜度: $O(\sqrt{finalSum})$。 我們依次添加 2, 4, 6, …, k。這些數的和大約是 $k^2/2$。當和達到 finalSum 時停止，所以 $k^2\approx 2\times finalSum$, 即 $k\approx \sqrt{2\times finalSum}$。循環的次數與 $k$ 成正比，因此時間復雜度為 $O(\sqrt{finalSum})$。
• 空間復雜度: $O(\sqrt{finalSum})$。 結果列表 ret 最多存儲約 $\sqrt{finalSum}$ 個數。

Code

class Solution {public List<Long> maximumEvenSplit(long finalSum) {List<Long> ret = new ArrayList<>();if (finalSum % 2 != 0) {return ret;}long i = 2;while (finalSum > 0) {finalSum -= i;if (finalSum <= i) {i += finalSum;finalSum = 0;}ret.add(i);i += 2;}return ret;}
}

---

2567. 修改兩個元素的最小分數

題目

解題思路

貪心

解題過程

題目要求我們通過修改數組中的兩個元素，使得數組的“分數”（最大值與最小值的差）最小。我們有兩次修改機會。

為了最小化最大值與最小值的差，最優的修改策略總是將待修改的元素值改為與數組中某個“目標”元素相等。由于我們可以修改兩個數，我們可以考慮以下幾種情況來消除極端值對分數的影響：

1. 修改兩個最大值: 將數組中最大的兩個元素修改成與最小值 nums[0] 相等（或者修改成任何小于等于 nums[n-3] 的值）。修改后，數組的實際最大值為 nums[n-3]，最小值為 nums[0]。分數是 nums[n-3] - nums[0]。
2. 修改兩個最小值: 將數組中最小的兩個元素修改成與最大值 nums[n-1] 相等（或者修改成任何大于等于 nums[2] 的值）。修改后，數組的實際最小值為 nums[2]，最大值為 nums[n-1]。分數是 nums[n-1] - nums[2]。
3. 修改一個最大值和一個最小值: 將最小值 nums[0] 修改成 nums[1]（或更大），并將最大值 nums[n-1] 修改成 nums[n-2]（或更小）。修改后，數組的實際最小值為 nums[1]，最大值為 nums[n-2]。分數是 nums[n-2] - nums[1]。

這三種情況涵蓋了通過兩次修改來最小化 max - min 的所有有效策略。因為我們總是希望消除最大的數或最小的數對分數的影響。

因此，我們首先對數組進行排序，然后計算上述三種情況對應的分數，取其中的最小值即為答案。

復雜度分析

• 時間復雜度: $O(N\log N)$，主要是數組排序所需的時間。
• 空間復雜度: $O(\log N)$ 或 $O(1)$，取決于排序算法使用的額外空間。

Code

class Solution {public int minimizeSum(int[] nums) {Arrays.sort(nums);int n = nums.length;int maxToMin = nums[n - 3] - nums[0];int minToMax = nums[n - 1] - nums[2];int maxToMinANDminToMax = nums[n - 2] - nums[1];return Math.min(maxToMinANDminToMax, Math.min(maxToMin, minToMax));}
}

---

1509. 三次操作后最大值與最小值的最小差

題目

解題思路

貪心

解題過程

這道題與上一題類似，但我們有三次修改機會。目標仍然是最小化修改后數組的最大值與最小值的差。

同樣，最優策略是修改數組中的極端值（最大或最小的那些）。有三次修改機會，意味著我們可以“消除”數組排序后兩端的最多三個元素對最終 max - min 差值的影響。考慮以下四種消除極端值的情況：

1. 修改最大的三個數: 將 nums[n-1], nums[n-2], nums[n-3] 修改掉。剩下的元素范圍是 [nums[0], nums[n-4]]。最小差值為 nums[n-4] - nums[0]。
2. 修改最小的三個數: 將 nums[0], nums[1], nums[2] 修改掉。剩下的元素范圍是 [nums[3], nums[n-1]]。最小差值為 nums[n-1] - nums[3]。
3. 修改最小的兩個數和最大的一個數: 將 nums[0], nums[1] 和 nums[n-1] 修改掉。剩下的元素范圍是 [nums[2], nums[n-2]]。最小差值為 nums[n-2] - nums[2]。
4. 修改最小的一個數和最大的兩個數: 將 nums[0], nums[n-1] 和 nums[n-2] 修改掉。剩下的元素范圍是 [nums[1], nums[n-3]]。最小差值為 nums[n-3] - nums[1]。

這四種情況覆蓋了所有最優的可能。因為要最小化差值，我們總是改變最大或最小端的元素。改變中間的元素不會比改變兩端的元素更優。

所以，先對數組排序。如果數組長度 n 小于或等于 4，我們總能通過三次修改使得所有元素相等，差值為 0。否則，計算上述四種情況的差值，返回其中的最小值。

復雜度分析

• 時間復雜度: $O(N\log N)$, 瓶頸在于排序。
• 空間復雜度: $O(\log N)$ 或 $O(1)$, 取決于排序算法。

Code

class Solution {public int minDifference(int[] nums) {int n = nums.length;if (n <= 4) {return 0;}Arrays.sort(nums);int maxToMin = nums[n - 4] - nums[0];int minToMax = nums[n - 1] - nums[3];int firstTwo = nums[n - 2] - nums[2];int lastTwo = nums[n - 3] - nums[1];int one = Math.min(maxToMin, minToMax);int two = Math.min(firstTwo, lastTwo);return Math.min(one, two);}
}