字节--字符串翻转
字節–字符串翻轉
文章目錄
- 字節--字符串翻轉
- 一、題目描述
- 二、分析
- 三、代碼
一、題目描述
有一個僅包含’a’和’b’兩種字符的字符串s，長度為n，每次操作可以把一個字符做一次轉換（把一個’a’設置為’b’，或者把一個’b’置成’a’)；但是操作的次數有上限m，問在有限的操作數范圍內，能夠得到最大連續的相同字符的子串的長度是多少。
- 輸入描述:
- 輸出描述:
二、分析
- 該字符串非 a 即 b 也就是說在區間 l~r之間把所有字符變為 a 所需的步驟數是 該區間內 字符b 的數量。反之亦然.
- 用數組 count[i] 表示 字符串中位置區間 0~i 包含的 a 的個數，則 區間 l~r 的 a 的個數為 count[r] - count[l - 1]
- b 的個數用 a 的個數算出 即 區間 l~r 的 b 的個數為 r + 1 - count[r] - (l + 1 - 1 - count[l - 1]) = r + 1 - l - count[r] + count[l - 1]
- 在區間 l~r 的 a 和 b 的個數已知的情況下
- 若 區間長度step內的 a 的個數 <= m 則 可以通過 m 個步驟 產生 長度為step的連續字符串 b
- 若 區間長度step內的 b 的個數 <= m 則 可以通過 m 個步驟 產生 長度為step的連續字符串 a
- 歸納為 ：若 區間長度step內的字符 b 或字符 a 的個數 <= m 則 可以通過 m 個步驟 產生 長度為step的字符串（不管是全a還是全b）
- 這樣 就可以直接計算出一個字符串長度（區間長度step）是否可行，因此不需要進行遞推，可以直接進行二分搜索，得到最大長度。
- 檢查一個長度step是否可行的時間復雜度為O(n),二分搜索的時間復雜度為O(log n)。
- 因此，該方法總的時間復雜度為 O(n*log n)
三、代碼
#include<iostream> #include<string> #include<cstring> using namespace std;//數組區間 int count[50005]; int n,m;//檢查當前區間長度(step)是否能在 m 個步驟內實現全 a 或 全 b bool func(int step) {for(int i = 0;i + step < n;i++){if(m >= step + 1 - (count[i + step] - count[i - 1]))return true; //檢查 a--》 公式 m>=區間內 b 的個數 if(m >= count[i + step] - count[i - 1])return true; //檢查 b--》 公式： m>=區間內 a 的個數 }return false; }int main() {cin>>n>>m;string str;cin>>str;//輸入并計算出 count 數組 int sum = 0;//統計0～i區間內的a的數量分別保存在每個count[i]位置for(int i = 0;i < str.size();i++){if(str[i] == 'a')count[i] = ++sum;else count[i] = sum;}//二分搜索最大區間值 int l = 0,r = n-1,mid; while(l < r){//取中點，確定區間的大小mid = l + (r - l) / 2;//如果當前區間長度滿足情況，需要睜增大區間長度if(func(mid)){l = mid + 1;}//反之縮小區間長度else{r = mid;}}cout<<l<<endl;return 0; }總結
