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不是很大...尴尬

   intnumSub(strings) {

       intlen=s.size();

       intmod=1e9+7,res=0;

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

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

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

       }

       

       for(intlow=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++;

           

       }

       

       returnres;      

   }

2、是我想多了

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

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

   intnumSub(strings) {        

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

       intres=0,count=0;

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

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

               ++count;

               res= ( res+count )%mod;

           }else{

               count=0;

           }

       }      

       returnres;    

   }


目录
相关文章
|
人工智能 C# C++
Cool说丨力扣153、454
153. 寻找旋转排序数组中的最小值 454. 四数相加 II
135 1
|
C# C++
Cool说丨力扣287/792/378
关注博主,获取更多知识
112 0
|
C# C++ 索引
Cool说丨力扣162
162. 寻找峰值
100 0
|
存储 C# C++
Cool说丨力扣29/34
关注博主。获取更多知识
112 0
|
存储 C# C++
Cool说丨力扣392
392. 判断子序列
77 0
|
C# C++
Cool说丨力扣744、704
744. 寻找比目标字母大的最小字母 704. 二分查找
111 0
|
C#
Cool说丨力扣475
475. 供暖器
119 0
|
机器学习/深度学习 算法 C#
Cool说丨力扣202
202. 快乐数
104 0
|
C#
Cool说丨力扣167
167. 两数之和 II - 输入有序数组
73 0
|
C# C++
Cool说丨力扣374、441
441. 排列硬币 374. 猜数字大小
99 0