X

LEETCODE 1513. Number of Substrings With Only 1s 解题思路分析

题目大意:

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1513

解题思路分析:

这道题难度不大,首先找到每个连续是1的子数组,并查看这些数组中包含多少个子数组即可。比如”11111″,其中有一个长度为5的子数组,2个长度为4的子数组,3个长度为3的子数组,4个长度为2的子数组,以及5个长度为1的子数组。总结来说,如果一个数组的长度为n,那么他的子数组个数共为1+2+3+….+n。

解题时,我们建立2个变量,一个作为返回结果res。另一个作为当前连续是1的子数组长度length。两个变量的初始值都为0。接下来开始循环字符串中每个字符,当遇到1时,length加一,根据上文讲到的统计子数组的公式,我们将length累加至返回结果res。当遇到0时,重置length为0。

实现代码:

public int numSub(String s) {
    long res=0; // 返回结果
    long length=0; // 当前连续1的区间长度
    char[] arr=s.toCharArray(); // 为了提高效率,将字符串转为数组
    for(int i=0;i<arr.length;i++){ // 循环每个字符
        if(arr[i]=='1'){ // 如果当前字符是1
            length++; // 连续1的区间加一
            res+=length; // 当前区间长度即是新增的全是1的子数组个数
            res=res%1000000007; // 取模
        }else{ // 如果当前字符是0
            length=0; // 重置length
        }
    }
    return (int)res;
}

本题解法执行时间为6ms。

Runtime: 6 ms, faster than 91.80% of Java online submissions for Number of Substrings With Only 1s.

Memory Usage: 39.6 MB, less than 100.00% of Java online submissions for Number of Substrings With Only 1s.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1513-number-of-substrings-with-only-1s-解题思路分析/
Categories: leetcode
kwantong: