LeetCode 1234. 替换子串得到平衡字符串

798236606 · 发表于 2020-3-5 23:37:54

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由 798236606 于 2020-3-6 12:38 编辑

传送门：https://leetcode-cn.com/problems ... or-balanced-string/

分析：
题目求子串的最小长度，首先考虑这样的子串符合什么样的条件？
答：对于每个多出来的字符种类，它在子串中的数量大于等于它多出来的数量。
比如：原字符串 = {Q : 3, W : 0, E: 4, R : 1}, len = 8。
显然，Q多了1个， E多了2个，那么子字符串只要满足Q >= 1, E >= 2即可，而最小的子字符串即为Q = 1, E == 2的情况。
为了方便检查子串是否符合条件，把每中字符的数量减去平衡数量，此时各个数量变成了相对数量，其中大于0 的就是多余字符。

1.固定长度的滑动窗口

滑动窗口的长度从小到大遍历，对于每一长度的滑动窗口遍历一遍原字符串，一旦窗口内的子串条件符合，即为最小答案。

class Solution {
public:
int balancedString(string s) {
int hash['Z'];
vector<int> cnt(4, 0);
int n = s.size();
hash['Q'] = 0;
hash['W'] = 1;
hash['E'] = 2;
hash['R'] = 3;
for (char c: s) ++cnt[hash[c]];//记录每个字母的数量
for (int &i: cnt) i -= n / 4;
int wd = 0;//代表滑动窗口的长度
for (int i: cnt) if (i > 0) wd += i;//记录需要改变的字母数量，即为滑动窗口的起始长度
if (!wd) return 0;
for (; wd < n; ++wd)//滑动窗口的长度从小到大遍历，一旦条件符合，即为最小答案。
{
vector<int> now = cnt;
for (int i = 0; i < n; ++i)//对于每个窗口，遍历一遍字符串
{
--now[hash[s[i]]];//减掉窗口最右边的字母
if (i >= wd - 1)
{
bool flag = true;
for (int j: now) if (j > 0) flag = false;
if (flag) return wd;//如果窗口内不再有字母数量大于零，则符合条件
++now[hash[s[i - wd + 1]]];//减掉窗口最左边的字母
}
}
}
return -1;
}
};

复制代码

2.双指针滑动窗口

定义r和l代表窗口的左右端，r先向右移探路，直到窗口符合条件，l再向右移试图使窗口更小。

class Solution {
public:
int cnt[4] = {0};
bool check(void)//检查是否符合条件
{
for (int i: cnt) if (i > 0) return false;
return true;
}
int balancedString(string s) {
int hash['Z'];
hash['Q'] = 0;
hash['W'] = 1;
hash['E'] = 2;
hash['R'] = 3;
for (char c: s) ++cnt[hash[c]];
int n = s.size();
for (int &i: cnt) i -= n / 4;
if (check()) return 0;
int l = 0, r = 0, min_size = n;
--cnt[hash[s[0]]];
while (true)
{
if (check())//若窗口满足条件
{
min_size = min(min_size, r - l + 1);//更新最小窗口长度
++cnt[hash[s[l++]]];//窗口左端右移
}
else
{
if (r == n - 1) break;
--cnt[hash[s[++r]]];//窗口右端右移
}
}
return min_size;
}
};

复制代码

3.继续优化，发现其实r遍历了整个s的所有下标，不如直接遍历

class Solution {
public:
int cnt[4] = {0};
bool check(void)//检查是否符合条件
{
for (int i: cnt) if (i > 0) return false;
return true;
}
int balancedString(string s) {
int hash['Z'];
hash['Q'] = 0;
hash['W'] = 1;
hash['E'] = 2;
hash['R'] = 3;
for (char c: s) ++cnt[hash[c]];
int n = s.size();
for (int &i: cnt) i -= n / 4;
if (check()) return 0;
int min_size = n;
for (int l = 0, r = 0; r < n; ++r)
{
--cnt[hash[s[r]]];//窗口右端右移
while (check())//若窗口满足条件
{
min_size = min(min_size, r - l + 1);//更新最小窗口长度
++cnt[hash[s[l++]]];//窗口左端右移
}
}
return min_size;
}
};

复制代码

账号		自动登录	找回密码
密码			立即注册

[技术交流] LeetCode 1234. 替换子串得到平衡字符串

马上注册，结交更多好友，享用更多功能^_^