LeetCode 1234. 替换子串得到平衡字符串
本帖最后由 798236606 于 2020-3-6 12:38 编辑传送门：https://leetcode-cn.com/problems/replace-the-substring-for-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];//记录每个字母的数量
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]];//减掉窗口最右边的字母
if (i >= wd - 1)
{
bool flag = true;
for (int j: now) if (j > 0) flag = false;
if (flag) return wd;//如果窗口内不再有字母数量大于零， 则符合条件
++now]];//减掉窗口最左边的字母
}
}
}
return -1;
}
};
2.双指针滑动窗口
定义r和l代表窗口的左右端，r先向右移探路，直到窗口符合条件，l再向右移试图使窗口更小。
class Solution {
public:
int cnt = {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];
int n = s.size();
for (int &i: cnt) i -= n / 4;
if (check()) return 0;
int l = 0, r = 0, min_size = n;
--cnt]];
while (true)
{
if (check())//若窗口满足条件
{
min_size = min(min_size, r - l + 1);//更新最小窗口长度
++cnt]];//窗口左端右移
}
else
{
if (r == n - 1) break;
--cnt]];//窗口右端右移
}
}
return min_size;
}
};
3.继续优化，发现其实r遍历了整个s的所有下标，不如直接遍历
class Solution {
public:
int cnt = {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];
int n = s.size();
for (int &i: cnt) i -= n / 4;
if (check()) return 0;
intmin_size = n;
for (int l = 0, r = 0; r < n; ++r)
{
--cnt]];//窗口右端右移
while (check())//若窗口满足条件
{
min_size = min(min_size, r - l + 1);//更新最小窗口长度
++cnt]];//窗口左端右移
}
}
return min_size;
}
};
页:
[1]