資料結構
組網
關係資料庫管理系統
作業系統
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 瀏覽量
廣告