筆試算法模拟題精解之“Alice的01串”

【線上程式設計産品介紹】

阿裡雲開發者社群線上程式設計：

免費刷題大神器，助你拿到好offer

周賽月賽不停歇，做題還能領獎品

大賽筆試全真題，常做常新有驚喜

點選連結開始産品體驗：

https://developer.aliyun.com/coding 本文為大家介紹的是“65.Alice的01串”的解法探究。先來看一下題目内容：

題目描述：

檢視題目：Alice的01串

Alice給了Bob一個字元串s，Alice想讓Bob找出這個字元串中有多少個恰好包含了k個1的子串。請你幫助Bob計算出這些子串的個數。

輸入一個正整數k，表示包含1的個數(0<=k<=10^6)和一個長度不為0的字元串，字元串的長度不超過10^6

輸出一個數字，表示s中恰好包含k個1的子串的個數。

示例1

輸入：

2

"01010"

輸出：

4

方法 1：暴力搜尋

根據題意，本題可以直接用雙層循環掃描數組，找到所有的連續子串，檢視每個組合是否擁有指定數量的 1。搜尋可以做适當優化，比如内層循環找到超出 k 個 1 時，可以停止掃描，但本質上時間複雜度上界仍是二次幂。

時間複雜度：O(n^2)

空間複雜度：O(1)

方法 2：暴力搜尋的優化，滑窗法

上面暴力法的主要缺陷是，掃描過程中有過多的無用掃描，比如尋找含有 3 個 1 的 01 串，可以在前一個含有 3 個 1 的 01 串的基礎上，去掉第 1 個 1，并尋找到下 1 個 1，而不是像暴力解法一樣，每次都要從頭掃描。

請試圖在暴力搜尋二重循環的基礎上，用幾個辨別輸入串下标的變量，辨別目前搜尋 01 串的開頭和結尾，盡可能減小時間複雜度。如果設計足夠耐心的話，此方法可以達到 1 遍掃描解決的效果，但需要的分支判斷會比較多。

時間複雜度：O(n)

方法 3：尋找規律

優化本題的關鍵是設計合理的資料結構，在方法 2 的基礎上避免多餘的滑窗操作和分支判斷，直接利用每個串兩側贅餘 0 的個數，用數學方法算出 01 串數量。記錄下每個 1 出現的位置和順序，及各個 1 之間 0 的數量，這樣，隻要将 k 個 1 的最短 01 串前後 0 的數量做乘積，就得到了所有含 k 個 1 的 01 串的數量，譬如：

輸入：
2
"00101010"           

将上面的串轉化為 map 映射：

這是第幾個 1	這個 1 到上一個 1 之間 0 的數量
1
3
#

首先考察第 1 個 1 和第 2 個 1 組成的最短 01 串：

"00101010"

前後分别有 2 和 1 個 0：

重點： 此時可以直接算出，第 1 個 1 和第 2 個 1 組成的 “含 2 個 1 的 01 串” 的數量為：

(2+1)*(1+1)=6

；用類似的方法繼續計算第 2 和第 3 個 1 組成的 01 串數量，加到一起就得到了答案。

将上面的思路轉換為代碼，大緻分為幾步：

• 周遊輸入串，用散清單，或者數組，記錄下每個 1 到上個 1（也可以記錄每個 1 到下個 1）的 0 的個數。
• 周遊生成的散清單或數組，同時用兩個臨時變量辨別目标 01 串的第一個 1 和最後一個 1 的位置，直接利用他們前/後的 0 的個數做乘積。累加得到結果。

這種解法寫代碼的思路會相對清晰，相對解法 2 滑窗的分支判斷較少。

注意： 計算時，注意需要将間隔的 0 的數量 2 和 1 分别 +1 後再彼此相乘，因為最短 01 串兩側分别不包含任何 0，也是一種符合題意的 Alice01 串。

空間複雜度：O(n)

看完之後是不是有了答題思路了呢，快來練練手吧：

65.Alice的01串

線上程式設計周賽、月賽火熱進行中，更有限時答題活動，社群定制衛衣、雙肩背包等你來拿~每天都有好禮相送~點選了解周賽詳情：

線上程式設計内測中，搶先周賽赢好禮！面試考試前，快來刷刷題！

上一篇： 筆試算法模拟題精解之“超車”的兩種解法 下一篇： 筆試算法模拟題精解之“2的幂次方數”