算法
(用栈遍历数据)
就是一位一位的遍历原数据。然后判断是否能组成一对,如果栈是空的就将现在检测的字符放到栈里,否则,如果栈顶元素和现在检测的元素相同,或者其中有一个是’?’那就将栈顶元素出栈,如果以上两种都不是,那就栈顶元素出栈,检测的元素入栈,就这样子,时间复杂度应该是O(n);
C++ 代码
#include<iostream>
#include<vector>
using namespace std;
const int N = 1000010;
string a;
vector<char> A;
int main() {
int sum = 0;
cin >> a;
for (int i = 0; i < a.size(); i++) {
if (A.size() > 0) {
if (a[i] == A[0] || a[i] == '?' || A[0] == '?') {
A.pop_back();
sum += 1;
}
else {
A.pop_back();
A.push_back(a[i]);
}
}
else {
A.push_back(a[i]);
}
}
cout << sum;
return 0;
}