資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中最長重複字元替換
假設我們給定一個只包含大寫字母的字串 s，我們最多可以在該字串上執行 k 次操作。在一次操作中，我們可以選擇字串的任何字元並將其更改為任何其他大寫字母。我們必須找到在執行上述操作後可以獲得的最長包含所有重複字母的子字串的長度。因此，如果輸入類似於：“ABAB”並且 k = 2，則輸出將為 4。這是因為兩個 'A' 和兩個 'B'，反之亦然。
為了解決這個問題，我們將遵循以下步驟：
- maxCount := 0，ans := 0，n := 字串 s 的大小
- 建立一個大小為 26 的陣列 cnt，j := 0
- 對於 i := 0 到 n – 1
- 將 cnt[s[i] – ‘A’] 加 1
- maxCount := maxCount 和 count[s[i] – ‘A’] 的最大值
- 當 j <= i 且 i – j + 1 – maxCount > k 時，執行以下操作：
- 將 cnt[s[j] – ‘A’] 減 1
- 將 j 加 1
- ans := ans 和 i – j + 1 的最大值
- 返回 ans
示例 (C++)
讓我們看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int characterReplacement(string s, int k) {
int maxCount = 0;
int ans = 0;
int n = s.size();
vector <int> cnt(26);
int j = 0;
for(int i = 0; i < n; i++){
cnt[s[i] - 'A']++;
maxCount = max(maxCount, cnt[s[i] - 'A']);
while(j <= i && i - j + 1 - maxCount > k){
--cnt[s[j] - 'A'];
j++;
}
ans = max(ans, i - j + 1);
}
return ans;
}
};
main(){
Solution ob;
cout << ob.characterReplacement("ABAB", 2);
}輸入
"ABAB" 2
輸出
4
更新於：2020年4月28日
1K+ 次瀏覽
廣告