資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中交換以獲取最長重複字元子字串
假設我們有一個字串 text，我們允許交換字串中的兩個字元。我們需要找到具有重複字元的最長子字串的長度。例如，如果輸入是“ababa”，則結果將是 3，因為如果我們將第一個 b 與最後一個 a 交換，或者將最後一個 b 與第一個 a 交換，則最長的重複字元將是“aaa”，因此長度為 3。
為了解決這個問題，我們將遵循以下步驟：
定義一個對映 cnt，設定 ret := 1，j := 0，n := text 的大小，v := 0，定義一個名為 x 的集合，並建立另一個名為 m 的對映，m 將儲存 text 中每個字元的頻率。
設定 a := * 和 b := *
對於 i 從 0 到 n 的範圍
將 cnt[text[i]] 增加 1
將 text[i] 插入到 x 中
如果 cnt[text[i]] 等於 2，則
如果 a 是 *，則 a := text[i]，否則 b := text[i]
如果 a 不是 * 並且 b 也不是 * 或 x 的大小大於 2
將 cnt[text[j]] 減少 1
如果 cnt[text[j]] 等於 1，則
如果 text[j] 等於 a，則設定 a := *，否則 b := *
如果 cnt[text[j]] 等於 0，則從 x 中刪除 text[j]
greater := 如果 cnt[a] > cnt[b] 則為 a，否則為 b
如果 x 的大小為 1 或 m[greater] – cnt[greater] 不為 0，則
ret := ret 和 i – j + 1 的最大值
否則 ret := ret 和 i – j 的最大值
返回 ret。
讓我們看看以下實現以獲得更好的理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxRepOpt1(string text) {
int ret = 1;
map <char, int> cnt;
int j = 0;
int n = text.size();
int v = 0;
set <char> x;
map <char, int> m;
for(int i = 0; i < text.size(); i++)m[text[i]]++;
char a = '*', b ='*';
for(int i = 0; i < n; i++){
cnt[text[i]]++;
x.insert(text[i]);
if(cnt[text[i]] == 2){
if(a == '*'){
a = text[i];
}else{
b = text[i];
}
}
while(a != '*' && b != '*' || x.size() > 2){
cnt[text[j]]--;
if(cnt[text[j]] == 1) {
if(text[j] == a) {
a ='*';
}else{
b = '*';
}
}
if(cnt[text[j]] == 0) x.erase(text[j]);
j++;
}
char greater = cnt[a] > cnt[b] ? a : b;
if(x.size() == 1 || m[greater] - cnt[greater]){
ret = max(ret, i - j + 1);
}else{
ret = max(ret, i - j);
}
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.maxRepOpt1("ababa"));
}輸入
"ababa"
輸出
3
更新於: 2020年4月30日
489 次檢視
廣告