1513. 仅含 1 的子串数 [medium]

https://leetcode-cn.com/problems/number-of-substrings-with-only-1s/

给你一个二进制字符串 s（仅由 '0' 和 '1' 组成的字符串）。

返回所有字符都为 1 的子字符串的数目。

由于答案可能很大，请你将它对 10^9 + 7 取模后返回。

示例 1：

输入：s = "0110111"
输出：9
解释：共有 9 个子字符串仅由 '1' 组成
"1" -> 5 次
"11" -> 3 次
"111" -> 1 次

示例 2：

输入：s = "101"
输出：2
解释：子字符串 "1" 在 s 中共出现 2 次

示例 3：

输入：s = "111111"
输出：21
解释：每个子字符串都仅由 '1' 组成

示例 4：

输入：s = "000"
输出：0

提示：

s[i] == '0' 或 s[i] == '1'
1 <= s.length <= 10^5

通过次数5,083 | 提交次数14,428

Second Try

2020-07-15

判断连续1的数量，本来还打算用开始进入1的序列，出1的序列之类进行统计，后来看题解发现根本不用考虑那么多，一波统计直接带走。偶尔还是要看下别人怎么写的，去除很多非高效的写法。

另外这题的连续1的数量，看来又是一个经典的套路题。连续n个1能够凑成的1的子序列的数量就是(n + 1) * n / 2.

原因考虑考虑从n-1个1的序列，拓展为n个1的序列的时候，能够增加多少个序列？发现其实只增加了n个子序列，因为新增加的子序列都是跟最后一个1相关的才行。然后往前递推，发现这其实就是一个等差数列，于是甚至都不用动态规划算法，直接搞定。

在周赛的时候，我倒是直接用上了动态规划算法，写得比较繁琐，但也算是ac了这道题。

class Solution(object):
    def numSub(self, s):
        """
        :type s: str
        :rtype: int
        """
        
        clen = 0 
        rv = 0 

        for c in s:
            if c == "0" and clen:
                rv += (1 + clen) * clen / 2
                clen = 0 
            elif c == "1":
                clen += 1
        # 最后剩下的一小戳，且最后一个字母不是0 
        rv += (1 + clen) * clen / 2
        return rv % (10 ** 9 + 7)

执行用时：108 ms, 在所有 Python 提交中击败了38.17%的用户
内存消耗：13.2 MB, 在所有 Python 提交中击败了100.00%的用户

pretry 普通版本

class Solution(object):
    def numSub(self, s):
        """
        :type s: str
        :rtype: int
        """
        
        rv = 0 
        clen = 0 
        for i, c in enumerate(s):
            if c == "0" and clen:
                rv += (1 + clen) * clen / 2
                clen = 0 
            elif c == "1":
                clen += 1
        # 最后剩下的一小戳，且最后一个字母不是0 
        rv += (1 + clen) * clen / 2
        return rv % (10 ** 9 + 7)

执行用时：180 ms, 在所有 Python 提交中击败了9.16%的用户
内存消耗：13.2 MB, 在所有 Python 提交中击败了100.00%的用户

First Try

2020-07-12

周赛时候的解法，比较琐碎，用上了动态规划的缓存数组，好歹是观察出了规律写出来。

一开始看题目，以为是在n个1中随意选择子序列，是C(n, a)的选择序列。测试后发现原来是连续1的子序列，于是改成了动态规划。当然按照second try中的写法，这其实就是等差数列。

算是又了解了一种套路题，再遇到的话可以节约不少时间。

class Solution:
    def numSub(self, s: str) -> int:
        # find continue ints 
        # calculate possible combination in continue ones
        counter = collections.defaultdict(int)
        start = None 
        conlen = 0
        for i, c in enumerate(s):
            if start is None:
                if c == "1":
                    start = i 
                continue 
            else:
                if c == "1":                    
                    continue 
                conlen = i -  start
                counter[conlen] += 1
                start = None
        # 还需要考虑最后的一小撮有效分子，debug才发现。。
        if start is not None:
            counter[len(s) - start] += 1
        # print(counter)
        
        if not len(counter.keys()):
            return 0 
        maxlen = max(counter.keys())
        cache = [None] * (maxlen + 1) 
        cache[0] = 0
        cache[1] = 1
        def possible(n):
            if cache[n] is not None:
                return cache[n]
            cache[n] = possible(n-1) + n 
            return cache[n]

        rem = 10 ** 9 + 7
        rv = 0
        for k, v in counter.items():
            rv += v * possible(k)
        return rv % rem
            
        
#         factorial = dict()  # 0! is 1 
#         def factor(n):
#             if n not in factorial:
#                 factorial[n] = math.factorial(n)
#             return factorial[n]
            
#         # 靠，搞错了，不能纯靠多项式选择。。。
#         def combinations(conlen):
#             rv = 0
#             for i in range(1, conlen + 1):
#                 rv += factor(conlen) / (factor(i) * factor(conlen - i))
#             print(conlen, rv)
#             return rv 
#         rem = 10 ** 9 + 7
#         rv = 0
#         for k, v in counter.items():
#             rv += v * combinations(k)
#         return rv % rem
            