每日算法-250511

每日算法 - 250511

记录一下今天刷的几道LeetCode题目，主要是关于贪心算法和数组处理。

1221. 分割平衡字符串

题目

思路

贪心

解题过程

我们可以遍历一次字符串，维护一个计数器 balance。当遇到字符 'L' 时，balance 增加；当遇到字符 'R' 时，balance 减少。当 balance 的值回到 0 时，说明从上一个平衡点（或字符串开头）到当前位置的 'L' 和 'R' 字符数量相等，即找到了一个平衡字符串，此时结果 ret 加一。

复杂度

• 时间复杂度: $O(N)$, N为字符串长度。
• 空间复杂度: $O(N)$, 因为 ss.toCharArray() 创建了一个新的字符数组。如果只考虑额外空间（不包括输入转换），则为 $O(1)$。

Code

class Solution {public int balancedStringSplit(String ss) {int ret = 0;char[] s = ss.toCharArray();int balance = 0; // Renamed sum to balance for clarityfor (int i = 0; i < s.length; i++) {if (s[i] == 'L') {balance++;} else { // s[i] == 'R'balance--;}if (balance == 0) {ret++;}}return ret;}
}

2405. 子字符串的最优划分

题目

思路

贪心

解题过程

我们遍历字符串，目标是让每个子字符串尽可能长，同时确保其中没有重复字符。
使用一个频率数组 map (或哈希集合) 来追踪当前子字符串中已出现的字符。
遍历字符串中的每个字符：

1. 如果当前字符在 map 中已标记为出现过，则表示当前子字符串到此为止（不包括当前字符）是一个有效的划分。我们让结果 ret 增加，并重置 map (清空频率记录)，然后将当前字符加入新的子字符串（即标记其在 map 中出现）。
2. 如果当前字符未在 map 中出现过，则将其加入当前子字符串（标记其在 map 中出现），并继续扩展。
   初始时，ret 为 1，因为至少会有一个子字符串。

复杂度

• 时间复杂度: $O(N)$, N为字符串长度。遍历字符串一次，Arrays.fill 操作作用于固定大小 (26) 的数组，是 $O(1)$ 操作。
• 空间复杂度: $O(N)$

Code

class Solution {public int partitionString(String ss) {char[] s = ss.toCharArray();int[] map = new int[26];int ret = 1;for (char c : s) {if (++map[c - 'a'] > 1) {ret++;Arrays.fill(map, 0);map[c - 'a']++;}}return ret;}
}

2294. 划分数组使最大差为 K

题目

思路

贪心

解题过程

想要获得最少的子序列（子数组在题目中指子序列，因为元素顺序可以打乱后分组），我们就希望每个子序列尽可能包含更多的元素，同时满足最大差不超过 K 的条件。

1. 对数组 nums进行排序。这样，具有相似数值的元素会聚集在一起。
2. 初始化子序列数量 ret = 1（因为至少有一个子序列）。
3. 将排序后数组的第一个元素设为当前子序列的最小值 minVal。
4. 遍历排序后的数组，从第二个元素开始。对于每个元素 x：
   • 如果 x - minVal > k，则当前元素 x 不能包含在当前子序列中。因此，我们必须开始一个新的子序列。让 ret 增加，并将 minVal 更新为当前元素 x（它将是新子序列的第一个也是最小的元素）。
   • 如果 x - minVal <= k，则当前元素 x 可以包含在当前子序列中，我们继续。minVal 保持不变，因为它是当前子序列的固定最小值。
     为什么可以排序？我们关心的是子序列里的最大值和最小值的差值，这和原始顺序无关。题目要求返回的是最少子序列的个数，而不是子序列本身。所以可以排序。

复杂度

• 时间复杂度: $O(N\log N)$, 主要由排序决定。遍历是 $O(N)$。
• 空间复杂度: $O(\log N)$ or $O(1)$, 取决于排序算法实现所使用的栈空间或是否为原地排序。Java的Arrays.sort()对于基本类型数组通常是快速排序的变体，会使用 $O(\log N)$ 的栈空间。

Code

class Solution {public int partitionArray(int[] nums, int k) {if (nums == null || nums.length == 0) {return 0;}Arrays.sort(nums);int ret = 1;int minVal = nums[0]; for (int x : nums) {if (x - minVal > k) {ret++;minVal = x; }}return ret;}
}

154. 寻找旋转排序数组中的最小值 II

题目

这是第二次写这道题，这次写的还不错，就不再多说了，详细题解见每日算法-250415

Code

class Solution {public int findMin(int[] nums) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == nums[right]) {right--;} else if (nums[mid] > nums[right]) {left = mid + 1;} else {right = mid;}}return nums[left];}
}