696. 計數(shù)二進(jìn)制子串

Tags: 字符串

給定一個字符串 s，計算具有相同數(shù)量0和1的非空(連續(xù))子字符串的數(shù)量，并且這些子字符串中的所有0和所有1都是組合在一起的。重復(fù)出現(xiàn)的子串要計算它們出現(xiàn)的次數(shù)。

1. 最開始的思路首先沒有注意到可以考慮重復(fù)子串的情況，且按照最直接的思路雙重循環(huán)遍歷字符串尋找滿足條件的子串，時間復(fù)雜度達(dá)到，結(jié)果超出時間限制。
2. 參考官方題解，思路是依次計算整個字符串中的連續(xù)字符個數(shù)，保存在數(shù)組中，之后兩兩元素的遍歷這個新數(shù)組，每次累加的個數(shù)是min(arr[i], arr[i+1])。此時的時間復(fù)雜度是O(n)，空間復(fù)雜度也是O(n)。

ch_cnt = []
last_ch = ''
for ch in s:
    if ch != last_ch:
        ch_cnt.append(1)
        last_ch = ch
    else:
        ch_cnt[-1] += 1

res = 0
for i in range(len(ch_cnt)-1):
    res += min(ch_cnt[i], ch_cnt[i+1])
return res

3. 注意到2中每次只需考慮鄰接的兩個連續(xù)字符子串的長度，因此可以省去存儲整個字符串包含的連續(xù)字符子串的數(shù)組，只記錄鄰接的兩個連續(xù)字符子串的長度進(jìn)行比較計算答案，使得空間復(fù)雜度縮小至O(1)。

# 優(yōu)化空間復(fù)雜度（以下代碼是每遍歷到一個新字符，就進(jìn)行依次結(jié)果的判斷）
last_cnt = 0
this_cnt = 1
last_ch = s[0]
res = 0
for i in range(1,len(s)):
    ch = s[i]
    if ch != last_ch:
        last_ch = ch
        last_cnt = this_cnt
        this_cnt = 1
        res += 1
    else:
        this_cnt += 1
        if this_cnt <= last_cnt:
            res += 1

return res

以上代碼略顯冗余，參考題解又對代碼結(jié)構(gòu)進(jìn)一步優(yōu)化：

# 每遍歷完一個連續(xù)重復(fù)字符子串再進(jìn)行結(jié)果的計算
i, res, last = 0, 0, 0
while i < len(s):
    ch = s[i]
    cnt = 0
    while i < len(s) and s[i] == ch:
        i += 1
        cnt += 1
    res += min(cnt, last)
    last = cnt
return res