Python
 Computer >> コンピューター >  >> プログラミング >> Python

Pythonのバイナリ文字列ですべて1の部分文字列をカウントするプログラム

バイナリ文字列sがあるとします。 「1」のみを含む部分文字列の数を見つける必要があります。答えが大きすぎる場合は、結果を10 ^ 9+7で変更します。

したがって、入力がs ="100111"の場合、出力は7になります。これは、"1"のみを含むサブ文字列が["1"、 "1"、 "1"、 "1"、"11"であるためです。 、"11"および"111"]

これを解決するには、次の手順に従います-

  • a：=0
  • count：=0
  • 範囲0からs-1のサイズのiの場合、do
    • s[i]が"0"と同じ場合、
      • a：=0
    • それ以外の場合、
      • a：=a + 1
      • count：=count + a
  • 返品数

例

理解を深めるために、次の実装を見てみましょう-

def solve(s):
   a = 0
   count = 0
   for i in range(len(s)):
      if s[i] == "0":
         a = 0
      else:
         a += 1
         count += a
   return count

s = "100111"
print(solve(s))

入力

"100111"

出力

7

  1. PythonでnノードのBSTの数をカウントするプログラム

    n個の異なるノードがあるとします。すべてが異なります。二分探索木を形成するためにそれらを配置できる方法の数を見つける必要があります。二分探索木で知っているように、左側のサブツリーは常に小さい値を保持し、右側のサブツリーは大きい値を保持します。 これを解決するために、カタラン数を見つけます。カタラン数C（n）は、n個の異なるキーを持つ二分探索木を表します。式は次のようになります $$ C（n）=\ frac {（2n）！} {（n + 1）！\ times n！} $$ したがって、入力がn =3の場合、出力は5になります。 これを解決するには、次の手順に従います- 関数ncr

  2. Pythonで指定されたインデックスを使用して文字列をシャッフルするプログラム

    文字列sとインデックスindのリストがあり、それらは同じ長さであるとします。文字列sは、位置iの文字が最終文字列のindexes[i]に移動するようにシャッフルされます。最後の文字列を見つける必要があります。 したがって、入力がs =ktoalak ind =[0,5,1,6,2,4,3]の場合、出力は「コルカタ」になります これを解決するには、次の手順に従います- fin_str：=サイズがsと同じで、0で埋められるリスト sの各インデックスiと文字vについて、実行します fin_str [ind [i]]：=v fin_strに存在する各文字を結合し