【C++滑动窗口】2516. 每种字符至少取 K 个|1947
本文涉及的基础知识点
LeetCode2516. 每种字符至少取 K 个
给你一个由字符 ‘a’、‘b’、‘c’ 组成的字符串 s 和一个非负整数 k 。每分钟，你可以选择取走 s 最左侧 还是 最右侧 的那个字符。
你必须取走每种字符 至少 k 个，返回需要的 最少 分钟数；如果无法取到，则返回 -1 。
示例 1：
输入：s = “aabaaaacaabc”, k = 2
输出：8
解释：
从 s 的左侧取三个字符，现在共取到两个字符 ‘a’ 、一个字符 ‘b’ 。
从 s 的右侧取五个字符，现在共取到四个字符 ‘a’ 、两个字符 ‘b’ 和两个字符 ‘c’ 。
共需要 3 + 5 = 8 分钟。
可以证明需要的最少分钟数是 8 。
示例 2：
输入：s = “a”, k = 1
输出：-1
解释：无法取到一个字符 ‘b’ 或者 ‘c’，所以返回 -1 。
提示：
1 <= s.length <= 105
s 仅由字母 ‘a’、‘b’、‘c’ 组成
0 <= k <= s.length
滑动窗口
n = s.length
nums[i…j-1]表示滑动窗口，其含义为：最终没有取走的。
令s中a,b,c的数量为cnta,cntb,cntc。则nums[i…j-1]中a,b,c的数量（令分别为a,b,c)小于等于cnta-k,cntb-k,cntc-k。
j一定是以下两种情况之一：
一，j == n。
二，a > cnta或b>cntb或c>cntc。
为了简化操作c1 = {a,b,c},c2={cnta,cntb,cntc}
结果就是 n - max(j-i)
注意：c2[i]<k直接返回-1。
时间复杂度：O(n)
代码
核心代码
class Solution {
public:
int takeCharacters(string s, int k) {
int c1[3] = { 0 }, c2[3] = { 0 };
for (int i = 0; i <3; i++) {
c2[i] = count(s.begin(), s.end(), 'a' + i);
}
if ((c2[0] < k) || (c2[1] < k) || (c2[2] < k)) { return -1; }
int ans = -1;
for (int i = 0, j = 0; i < s.length(); i++) {
while (j < s.length() ) {
const int inx = s[j] - 'a';
if ((c1[inx]+1 > c2[inx] - k)) { break; }
c1[inx]++; j++;
}
ans = max(ans, j - i);
c1[s[i] - 'a']--;
}
return s.length() - ans;
}
};
单元测试
string s;
int k;
TEST_METHOD(TestMethod11)
{
s = "aabaaaacaabc", k = 2;
auto res = Solution().takeCharacters(s, k);
AssertEx(8, res);
}
TEST_METHOD(TestMethod12)
{
s = "a", k = 2;
auto res = Solution().takeCharacters(s, k);
AssertEx(-1, res);
}
TEST_METHOD(TestMethod13)
{
s = "abc", k = 1;
auto res = Solution().takeCharacters(s, k);
AssertEx(3, res);
}
扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
原文地址：https://blog.csdn.net/he_zhidan/article/details/142670350
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！