資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++中統計二進位制子串
假設我們有一個字串s，我們需要找到包含相同數量的0和1的連續子串的數量，並且這些子串中的所有0和所有1都連續分組。如果子串出現多次，則計算其出現的次數。
因此，如果輸入類似於“11001100”，則輸出將為6，因為子串為“1100”、“10”、“0011”、“01”、“1100”、“10”。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個大小為2的陣列cnt，並將其填充為0
- res := 0
- for 初始化 i := 0，當 i < s的長度，更新 (i增加1)，執行：
- num := s[i] - '0' 的ASCII碼
- 如果 i 等於 0 或 s[i] 不等於 s[i - 1]，則：
- cnt[num] := 0
- (cnt[num] 增加1)
- 如果 cnt[num] <= cnt[1 - num]，則：
- (res 增加1)
- 返回 res
讓我們來看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int countBinarySubstrings(string s) {
int cnt[2] = { 0 };
int res = 0;
for (int i = 0; i < s.length(); ++i) {
int num = s[i] - '0';
if (i == 0 || s[i] != s[i - 1])
cnt[num] = 0;
++cnt[num];
if (cnt[num] <= cnt[1 - num])
++res;
}
return res;
}
};
main(){
Solution ob;
cout << (ob.countBinarySubstrings("11001100"));
}輸入
"11001100"
輸出
6
更新於：2020年7月4日
706 次瀏覽
廣告