开发者社区> Cool架构> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

Cool说丨力扣5461

简介: [5461. 仅含 1 的子串数](https://leetcode-cn.com/problems/number-of-substrings-with-only-1s/)
+关注继续查看


5461. 仅含 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

1、很简单的做法

C++,双百 为预防数据量过大,先进行结果的保存,结果发现数据量1不是很大...尴尬

   int numSub(string s) {

       int len = s.size();

       int mod = 1e9 + 7,res = 0;

       vector<int> dp(len + 1, 0);

       for (int i = 1; i <= len; ++i) {

           dp[i] += (dp[i-1] +i)%mod ;

       }

        

       for(int low = 0, high =0; low<len;){          

           if(s[low] == '1'){

               high = low + 1;

               while( high<len && s[high] == '1') { ++high; } //统计连续1的个数              

               res += dp[high-low];

               res %= mod;

               low = high -1;

           }

           low++;

            

       }

        

       return res;      

   }

2、是我想多了

执行用时:32 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗:8.9 MB, 在所有 C++ 提交中击败了100.00%的用户

   int numSub(string s) {        

       int mod = 1e9+7,len = s.size();

       int res = 0,count = 0;

       for(int i = 0; i < len; ++i){

           if(s[i] == '1'){

               ++count;

               res = ( res + count )%mod;

           }else{

               count = 0;

           }

       }      

       return res;    

   }


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Cool说丨力扣3
[3. 无重复字符的最长子串](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/)
11 0
Cool说丨力扣989
989. 数组形式的整数加法
20 0
Cool说丨力扣840
840. 矩阵中的幻方
8 0
Cool说丨力扣718
[718. 最长重复子数组](https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/)
19 0
Cool说丨力扣6
6. Z 字形变换
15 0
Cool说丨力扣914
914.卡牌分组
10 0
Cool说丨力扣1128
1128. 等价多米诺骨牌对的数量
14 0
Cool说丨力扣153、454
153. 寻找旋转排序数组中的最小值 454. 四数相加 II
32 0
Cool说丨力扣153、454
153. 寻找旋转排序数组中的最小值 454. 四数相加 II
14 0
Cool说丨力扣205
[205. 同构字符串](https://leetcode-cn.com/problems/isomorphic-strings/)
10 0
+关注
Cool架构
大三在读,两次国奖,竞赛生。
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载