数据结构
网络
关系型数据库管理系统
操作系统
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 次查看
广告