专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

最近在网上看到一篇微博，统计2024年中国互联网大厂的收入和净利润，通过统计的数据可以看到，收入和净利润排名第一的是字节跳动，果然是中国最赚钱的公司，腾讯的净利润排在第二，收入排在第 5 位。

最让人不可思议的是拼多多，倒不是因为它的净利润高，而是因为它的员工太少了，区区1.3万人，竟然创造了1000多亿的净利润，如果我没算错的话，人均创造的净利润快超过一千万了吧，恐怖如斯，这么多净利润为啥不能多提供点工作岗位。

最受网友称赞的是京东，收入虽然很高，一万多亿，但员工也多，高达60多万人，养活了那么多员工，所以净利润并不高，被网友成为中国最牛企业，也是最有但当的企业。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第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 次

  • s[i] == '0' 或 s[i] == '1'

  • 1 <= s.length <= 10^5

问题分析

这题让统计所有字符都为 1 的子字符串的数目，解这题之前我们首先来找下规律：

1，如果是"1"，那么它贡献的数量就是 1 。

2，如果是"11"（这里为了区分两个 1 ，使用了不同的颜色），它贡献是数量是 3 ，分别是"1"，"1"，"11"。

3，如果是"111"，它贡献的数量是 6 ，分别是 "1"，"1"，"1"，"11"，"11"，"111"。注意"11"不是的，因为它两个不是连续的。

4，如果是"1111"，它贡献的数量就是6+4，6 是前面 3 个数字贡献的，4 是当我们添加第 4 个数字的时候贡献的。

所以我们可以得出结论，如果是连续的 n 个 1 ，那么它贡献的数量就是 1+2+……+n，也就是n*(n+1)/2。

有了这个公式，我们直接统计字符串中所有连续 1 的个数，然后带入公式计算即可。

JAVA：

publicintnumSub(String s){     int i = 0, n = s.length();     int mod = 1000000007;     int ans = 0;     while (i < n) {         long cnt = 0;// 统计连续 1 的个数。         while (i < n && s.charAt(i++) == '1')             cnt++;         ans += (cnt * (cnt + 1) / 2) % mod;         ans %= mod;     }     return ans; }

C++：

public:     intnumSub(string s){         int i = 0, n = s.length();         int mod = 1000000007;         int ans = 0;         while (i < n) {             long cnt = 0;// 统计连续 1 的个数。             while (i < n && s[i++] == '1')                 cnt++;             ans += (cnt * (cnt + 1) / 2) % mod;             ans %= mod;         }         return ans;     }

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。