d456 - 社辦合併
題目描述
題目給定一個字串 S 代表社辦配置，以及兩個字元分別代表電研和數創的社辦。要求輸出合併後的社辦配置，以及被鏟掉的部份，也就是電研和數創社辦中間的字串。需要考慮電研和數創在字串中的順序不確定。
解題思路
程式碼首先讀取測試案例數量 t。對於每個測試案例，讀取社辦配置字串 s 和電研、數創的字元 b。然後，程式碼找到電研和數創在 s 中的位置，分別記錄最小索引 mi 和最大索引 ma。接著，程式碼使用 min(abs(mi), abs(ma)) 和 max(abs(mi), abs(ma)) 計算需要保留的字串範圍，並將中間的字串提取出來作為被鏟掉的部分 r。最後，程式碼輸出合併後的社辦配置（將被鏟掉的部分替換為 -1，然後輸出不為 -1 的字元）和被鏟掉的字串。
複雜度分析
- 時間複雜度: O(n)，其中 n 是字串
s的長度。程式碼需要遍歷字串s兩次，一次用於查找電研和數創的位置，一次用於構建合併後的字串。 - 空間複雜度: O(n)，其中 n 是字串
s的長度。程式碼需要額外空間來存儲被鏟掉的字串r，在最壞情況下，r的長度可能與s相同。
程式碼
#include <iostream>
using namespace std;
int t;
string s,b;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> t;
getline(cin,s);
while(t--){
getline(cin,s);
getline(cin,b);
string r;
int sl=s.length(),mi=sl,ma=-sl;
for(int i=0;i<sl;++i){
int c=0;
if(s[i]==b[0]){
mi=min(-i,mi);
}
else if(s[i]==b[1]){
ma=max(i,ma);
}
}
for(int i=min(abs(mi),abs(ma))+1;i<max(abs(mi),abs(ma));++i){
r+=s[i];
s[i]=-1;
}
for(int i=0;i<sl;++i){
if(s[i]!=-1)cout << s[i];
}
cout << "\n" << r << "\n";
}
}