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

Pythonを使用して1のみの部分文字列の数を見つけるプログラム

バイナリ文字列sがあるとします。すべての文字が1である部分文字列の数を見つける必要があります。答えは非常に大きい可能性があるため、結果mod 10 ^ 9+7を返します。

したがって、入力がs ="1011010"の場合、出力は5になります。これは1.4回"1"2.1回"11"

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

  • m：=10 ^ 9 + 7

  • 結果：=0

  • div：=「0」を使用してバイナリ文字列を分割する

  • div内のxごとに、実行します

    • xが空の場合は、次の反復に進みます

    • 結果：=結果+（xのサイズ*（x +1のサイズ））/2の商

  • 結果を返すmodm

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

例

def solve(s):
   m = 10**9+7
   result = 0
   for x in s.split('0'):
      if not x: continue
      result += (len(x)*(len(x)+1)) // 2
   return result % m
s = "1011010"
print(solve(s))

入力

"1011010"

出力

5

  1. Pythonを使用して、同じラベルを持つサブツリー内のノードの数を見つけるプログラム

    ノードに0からn-1までの番号が付けられたn個のノードを持つルート化された一般ツリーがあるとします。各ノードには、小文字の英字のラベルがあります。ラベルはlabels配列の入力として指定されます。ここで、lables[i]にはi番目のノードのラベルが含まれています。ツリーはエッジリストで表され、各エッジeには[u、v]があり、uは親、vは子を表します。サイズnの配列Aを見つける必要があります。これは、iと同じラベルを持つi番目のノードのサブツリー内のノードの数を表します したがって、入力が次のような場合 ここで、n =5およびlabel=“ ccaca” ルートには同じラベルの子

  2. Pythonを使用して最大の確率でパスを見つけるプログラム

    n個のノード（ノードには0から番号が付けられます）を持つ無向加重グラフがあるとします。このグラフは、エッジリストを使用して入力として与えられ、各エッジeについて、そのエッジ確率[e]を通過する成功の確率があります。開始ノードと終了ノードもあります。最初から最後まで成功の確率が最大のパスを見つけて、成功の確率を返す必要があります。パスが見つからない場合は、0を返します。 したがって、入力が次のような場合 ノード0から2へのパスが2つあるため、出力は0.24になります。1つは確率0.2、もう1つはノード1を経由するパスの確率は0.4 * 0.6 =0.24で、これが最大です。 これを解