Given a binary string s
(a string consisting only of '0' and '1's).
Return the number of substrings with all characters 1's.
Since the answer may be too large, return it modulo 10^9 + 7.
Example 1:
Input: s = "0110111" Output: 9 Explanation: There are 9 substring in total with only 1's characters. "1" -> 5 times. "11" -> 3 times. "111" -> 1 time.
Example 2:
Input: s = "101" Output: 2 Explanation: Substring "1" is shown 2 times in s.
Example 3:
Input: s = "111111" Output: 21 Explanation: Each substring contains only 1's characters.
Example 4:
Input: s = "000" Output: 0
Constraints:
s[i] == '0'
ors[i] == '1'
1 <= s.length <= 10^5
A:
class Solution { public: int numSub(string s) { int n = s.length(); int start = 0; vector<long> count(n+1,0); for(int i=1;i<=n;i++){ count[i] = i + count[i-1]; } int res = 0; while(start<n){ while(start<n && s[start]=='0'){ start++; } int end = start; while(end<n && s[end]=='1'){ end++; } int len = end - start; res = (res + count[len]) % 1000000007; start = end; } return res; } };
核心是 f( i 个连续1 的子集数) = f(i-1) + i;
No comments:
Post a Comment