当前位置：首页 > news >正文

每日算法-250429

news 来源：原创 2025/7/13 1:44:37

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

大家好！这是今天的 LeetCode 刷题记录，主要涉及几道可以使用贪心策略解决的问题。

2037. 使每位学生都有座位的最少移动次数

题目描述:

思路

贪心

解题过程

要使总移动次数最少，直观的想法是让每个学生移动到离他“最近”的可用座位。我们可以证明，最优策略是将位置排序后的第 i 个学生分配到排序后的第 i 个座位。

因此，最优解是将排序后的 seats 数组和 students 数组按索引一一对应。我们只需对 seats 和 students 数组进行排序，然后计算对应位置 seats[i] 和 students[i] 之间距离的绝对值之和。

复杂度

时间复杂度: $\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. 分发饼干

题目描述:

思路

贪心

解题过程

目标是满足尽可能多的孩子。贪心策略是：优先满足胃口最小的孩子，并且用能满足他的最小的饼干。

为了实现这个策略：

将孩子的胃口数组 g 和饼干尺寸数组 s 都进行升序排序。
使用两个指针：i 指向当前考虑的孩子，j 指向当前考虑的饼干。
遍历孩子数组（i 从 0 开始）。对于孩子 g[i]，在饼干数组中找到第一个尺寸大于或等于 g[i] 的饼干 s[j]。
如果找到了这样的饼干 (s[j] >= g[i])，则这个孩子可以被满足。我们将满足的孩子数量 ret 加一，然后考虑下一个孩子 (i++) 和下一块饼干 (j++)。
如果当前的饼干 s[j] 小于 g[i]，说明这块饼干无法满足当前的孩子，我们需要尝试更大的饼干，因此移动饼干指针 (j++)，但仍然尝试满足同一个孩子 g[i]。
当孩子指针 i 或饼干指针 j 超出数组范围时，停止过程。

复杂度

时间复杂度: $\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 对应位置的字符（考虑反证法或鸽巢原理）。

所以，解题步骤如下：

将两个字符串 ss1 和 ss2 转换成字符数组 s1 和 s2。
对 s1 和 s2 进行排序。
检查排序后的 s1 是否能打破 s2 (即 s1[i] >= s2[i] 对所有 i 成立)。
同时检查排序后的 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。

复杂度

时间复杂度: $\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;}
}

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

思路

解题过程

复杂度

Code

思路

解题过程

复杂度

Code

思路

解题过程

复杂度

Code

相关文章：