题面
LC1513
代码
class Solution:def numSub(self, s: str) -> int:subLens = []count = 0for i in range(len(s)):if s[i] == '1':count+=1elif s[i] == '0':subLens.append(count)count = 0subLens.append(count)# 计算组合数cache = {}def calc(n: int) -> int:try:return cache[n]except:res = n*(n+1)/2cache[n] = resreturn resres=0for slen in subLens:res += calc(slen)return int(res % (10**9+7))
思路
- 尝试cache等差数列求和的结果，但是GPT说没有必要
- 直接扫描找出连续全1的子区间长度，然后计算等差数列的和就可以了
待续