LC1513 全1子串数

题面

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的子区间长度，然后计算等差数列的和就可以了
  待续