[leetcode] 1513. Number of Substrings With Only 1s

[leetcode] 1513. Number of Substrings With Only 1s

Description

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: 9Explanation: 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: 2Explanation: Substring "1" is shown 2 times in s.

Example 3:

Input: s = "111111"Output: 21Explanation: Each substring contains only 1's characters.

Example 4:

Input: s = "000"Output: 0

Constraints:

s[i] == ‘0’ or s[i] == ‘1’1 <= s.length <= 10^5

分析

题目的意思是：给定只包含0和1的字符串，求其中的1能够成的不同的组合数目。思路很直接，考虑到连续的1的组合的个数为n*(n+1)//2，n为连续1的字符串的长度。如果能想到这个，就可以遍历求出连续1的子串，然后进行计算就行了。

代码

class Solution: def numSub(self, s: str) -> int: n=len(s) i=0 res=0 while(i

参考文献

​​[LeetCode] [Java/C++/Python] Count​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。