数据结构
组网
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚学
法律研究在 C++ 中查找字符串中平衡位置的数量
假设我们有一个字符串。我们必须找出该字符串中平衡位置的数量，左右两部分包含相同的字符。字符的频率无关紧要。因此，如果字符串是“ABAABA”，那么平衡位置的数量是 3。这些位置为 AB|AABA、ABA|ABA、ABAA|BA。
要解决此问题，我们将遵循一些有效方法。在遍历字符串后，我们首先根据所有字符的数量来感觉 right[]。然后从左到右遍历字符串。对于每个字符，我们会在 left[] 中增加其计数，并在 right 中减少计数。对于遍历的任何点，如果 left 中所有具有非零值的字符在 right 中也具有非零值，反之亦然。然后增加结果。
示例
#include <iostream>
#include <algorithm>
#define MAX_CHAR 256
using namespace std;
int countBalancePoints(string str) {
int left[MAX_CHAR] = {0};
int right[MAX_CHAR] = {0};
for (int i=0; i<str.length(); i++)
right[str[i]]++;
int count = 0;
for (int i=0; i < str.length() ; i++) {
left[str[i]]++;
right[str[i]]--;
int j;
for (j=0; j<MAX_CHAR; j++) {
if ( (left[j] == 0 && right[j] != 0) || (left[j] != 0 && right[j] == 0))
break;
}
if (j == MAX_CHAR)
count++;
}
return count;
}
int main() {
char str[] = "ABAABA";
cout << "Number of balance points: " << countBalancePoints(str);
}输出
Number of balance points: 3
更新于： 03-01-2020
103 浏览量
广告