每日算法-250429

每日 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;}
}

---