專欄：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算法文檔 。