|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
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;
- }
- };
复制代码 |
|