一 🏠 题目描述
1513. 仅含 1 的子串数
给你一个二进制字符串 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
二 🏠破题思路
2.1 🚀 关键信息
解决问题第一步，当然先提取题目字面上的关键信息 😎😎😎
如示例三，输入 111111 = 6 + 5+ 4 + 3 + 2 + 1 = 21
从上述示例易知，对于任意一个连续 1 个数为 N 的子串，它子串数 = N + (N-1) + . . . + 2 + 1 🌸🌸🌸
如示例一，输入 0110111= （2 +1）+（3 +2+1）=9
因此上述问题即转换为对于输入字符串，求它任意一个连续 1 个数为 N 序列的子串数之和 💐💐💐
提取完题目中的关键信息后，直接进入第二阶段，思路整理 😃😃😃
2.2 🚀 思路整理
正向遍历法
遍历字符串，遇到 1 则用 count 值记录 1 个数，并将当前 count 累加（1 + 2 + . . . + (N-1) + N ）
遇到 0 则把 count 值置为 0 ，表示 1 个数为 0，最后将所有 count 累加结果输出即可 🌷🌷🌷
小细节：在累计子串数之和时，有可能会超过短整型的最大长度，注意溢出问题
注：解法出处 ，有部分删减
整理完解题思路后，直接进入第三阶段，代码实现 😃😃😃
三 🏠 代码详解
3.1 🚀 代码实现
按照我们刚才的破题思路，直接代码走起来 👇👇👇👇
int numSub(string s) { int len = s.size(), count =0; //获取字符串长度, 初始化当前 1 个数 long result =0; //初始化当前 count 累加和 for(int i =0; i < len; i++) { //遍历字符串 if (s[i]=='1') { //当前字符为 1 count++; //当前 1 个数加加 result += count; //count 累加 } else { //当前字符为 0 count =0; //把当前 1 个数置为 0 } } return result % (1e9 +7); //返回 count 累加和 }
3.2 🚀 细节解析
看完 👀👀👀 全注释版的代码实现后，相信看官大大对整体逻辑已经是大写的 OK 了 😃😃😃
那么我们挖掘上述实现的晦涩细节 😖😖😖 进行解析，直接开干，走起来 👇👇👇👇
long result =0; //初始化当前 count 累加和
题目描述中 MAX(s.length) = 10^5 ，故 count 并没有溢出风险 🐌🐌🐌
在累计子串数之和时，有可能会超过短整型的最大长度，注意溢出问题 🐳🐳🐳
四 🏠 心路历程
为方便各位看官大大了解博主真实刷题过程，我把当时状态纯纯真实还原，记录在心路历程这一小节，不感兴趣的小伙伴可以直接跳过哈
博主在第一阶段提取 🚀 关键信息没有问题，在第二阶段 🚀 思路整理没有问题
代码实现时未想到 将当前 count 累加（1 + 2 + . . . + (N-1) + N ）的方式，而对于 calCountVal 的方式在函数内部会有溢出问题，故代码简洁性差 😭😭😭 ，代码如下 👇👇👇👇
const long long checkValNum = pow(10, 9) +7; long long calCountVal(long long len) { if (len !=1) { long long currentVal = len + calCountVal(len -1); if (currentVal < checkValNum) return currentVal; else return currentVal % checkValNum; } else { return 1; } } int numSub(string s) { long long len = s.size(); long long subLen =0, count =0; for (long long i =0; i < len; ++i) { if (s[i] =='1') ++subLen; if ((s[i] =='0' || i == len -1) && subLen !=0) { long long countVal = count + calCountVal(subLen); subLen =0; if (countVal < checkValNum) count = countVal; else count = countVal % checkValNum; } } return count; }
