專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

專欄：50多種經(jīng)典圖論算法全部掌握

最近在網(wǎng)上看到一篇微博，統(tǒng)計2024年中國互聯(lián)網(wǎng)大廠的收入和凈利潤，通過統(tǒng)計的數(shù)據(jù)可以看到，收入和凈利潤排名第一的是字節(jié)跳動，果然是中國最賺錢的公司，騰訊的凈利潤排在第二，收入排在第 5 位。

最讓人不可思議的是拼多多，倒不是因為它的凈利潤高，而是因為它的員工太少了，區(qū)區(qū)1.3萬人，竟然創(chuàng)造了1000多億的凈利潤，如果我沒算錯的話，人均創(chuàng)造的凈利潤快超過一千萬了吧，恐怖如斯，這么多凈利潤為啥不能多提供點工作崗位。

最受網(wǎng)友稱贊的是京東，收入雖然很高，一萬多億，但員工也多，高達(dá)60多萬人，養(yǎng)活了那么多員工，所以凈利潤并不高，被網(wǎng)友成為中國最牛企業(yè)，也是最有但當(dāng)?shù)钠髽I(yè)。

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

來看下今天的算法題，這題是LeetCode的第1513題：僅含 1 的子串?dāng)?shù)，難度是中等。

給你一個二進制字符串 s（僅由 '0' 和 '1' 組成的字符串）。返回所有字符都為 1 的子字符串的數(shù)目。由于答案可能很大，請你將它對 10^9 + 7 取模后返回。

示例1：

輸入：s = "0110111" 輸出：9 解釋：共有 9 個子字符串僅由 '1' 組成 "1" -> 5 次 "11" -> 3 次 "111" -> 1 次

示例2：

輸入：s = "101" 輸出：2 解釋：子字符串 "1" 在 s 中共出現(xiàn) 2 次

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

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

問題分析

這題讓統(tǒng)計所有字符都為 1 的子字符串的數(shù)目，解這題之前我們首先來找下規(guī)律：

1，如果是"1"，那么它貢獻(xiàn)的數(shù)量就是 1 。

2，如果是"11"（這里為了區(qū)分兩個 1 ，使用了不同的顏色），它貢獻(xiàn)是數(shù)量是 3 ，分別是"1"，"1"，"11"。

3，如果是"111"，它貢獻(xiàn)的數(shù)量是 6 ，分別是 "1"，"1"，"1"，"11"，"11"，"111"。注意"11"不是的，因為它兩個不是連續(xù)的。

4，如果是"1111"，它貢獻(xiàn)的數(shù)量就是6+4，6 是前面 3 個數(shù)字貢獻(xiàn)的，4 是當(dāng)我們添加第 4 個數(shù)字的時候貢獻(xiàn)的。

所以我們可以得出結(jié)論，如果是連續(xù)的 n 個 1 ，那么它貢獻(xiàn)的數(shù)量就是 1+2+……+n，也就是n*(n+1)/2。

有了這個公式，我們直接統(tǒng)計字符串中所有連續(xù) 1 的個數(shù)，然后帶入公式計算即可。

JAVA：

publicintnumSub(String s){     int i = 0, n = s.length();     int mod = 1000000007;     int ans = 0;     while (i < n) {         long cnt = 0;// 統(tǒng)計連續(xù) 1 的個數(shù)。         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;// 統(tǒng)計連續(xù) 1 的個數(shù)。             while (i < n && s[i++] == '1')                 cnt++;             ans += (cnt * (cnt + 1) / 2) % mod;             ans %= mod;         }         return ans;     }

筆者簡介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個算法網(wǎng)站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。