上海
专栏：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算法文档 。
特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
