当前位置: 首页 > news >正文

营销型网站建设费用上海网站排名seo公司

营销型网站建设费用,上海网站排名seo公司,中国风 wordpress主题,怎么做百度网站验证来源:力扣(LeetCode) 描述: 有一个只含有 Q, W, E, R 四种字符,且长度为 n 的字符串。 假如在该字符串中,这四个字符都恰好出现 n/4 次,那么它就是一个「平衡字符串」。 给你一个这样的字符…

来源:力扣(LeetCode)

描述:

有一个只含有 'Q', 'W', 'E', 'R' 四种字符,且长度为 n 的字符串。

假如在该字符串中,这四个字符都恰好出现 n/4 次,那么它就是一个「平衡字符串」。

给你一个这样的字符串 s,请通过「替换一个子串」的方式,使原字符串 s 变成一个「平衡字符串」。

你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。

请返回待替换子串的最小可能长度。

如果原字符串自身就是一个平衡字符串,则返回 0

示例 1:

输入:s = "QWER"
输出:0
解释:s 已经是平衡的了。

示例 2:

输入:s = "QQWE"
输出:1
解释:我们需要把一个 'Q' 替换成 'R',这样得到的 "RQWE" ("QRWE") 是平衡的。

示例 3:

输入:s = "QQQW"
输出:2
解释:我们可以把前面的 "QQ" 替换成 "ER"

示例 4:

输入:s = "QQQQ"
输出:3
解释:我们可以替换后 3'Q',使 s = "QWER"

提示:

  • 1 <= s.length <= 105
  • s.length 是 4 的倍数
  • s 中只含有 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符

方法:滑动窗口

思路与算法

设 partial = n / 4 ,我们选择 s 的一个子串作为「待替换子串」,只有当 s 剩余的部分中 ‘Q’,‘W’,‘E’,‘R’ 的出现次数都小于等于 partial 时,我们才有可能使 s 变为「平衡字符串」。

如果原始的 s 就是 「平衡字符串」,我们直接返回 0,否则我们按照以下思路求解。

从小到大枚举「待替换子串」的左端点 l,为了使得替换的长度最小,我们要找到最近的右端点 r,使得去除 [l, r) 之后的剩余部分满足上述条件。不难发现,随着 l 的递增,r 也是递增的。

具体的,我们使用滑动窗口来维护区间 [l, r) 之外的剩余部分中 ‘Q’,‘W’,‘E’,‘R’ 的出现次数,当其中一种字符的出现次数大于 partial 时,令 s[r] 的出现次数减 1,并使得 r 向右移动一个单位。该操作一直被执行,直到条件被满足或者 r 到达 s 的末尾。

如果找到了使得条件被满足的 r,我们用 r − l 来更新答案,然后令 s[l] 的出现次数加 1,并使得 l 向右移动一个单位进行下一次枚举。否则,后序的 l 也将不会有合法的 r,此时我们可以直接跳出循环。对于所有合法的 [l, r),取 r − l 的最小值做为答案。

代码:

class Solution {
public:int idx(const char& c) {return c - 'A';}int balancedString(string s) {vector<int> cnt(26);for (auto c : s) {cnt[idx(c)]++;}int partial = s.size() / 4;int res = s.size();auto check = [&]() {if (cnt[idx('Q')] > partial || cnt[idx('W')] > partial \|| cnt[idx('E')] > partial || cnt[idx('R')] > partial) {return false;}return true;};if (check()) {return 0;}for (int l = 0, r = 0; l < s.size(); l++) {while (r < s.size() && !check()) {cnt[idx(s[r])]--;r++;}if (!check()) {break;}res = min(res, r - l);cnt[idx(s[l])]++;}return res;}
};

执行用时:20 ms, 在所有 C++ 提交中击败了67.46%的用户
内存消耗:7.6 MB, 在所有 C++ 提交中击败了83.33%的用户
复杂度分析
时间复杂度:O(n),其中 n 为 s 的长度。
空间复杂度:O(∣Σ∣),其中 ∣Σ∣ 表示字符集大小,在本题中 ∣Σ∣ = 26。
author:LeetCode-Solution

http://www.mnyf.cn/news/34384.html

相关文章:

  • 做网站优化要多少钱查看今日头条
  • 医疗电子科技网站建设微博营销的特点
  • 合肥网站优化排名推广新网站推广最直接的方法
  • 平台类网站建设网站建设有多少公司
  • 厦门亚龙网站建设深圳百度seo代理
  • 织梦怎么做网站注册安全工程师
  • 做搜狗手机网站优化排软文营销文案
  • wordpress二级联动seo搜索优化公司
  • python 视频播放网站开发网页推广方案
  • 滨江道网站建设网站怎么快速被百度收录
  • dw属于什么网页制作工具seo包括什么
  • 广州冼村是什么地方seo页面链接优化
  • 中国建设银行门户网站百度竞价客服电话
  • 优秀企业网站欣赏店名设计网络推广代运营公司
  • wordpress修改底部文字廊坊网站建设优化
  • 自力教育太原seo报价
  • 主机屋做淘宝客网站上海牛巨仁seo
  • 上海哪个网站能应聘做家教的英语培训机构
  • 网站布局怎么用dw做兰州快速seo整站优化招商
  • 怎样防止别人利用自己电脑做网站怎么推广自己的微信
  • 在线免费网站建设平台小广告网站
  • 乐清微网站建设河源疫情最新通报
  • 做网做网站建设的网站淘宝搜索排名
  • 检察院门户网站建设方案友情链接买卖平台
  • 惠州专业网站建设公司哪里有百度信息流投放方式有哪些
  • 建设电商网站seo是做什么工作内容
  • 新疆公司网站怎么做网络营销软文范例300
  • 乐思网站建设河北网站推广
  • 自己域名做网站百度地图推广怎么收费标准
  • 网站做外链宁波优化网站厂家