题目:
给你一个二进制字符串 s(仅由 '0' 和 '1' 组成的字符串)。
返回所有字符都为 1 的子字符串的数目。
由于答案可能很大,请你将它对 10^9 + 7 取模后返回。
示例:
输入:s = "0110111"
输出:9
解释:共有 9 个子字符串仅由 '1' 组成
"1" -> 5 次
"11" -> 3 次
"111" -> 1 次
解题方法:
- 统计全1子串的长度ones;
- 根据统计长度计算所有可能的全1子串的数量,计算公式:
cnt=(ones+1)*ones/2
;
这个公式怎么来的呢,对于一个长度为n的全1字符串,有n个长度为1的全1子串,有n-1个长度为2的全1子串,...,有1个长度为n的全1子串,根据等差数列求和公式可以得到所有的可能数。
代码和结果:
class Solution {
public:
int numSub(string s) {
int i=0;
long cnt=0;
long ones=0;
for(int i=0;i<s.size();i++)
{
if(s[i]=='0')
{
cnt+=ones*(ones+1)/2;
cnt%=1000000007;
ones=0;
}
else
{
ones++;
}
}
cnt+=ones*(ones+1)/2;
cnt%=1000000007;
return cnt;
}
};
运行结果:原题链接:https://leetcode-cn.com/problems/number-of-substrings-with-only-1s/