每日算法 - 2024-05-13
記錄今天學習的算法題解。
2335. 裝滿杯子需要的最短總時長
題目
思路
貪心
這道題的關鍵在于每次操作盡可能多地減少杯子的數量。我們每次操作可以裝一杯或兩杯(不同類型)。為了最小化總時間,應該優先選擇裝兩杯不同類型的水。
解題過程
問題的最優解受到兩個因素的制約:
- 數量最多的那杯水:假設數量最多的水需要
max_val
杯。由于每次操作最多只能裝一杯這種類型的水,所以我們至少需要max_val
秒才能把這種水裝完。這是一個時間的下限。 - 總水量:假設總水量為
total_sum = amount[0] + amount[1] + amount[2]
。由于每次操作最多裝兩杯水,裝完total_sum
杯水至少需要ceil(total_sum / 2)
秒。這里的ceil
表示向上取整,因為如果總數是奇數,最后一次操作只能裝一杯。在整數除法中,(total_sum + 1) / 2
可以實現向上取整的效果。這也是一個時間的下限。
最短的總時長必須同時滿足這兩個下限條件。因此,最終答案就是這兩個下限中的較大值:max(max_val, (total_sum + 1) / 2)
。
可以證明,總是存在一種貪心策略(例如,每次都優先選擇數量最多的兩種水來裝)可以達到這個下限。
復雜度
- 時間復雜度: O ( 1 ) O(1) O(1)。只需要進行常數次的比較和算術運算。
- 空間復雜度: O ( 1 ) O(1) O(1)。只需要常數級別的額外空間存儲變量。
Code
class Solution {public int fillCups(int[] amount) {// 找到數量最多的杯子數int maxVal = 0;int totalSum = 0;for (int count : amount) {maxVal = Math.max(maxVal, count);totalSum += count;}int avgOps = (totalSum + 1) / 2; return Math.max(maxVal, avgOps);}
}
1753. 移除石子的最大得分
題目
思路
貪心
目標是最大化操作次數(每次操作得1分)。每次操作需要從兩堆不同的非空石子堆中各取一個。為了盡可能多地進行操作,我們應該避免讓某一堆石子過早地被單獨剩下。因此,貪心策略是每次都選擇當前石子數最多的兩堆進行操作。
解題過程
為了方便分析,我們先對三堆石子的數量 a, b, c
進行排序,假設排序后為 min_val <= mid_val <= max_val
。
考慮貪心策略:每次都從最多的兩堆(max_val
和 mid_val
)中取石子。
分析兩種情況:
-
max_val >= mid_val + min_val
:
在這種情況下,最大堆的石子數量大于等于另外兩堆之和。我們可以將mid_val
堆和min_val
堆的石子完全與max_val
堆配對消耗完。 -
max_val < mid_val + min_val
:
在這種情況下,最大堆的石子數不足以單獨消耗掉另外兩堆。這意味著我們可以持續地從最大的兩堆中取石子,直到所有石子幾乎被取完(最多只會剩下一個石子)。
總石子數為S = max_val + mid_val + min_val
。每次操作減少2個石子。我們可以進行的操作次數取決于總石子數S
。- 如果
S
是偶數,最多可以進行S / 2
次操作,最后沒有石子剩下。 - 如果
S
是奇數,最多可以進行(S - 1) / 2
次操作,最后會剩下1個石子。
這兩種情況合并起來就是floor(S / 2)
次操作。在整數除法中,(max_val + mid_val + min_val) / 2
正好計算出floor(S / 2)
。
因此,最大得分為(max_val + mid_val + min_val) / 2
。
- 如果
綜合這兩種情況,即為題解。
復雜度
- 時間復雜度: O ( 1 ) O(1) O(1)。對三個數排序(或找到最大、最小、中間值)以及后續計算都是常數時間。
- 空間復雜度: O ( 1 ) O(1) O(1)。只需要常數級別的額外空間。
Code
class Solution {public int maximumScore(int a, int b, int c) {int max = Math.max(a, Math.max(b, c));int min = Math.min(a, Math.min(b, c));int mid = (a + b + c) - (max + min);if (max >= mid + min) {return mid + min;} else {return (max + mid + min) / 2;}}
}
2592. 最大化數組的偉大值(復習)
題目
這是第二次寫這道題了,典型的田忌賽馬問題,寫的還不錯,就不多說了,詳細題解可以參考之前的筆記:每日算法-250428
Code
class Solution {public int maximizeGreatness(int[] nums) {int ret = 0;Arrays.sort(nums);int left = 0, right = nums.length - 1, i = right;while (left <= right) {if (nums[i] >= nums[right]) {left++;} else {ret++;right--;}i--;}return ret;}
}