696. 計數(shù)二進制子串
Tags: 字符串
給定一個字符串 s，計算具有相同數(shù)量0和1的非空(連續(xù))子字符串的數(shù)量垢袱，并且這些子字符串中的所有0和所有1都是組合在一起的。重復(fù)出現(xiàn)的子串要計算它們出現(xiàn)的次數(shù)港柜。
- 最開始的思路首先沒有注意到可以考慮重復(fù)子串的情況请契，且按照最直接的思路雙重循環(huán)遍歷字符串尋找滿足條件的子串，時間復(fù)雜度達到
夏醉，結(jié)果超出時間限制爽锥。
- 參考官方題解，思路是依次計算整個字符串中的連續(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
- 注意到2中每次只需考慮鄰接的兩個連續(xù)字符子串的長度玄捕，因此可以省去存儲整個字符串包含的連續(xù)字符子串的數(shù)組踩蔚，只記錄鄰接的兩個連續(xù)字符子串的長度進行比較計算答案，使得空間復(fù)雜度縮小至O(1)枚粘。
# 優(yōu)化空間復(fù)雜度（以下代碼是每遍歷到一個新字符馅闽，就進行依次結(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)進一步優(yōu)化：
# 每遍歷完一個連續(xù)重復(fù)字符子串再進行結(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
