传送门
思路
题目本质是找到有多少个连续的不同的字符区间,可以这样设计:定义一个信号量flag,每当进入一个区间就将信号量置为true,表示在区间内,只有在进区间的时候会增加答案,在区间内遇到不同的字符就不增加答案。当遇到相同的字符时说明已经出去区间了,将信号量置为false,用以准备进入新的区间时将答案加一。
时间复杂度
$O(n)$
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
string A, B;
cin >> A >> B;
int res = 0;
bool flag = false;
for (int i = 0; i < n; i ++ )
{
if (A[i] != B[i] && !flag) res++, flag = true; //进入区间时增加答案,并且信号量设为true,在区间内不再增加答案
if (A[i] == B[i]) flag = false; //离开区间,信号量置为false,准备下一次增加答案
}
cout << res;
return 0;
}