每日 LeetCode 題解 (2025-04-29)

大家好！這是今天的 LeetCode 刷題記錄，主要涉及幾道可以使用貪心策略解決的問題。

---

2037. 使每位學生都有座位的最少移動次數

題目描述:

思路

貪心

解題過程

要使總移動次數最少，直觀的想法是讓每個學生移動到離他“最近”的可用座位。我們可以證明，最優策略是將位置排序后的第 i 個學生分配到排序后的第 i 個座位。

想象一下，如果我們將學生和座位都按位置排序。假設學生 A 在 students[i]，座位 B 在 seats[j]，學生 C 在 students[k]，座位 D 在 seats[l]。如果 i < k 但 j > l （即學生 A 的位置小于學生 C，但 A 被分配到了位置更大的座位 B，而 C 被分配到了位置更小的座位 D），那么交換他們的座位（A 去 D，C 去 B）會使得總移動距離 |students[i] - seats[l]| + |students[k] - seats[j]| 不會超過原來的移動距離 |students[i] - seats[j]| + |students[k] - seats[l]|。

因此，最優解是將排序后的 seats 數組和 students 數組按索引一一對應。我們只需對 seats 和 students 數組進行排序，然后計算對應位置 seats[i] 和 students[i] 之間距離的絕對值之和。

復雜度

• 時間復雜度: $O(N\log N)$，主要由排序 seats 和 students 數組決定，其中 N 是數組的長度。
• 空間復雜度: $O(\log N)$ 或 $O(N)$，取決于排序算法使用的空間（例如，Java 的 Arrays.sort 對于基本類型數組通常使用快速排序，需要 $O(\log N)$ 的棧空間；對于對象數組使用 Timsort，可能需要 $O(N)$ 的額外空間）。如果我們不考慮排序本身所需的輔助空間（或認為是在原地排序），可以認為是 $O(1)$，但 $O(\log N)$ 更為嚴謹。

Code

class Solution {public int minMovesToSeat(int[] seats, int[] students) {Arrays.sort(seats);Arrays.sort(students);int n = students.length;int ret = 0;for (int i = 0; i < n; i++) {ret += Math.abs(seats[i] - students[i]);}return ret;}
}

---

455. 分發餅干

題目描述:

思路

貪心

解題過程

目標是滿足盡可能多的孩子。貪心策略是：優先滿足胃口最小的孩子，并且用能滿足他的最小的餅干。

為了實現這個策略：

1. 將孩子的胃口數組 g 和餅干尺寸數組 s 都進行升序排序。
2. 使用兩個指針：i 指向當前考慮的孩子，j 指向當前考慮的餅干。
3. 遍歷孩子數組（i 從 0 開始）。對于孩子 g[i]，在餅干數組中找到第一個尺寸大于或等于 g[i] 的餅干 s[j]。
4. 如果找到了這樣的餅干 (s[j] >= g[i])，則這個孩子可以被滿足。我們將滿足的孩子數量 ret 加一，然后考慮下一個孩子 (i++) 和下一塊餅干 (j++)。
5. 如果當前的餅干 s[j] 小于 g[i]，說明這塊餅干無法滿足當前的孩子，我們需要嘗試更大的餅干，因此移動餅干指針 (j++)，但仍然嘗試滿足同一個孩子 g[i]。
6. 當孩子指針 i 或餅干指針 j 超出數組范圍時，停止過程。

復雜度

• 時間復雜度: $O(G\log G+S\log S)$，主要由排序兩個數組決定。排序后的雙指針（或類似邏輯的循環）遍歷過程是線性的，時間復雜度為 $O(G+S)$。總時間復雜度由排序主導。 G 是孩子數量，S 是餅干數量。
• 空間復雜度: $O(\log G+\log S)$ 或 $O(G+S)$，同樣取決于排序算法使用的空間。

Code

class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int ret = 0;for (int i = 0, j = 0; i < g.length; i++) {for (; j < s.length;) {if (g[i] <= s[j++]) {ret++;break;}}}return ret;}
}

---

1433. 檢查一個字符串是否可以打破另一個字符串

題目描述:

思路

貪心

解題過程

字符串 s1 能 “打破” s2 是指存在一種 s1 的排列，使得對于所有位置 i，s1[i] 的字典序大于或等于 s2[i]。

一個關鍵的貪心思想是：如果 s1 能夠打破 s2，那么將 s1 和 s2 按字典序排序后，排序后的 s1 必定也能打破排序后的 s2。這是因為排序將最小的字符對齊比較，次小的對齊比較，依此類推。如果存在任何一個 i 使得 sorted_s1[i] < sorted_s2[i]，那么無論如何排列 s1，都不可能讓 s1 的所有字符都大于等于 s2 對應位置的字符（考慮反證法或鴿巢原理）。

所以，解題步驟如下：

1. 將兩個字符串 ss1 和 ss2 轉換成字符數組 s1 和 s2。
2. 對 s1 和 s2 進行排序。
3. 檢查排序后的 s1 是否能打破 s2 (即 s1[i] >= s2[i] 對所有 i 成立)。
4. 同時檢查排序后的 s2 是否能打破 s1 (即 s2[i] >= s1[i] 對所有 i 成立)。

我們可以用兩個布爾變量 s1BreaksS2 和 s2BreaksS1 來記錄這兩個條件是否滿足。在一次遍歷中，如果發現 s1[i] < s2[i]，則 s1BreaksS2 置為 false；如果發現 s1[i] > s2[i] (等價于 s2[i] < s1[i])，則 s2BreaksS1 置為 false。

最后，只要 s1BreaksS2 或 s2BreaksS1 中至少有一個為 true，就返回 true。

復雜度

• 時間復雜度: $O(N\log N)$，主要由排序字符數組決定，其中 N 是字符串的長度。遍歷檢查的過程是 $O(N)$。
• 空間復雜度: $O(N)$，因為需要創建字符數組來存儲和排序字符串內容。如果可以原地修改字符串（某些語言允許），且排序算法空間復雜度為 $O(\log N)$，則空間可以優化。在 Java 中，toCharArray() 創建了新數組，所以是 $O(N)$。

Code

class Solution {public boolean checkIfCanBreak(String ss1, String ss2) {char[] s1 = ss1.toCharArray();char[] s2 = ss2.toCharArray();Arrays.sort(s1);Arrays.sort(s2);boolean s1BreakS2 = true;boolean s2BreakS1 = true;for (int i = 0; i < s1.length; i++) {if (s1[i] < s2[i]) {s1BreakS2 = false;}if (s1[i] > s2[i]) {s2BreakS1 = false;}}return s1BreakS2 || s2BreakS1;}
}

---