資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究用 C++ 編寫一個程式，統計以 '1' 開頭並以 '1' 結尾的子字串的數量。
假設我們給定一個字串 'str' 的長度和一個字串。任務是在給定的二進位制字串中統計以 '1' 開頭並以 '1' 結尾的子字串的數量。二進位制字串僅包含 '1' 和 '0'。例如，
輸入-1 −
N = 5 str = ‘11101’
輸出 −
6
解釋 − 在給定的二進位制字串中，我們有 6 個以 '1' 開頭並以 '1' 結尾的子字串。這些子字串的集合是 {'11'，'111'，'1110'，'11101'，'1101'，'101'}。
輸入-1 −
N = 4 str = ‘0011’
輸出 −
1
解釋 −
在給定的二進位制字串中，我們有 1 個以 '1' 開頭並以 '1' 結尾的子字串。這些子字串的集合是一個單元素集合，即 {'11'}。
解決此問題的方法
對於給定的字串，我們必須統計以 '1' 開頭並以 '1' 結尾的子字串的數量。這個問題類似於著名的握手問題，其中我們必須統計 'n' 個人聚會中的握手次數。
如果我們統計給定字串中 '1' 的數量，那麼我們可以找到以 '1' 開頭並以 '1' 結尾的子字串的集合。
輸入長度為 N 的字串。
一個整數函式 countSubstring(int N, string s) 以字串的長度和一個字串作為輸入，並返回所有以 '1' 開頭並以 '1' 結尾的子字串的數量。
遍歷整個字串並統計字串中 '1' 的數量。
透過 n*(n-1)/2 計算給定字串中子字串（對）的數量。
返回 n*(n-1)/2 的結果。
示例
#include<iostream>
using namespace std;
int countSubstring(int N, string s){
int count=0;
for(int i=0; s[i]!= '\0'; ++i){
if( s[i]== '1' )
count++;
}
return count*(count-1)/2;
}
int main() {
int N=5;
string str= "11101";
cout<< countSubstring(N,str)<<endl;
return 0;
}輸出
如果我們執行以上程式碼，它將輸出如下所示：
6
由於給定字串中存在 '1' 的數量為 '4'，即 count = 4，因此以 '1' 開頭並以 '1' 結尾的子字串總數為 4*(4-1)/2 = 6。
更新於: 2021 年 2 月 5 日
393 次檢視
廣告