1 条题解
-
0
#include <bits/stdc++.h> using namespace std; int main() { // [1] n-输入字符串的长度(1≤n≤1000) int n; cin>>n; // [2] s1-目标字符串,s2-需要翻转操作的源字符串(仅包含'H'和'G') string s1,s2; cin>>s1>>s2; // [3] i-左指针(从字符串左端开始,初始为0);j-右指针(从字符串右端开始,初始为n-1) int i=0,j=n-1; // [4] sum-记录最少翻转次数,初始为0 int sum=0; // [5] 双指针循环:从两端向中间遍历,处理字符匹配问题 while(i<=j){ // [6] 情况1:左右两端的字符都与目标字符串不匹配 // 逻辑:翻转i到j的子串可同时修正两端的不匹配,减少翻转次数,符合“最少翻转”的目标 if(s1[i]!=s2[i] && s1[j]!=s2[j]){ // [7] 执行翻转操作:将i到j区间内的'H'和'G'互转 for(int k=i;k<=j;k++){ if(s2[k]=='H') s2[k]='G'; else s2[k]='H'; } // [8] 翻转后,左右指针向中间移动,翻转次数+1 i++,j--; sum++; // [9] 情况2:左指针字符不匹配,右指针字符匹配 // 逻辑:仅左不匹配,缩小右指针范围,尝试让左不匹配的字符与后续区间一起翻转 }else if(s1[i]!=s2[i] && s1[j]==s2[j] ){ j--; // [10] 情况3:左指针字符匹配,右指针字符不匹配 // 逻辑:仅右不匹配,缩小左指针范围,尝试让右不匹配的字符与后续区间一起翻转 }else if(s1[i]==s2[i] && s1[j]!=s2[j] ){ i++; // [11] 情况4:左右两端字符都匹配,直接向中间移动指针 }else{ i++,j--; } } // [12] 输出最少翻转次数 cout<<sum; return 0; }
- 1
信息
- ID
- 1030
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 1
- 标签
- 递交数
- 5
- 已通过
- 1
- 上传者