Q1、使数组元素互不相同所需的最少操作次数
1、题目描述
给你一个整数数组 nums，你需要确保数组中的元素 互不相同 。为此，你可以执行以下操作任意次：
- 从数组的开头移除 3 个元素。如果数组中元素少于 3 个，则移除所有剩余元素。
**注意：**空数组也视作为数组元素互不相同。返回使数组元素互不相同所需的 最少操作次数 。
2、解题思路
为了解决这个问题，我们可以按照以下步骤逐步分析：
- 统计每个元素的频率：
- 如果某个元素在数组中出现了多次，那么它一定会导致数组中出现重复，需要被解决。
- 确定需要移除的次数：
- 从后往前遍历数组，逐步找到需要移除的元素，确保不需要移除多余的部分。
- 模拟移除操作：
- 我们可以利用整数除法来计算需要移除的次数，即每次移除 3 个元素后所需的操作次数。
通过以上分析，我们可以使用以下逻辑：
- 用一个
hashmap统计每个元素的频率。 - 用一个
hashset跟踪我们已经处理过的重复元素。 - 从后往前遍历数组，检查是否需要进行移除，保证在操作完成后，数组中的所有元素互不相同。
3、代码实现
class Solution {
public:int minimumOperations(vector<int>& nums) {// 数组长度int n = nums.size();// 用于记录每个元素的出现次数unordered_map<int, int> freq;// 记录每个元素的频率for (int num : nums) {freq[num]++;}// 用于跟踪已处理的重复元素unordered_set<int> processed;// 从后往前检查数组for (int i = n - 1; i >= 0; --i) {// 如果当前元素的频率大于 1, 说明是重复元素if (freq[nums[i]] > 1) {// 如果已经处理过这个元素, 直接返回最少的移除次数if (processed.count(nums[i])) {return i / 3 + 1; // 计算移除次数} else {// 将当前元素标记为已处理processed.insert(nums[i]);}}}// 如果没有重复元素，直接返回 0return 0;}
};
4、复杂度分析
时间复杂度
- 统计频率：
O(n) - 遍历数组：
O(n) - 总复杂度：
O(n)
空间复杂度
- 使用了
unordered_map和unordered_set，占用额外空间O(n)。
总结
时间复杂度为 O(n)，空间复杂度为 O(n)，实现效率较高。
Q2、执行操作后不同元素的最大数量
1、题目描述
给你一个整数数组 nums 和一个整数 k。
你可以对数组中的每个元素 最多 执行 一次 以下操作：
- 将一个在范围
[-k, k]内的整数加到该元素上。
返回执行这些操作后，nums 中可能拥有的不同元素的 最大 数量。
2、解题思路
排序数组：
- 对数组
nums进行排序，目的是让相邻元素尽可能远离而不重叠。 - 排序后，我们可以按照贪心策略依次处理每个元素。
贪心策略：
- 记录当前已经占用的最后位置
lastUsed，初始化为一个极小值。 - 遍历数组中的每个元素：
- 如果当前元素通过调整后，可以放置在
num - k且不会与之前的元素冲突，则选择num - k位置。 - 如果无法放置在
num - k，则尝试放置在num + k或其他未被占用的位置。
- 如果当前元素通过调整后，可以放置在
统计结果：
- 每次成功放置一个元素到未占用的位置时，计数器
distinctCount增加。 - 最终返回
distinctCount，即数组中可能拥有的最大不同元素数量。
3、代码实现
class Solution {
public:int maxDistinctElements(vector<int>& nums, int k) {// 排序数组，方便后续计算sort(nums.begin(), nums.end());int lastUsed = INT_MIN; // 上一个被占用的位置int distinctCount = 0; // 统计可以选出的最大不同元素个数for (int num : nums) {// 检查当前元素能否放置在 num - k 位置if (num - k > lastUsed) {lastUsed = num - k;++distinctCount;}// 如果 num - k 不行, 检查 num + k 位置else if (num + k > lastUsed) {++lastUsed;++distinctCount;}}return distinctCount;}
};
4、复杂度分析
时间复杂度
- 排序数组：
O(n log n)。 - 遍历数组：
O(n)。 - 总时间复杂度为：
O(n log n)。
空间复杂度
- 使用了常量空间变量
lastUsed和distinctCount。 - 空间复杂度为：
O(1)。
Q3、字符相同的最短子字符串 Ⅰ
Q3 和 Q4 答案一样！
Q4、字符相同的最短子字符串 Ⅱ
1、题目描述
给你一个长度为 n 的二进制字符串 s 和一个整数 numOps。
你可以对 s 执行以下操作，最多 numOps 次：
- 选择任意下标
i（其中0 <= i < n），并 翻转s[i]，即如果s[i] == '1'，则将s[i]改为'0'，反之亦然。
你需要 最小化 s 的最长 相同子字符串 的长度，相同子字符串是指子字符串中的所有字符都相同。
返回执行所有操作后可获得的 最小 长度。
子字符串 是字符串中一个连续、 非空 的字符序列。
2、解题思路
为了最小化最长连续相同子字符串的长度 m，我们可以使用 二分查找 + 贪心检查 的方法：
- 二分查找：
- 将 m 的可能值限定在区间
[1, n]，最小为 1，最大为字符串长度 n。 - 二分查找的目标是找到最小的 m，使得在 numOps 次操作内可以将最长连续相同子字符串的长度减少到 m。
- 将 m 的可能值限定在区间
- 贪心检查：
- 对于给定的目标长度 m，我们需要计算需要多少次操作来将 s 中所有连续相同子字符串的长度减少到不超过 m：
- 如果 m=1，可以将字符串调整为交替模式（如 “0101…” 或 “1010…”），然后计算所需的最小操作次数。
- 如果 m>1，则将字符串划分为多个连续相同字符的子串，移除多余字符以满足每段长度不超过 m。
- 对于给定的目标长度 m，我们需要计算需要多少次操作来将 s 中所有连续相同子字符串的长度减少到不超过 m：
- 操作次数限制：
- 检查所需操作次数是否不超过 numOps，如果可以，则当前 m 可行，否则需要增加 m。
3、代码实现
class Solution {
public:int minLength(string s, int numOps) {int n = s.length();// 检查是否可以通过 numOps 次操作将最长相同子字符串长度调整为 mauto canAdjust = [&](int m) -> bool {int operations = 0;if (m == 1) {// 当 m 为 1 时, 将字符串调整为 "0101..." 或 "1010..." 的两种情况int changesToPattern1 = 0; // 记录变成 "0101..." 的操作次数for (int i = 0; i < n; ++i) {// 如果字符与其在 "0101..." 中的理想奇偶性不同, 则需要一次操作if ((s[i] - '0') != (i % 2)) {++changesToPattern1;}}// changesToPattern2 为变成 "1010..." 的操作次数int changesToPattern2 = n - changesToPattern1;// 取两种模式所需操作的较小值operations = min(changesToPattern1, changesToPattern2);} else {// 当 m > 1时, 将字符串划分为连续相同字符的子串, 移除部分字符使得每段长度 ≤ mint consecutiveCount = 0;for (int i = 0; i < n; ++i) {++consecutiveCount;// 如果到达子串末尾 (即当前字符与下一个字符不同, 或已到达字符串末尾)if (i == n - 1 || s[i] != s[i + 1]) {// 对当前子串, 所需操作为移除 k / (m + 1) 次operations += consecutiveCount / (m + 1);consecutiveCount = 0; // 重置计数器}}}return operations <= numOps;};// 二分查找最小的 m, 使得可以通过 numOps 次操作调整字符串int left = 0, right = n;while (left + 1 < right) {int mid = left + (right - left) / 2;if (canAdjust(mid)) {right = mid; // 如果可行, 缩小右边界} else {left = mid; // 如果不可行, 扩大左边界}}return right; // 最小的 m}
};
4、复杂度分析
时间复杂度：
- 二分查找的迭代次数为 O(logn)。
- 每次检查 m 的操作复杂度为 O(n)，因为需要遍历字符串计算所需操作次数。
- 总时间复杂度为 O(nlogn)。
空间复杂度：
- 使用了常数额外空间，复杂度为 O(1)。
 刷入Ubuntu Touch 16.04——安卓手机刷入Linux)
