鱼C论坛

 找回密码
 立即注册
查看: 1179|回复: 0

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

[复制链接]
发表于 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.固定长度的滑动窗口

滑动窗口的长度从小到大遍历,对于每一长度的滑动窗口遍历一遍原字符串,一旦窗口内的子串条件符合,即为最小答案。
  1. class Solution {
  2. public:
  3.     int balancedString(string s) {
  4.         int hash['Z'];
  5.         vector<int> cnt(4, 0);
  6.         int n = s.size();

  7.         hash['Q'] = 0;
  8.         hash['W'] = 1;
  9.         hash['E'] = 2;
  10.         hash['R'] = 3;

  11.         for (char c: s) ++cnt[hash[c]];//记录每个字母的数量

  12.         for (int &i: cnt) i -= n / 4;

  13.         int wd = 0;//代表滑动窗口的长度
  14.         for (int i: cnt) if (i > 0) wd += i;//记录需要改变的字母数量,即为滑动窗口的起始长度

  15.         if (!wd) return 0;

  16.         for (; wd < n; ++wd)//滑动窗口的长度从小到大遍历,一旦条件符合,即为最小答案。
  17.         {
  18.             vector<int> now = cnt;
  19.             
  20.             for (int i = 0; i < n; ++i)//对于每个窗口,遍历一遍字符串
  21.             {
  22.                 --now[hash[s[i]]];//减掉窗口最右边的字母

  23.                 if (i >= wd - 1)
  24.                 {
  25.                     bool flag = true;

  26.                     for (int j: now) if (j > 0) flag = false;

  27.                     if (flag) return wd;//如果窗口内不再有字母数量大于零, 则符合条件

  28.                     ++now[hash[s[i - wd + 1]]];//减掉窗口最左边的字母
  29.                 }
  30.             }
  31.         }

  32.         return -1;
  33.     }
  34. };
复制代码


2.双指针滑动窗口

定义r和l代表窗口的左右端,r先向右移探路,直到窗口符合条件,l再向右移试图使窗口更小。
  1. class Solution {
  2. public:
  3.     int cnt[4] = {0};

  4.     bool check(void)//检查是否符合条件
  5.     {
  6.         for (int i: cnt) if (i > 0) return false;

  7.         return true;
  8.     }

  9.     int balancedString(string s) {
  10.         int hash['Z'];
  11.         hash['Q'] = 0;
  12.         hash['W'] = 1;
  13.         hash['E'] = 2;
  14.         hash['R'] = 3;

  15.         for (char c: s) ++cnt[hash[c]];

  16.         int n = s.size();
  17.         for (int &i: cnt) i -= n / 4;

  18.         if (check()) return 0;
  19.         
  20.         int l = 0, r = 0, min_size = n;
  21.         --cnt[hash[s[0]]];

  22.         while (true)
  23.         {
  24.             if (check())//若窗口满足条件
  25.             {
  26.                 min_size = min(min_size, r - l + 1);//更新最小窗口长度
  27.                 ++cnt[hash[s[l++]]];//窗口左端右移
  28.             }
  29.             else
  30.             {
  31.                 if (r == n - 1) break;
  32.                 --cnt[hash[s[++r]]];//窗口右端右移
  33.             }
  34.         }

  35.         return min_size;
  36.     }
  37. };
复制代码


3.继续优化,发现其实r遍历了整个s的所有下标,不如直接遍历
  1. class Solution {
  2. public:
  3.     int cnt[4] = {0};

  4.     bool check(void)//检查是否符合条件
  5.     {
  6.         for (int i: cnt) if (i > 0) return false;

  7.         return true;
  8.     }

  9.     int balancedString(string s) {
  10.         int hash['Z'];
  11.         hash['Q'] = 0;
  12.         hash['W'] = 1;
  13.         hash['E'] = 2;
  14.         hash['R'] = 3;

  15.         for (char c: s) ++cnt[hash[c]];

  16.         int n = s.size();
  17.         for (int &i: cnt) i -= n / 4;

  18.         if (check()) return 0;
  19.         
  20.         int  min_size = n;
  21.         for (int l = 0, r = 0; r < n; ++r)
  22.         {
  23.             --cnt[hash[s[r]]];//窗口右端右移

  24.             while (check())//若窗口满足条件
  25.             {
  26.                 min_size = min(min_size, r - l + 1);//更新最小窗口长度
  27.                 ++cnt[hash[s[l++]]];//窗口左端右移
  28.             }
  29.         }

  30.         return min_size;
  31.     }
  32. };
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-3 09:01

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表