696.カウントバイナリサブストリング(Python)
2069 ワード
タイトル
難易度:★☆☆☆タイプ:文字列
1つの文字列sが与えられ、0と1の同じ数の非空(連続)サブ文字列の数が計算され、これらのサブ文字列のすべての0とすべての1が結合される.
繰り返されるサブストリングは、それらが現れる回数を計算します.
s.lengthは1から50000の間にあることに注意してください.sには「0」または「1」の文字のみが含まれます.
例1
入力:0010011出力:6説明:6個のサブストリングが同じ数の連続1と0を有する:“0011”、“01”、“1100”、“10”、“0011”と“01”.いくつかの重複するサブストリングは、それらの出現回数を計算することに注意してください.また、「0010011」は、すべての0(および1)が組み合わせられていないため、有効なサブ列ではない.
例2入力:「10101」出力:4説明:「10」、「01」、「10」、「01」、「01」の4つのサブ列があり、それらは同じ数の連続する1と0を有する.
に答える
長さ2のスライド窓を用いて文字列全体を遍歴し,ウィンドウ内の2文字(s[i]とs[i+1])が異なる場合,この長さ2のサブ列を基に左右に同期して拡張し,伸長したサブ列が要求を満たすかどうかを検出した.期間中、要求を満たすサブストリングの数を変数で即時に統計する必要があります.
例:
質問やアドバイスがあれば、コメントエリアへようこそ~
難易度:★☆☆☆タイプ:文字列
1つの文字列sが与えられ、0と1の同じ数の非空(連続)サブ文字列の数が計算され、これらのサブ文字列のすべての0とすべての1が結合される.
繰り返されるサブストリングは、それらが現れる回数を計算します.
s.lengthは1から50000の間にあることに注意してください.sには「0」または「1」の文字のみが含まれます.
例1
入力:0010011出力:6説明:6個のサブストリングが同じ数の連続1と0を有する:“0011”、“01”、“1100”、“10”、“0011”と“01”.いくつかの重複するサブストリングは、それらの出現回数を計算することに注意してください.また、「0010011」は、すべての0(および1)が組み合わせられていないため、有効なサブ列ではない.
例2入力:「10101」出力:4説明:「10」、「01」、「10」、「01」、「01」の4つのサブ列があり、それらは同じ数の連続する1と0を有する.
に答える
長さ2のスライド窓を用いて文字列全体を遍歴し,ウィンドウ内の2文字(s[i]とs[i+1])が異なる場合,この長さ2のサブ列を基に左右に同期して拡張し,伸長したサブ列が要求を満たすかどうかを検出した.期間中、要求を満たすサブストリングの数を変数で即時に統計する必要があります.
class Solution:
def countBinarySubstrings(self, s: str) -> int:
count = 0 #
for i in range(len(s)-1): #
left, right = s[i], s[i+1] #
left_idx, right_idx = i, i+1 #
if left != right: # ,
# ,
while 0 <= left_idx <= right_idx < len(s) and \
s[left_idx] == left and s[right_idx] == right:
count += 1 # +1
left_idx, right_idx = left_idx - 1, right_idx + 1 #
return count
例:
:“00001111”
i 0、1、2 , s[i]!=s[i+1] ;
i = 3 ,s[i]='0',s[i+1]='1', , "01", +1, :
i = 3, 1 , s[i-1]=='0',s[i+2]=='1', s[i-1:i+3]="0011", +1;
i = 3, 2 , s[i-2]=='0',s[i+3]=='1', s[i-2:i+4]="000111", , +1;
i = 3, 3 , s[i-3]=='0',s[i+4]=='1', s[i-3:i+5]=="00001111", , +1;
i = 3, 4 , , i=3 。
i 4,5,6 , 1, 。
質問やアドバイスがあれば、コメントエリアへようこそ~