資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中平衡字串的子字串替換
假設我們有一個字串，其中只包含 4 種字元 'Q'、'W'、'E' 和 'R'。如果字串中的每個字元都出現了 n/4 次（其中 n 是字串的長度），則該字串是平衡的。找到可以替換為任何其他相同長度的字串的子字串的最小長度，以使原始字串變得平衡。因此，如果 s = “QQWE”，則輸出將為 1。這是因為我們可以將 Q 替換為 R，從而得到“RQWE”，它是平衡的。
如果字串已經平衡，則返回 0。
要解決此問題，我們將遵循以下步驟：
- 建立一個對映 m
- 對於 s 中的每個字元，將字元的頻率儲存到對映中，n := s 的大小
- res := n，left := 0
- 對於 right 從 0 到 n – 1
- 將 m[s[right]] 減少 1
- 當 left < n 且 m[Q] <= n/4 且 m[W] <= n/4 且 m[E] <= n/4 且 m[R] <= n/4 時
- res := res 和 right – left + 1 的最小值
- 將 m[s[left]] 增加 1
- 將 left 增加 1
- 返回 res
讓我們看看下面的實現以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int balancedString(string s) {
unordered_map <char, int> m;
for(int i = 0;i<s.size();i++)m[s[i]]++;
int n = s.size();
int res = n;
int left = 0;
for(int right = 0;right<n;right++){
m[s[right]]--;
while(left<n && m['Q']<=n/4 && m['W'] <=n/4 && m['E'] <=n/4 && m['R']<=n/4){
res = min(res, right - left + 1);
m[s[left]]+=1;
left++;
}
}
return res;
}
};
main(){
Solution ob;
cout << (ob.balancedString("QQEQ"));
}輸入
"QQEQ"
輸出
2
更新於: 2020 年 5 月 2 日
377 次檢視
廣告