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

可能なBSTの数を見つけるプログラムは、Pythonのn個の異なるノードを使用して生成できます

数nがあるとします。 [1,2、...、n]のような数がある場合、これらのn個の値を使用して形成できるBSTの数を数える必要があります。答えが大きすぎる場合は、結果を10 ^ 9+7で変更します。

したがって、入力がn =3の場合、出力は14になります。

可能なBSTの数を見つけるプログラムは、Pythonのn個の異なるノードを使用して生成できます

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

  • a：=値が[0、1]のリスト
  • m：=10 ^ 9 + 7
  • max_n：=1000
  • 2からmax_n+1の範囲のkについては、
    • （1 +リストのすべての要素の合計（a [i] * a [k --i] for all i in range（1、k）））modmをaの最後に挿入します
  • return（a [n + 1]-1）mod m

例

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

def solve(n):
   a = [0, 1]
   m = 10**9+7
   max_n = 1000

   for k in range(2, max_n + 2):
      a.append((1 + sum(a[i] * a[k - i] for i in range(1, k))) % m)
   return ((a[n + 1] - 1) % m)

n = 3
print(solve(n))
>

入力

3

出力

14

  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で範囲内のノード数を見つけるプログラム

    BSTがあり、左と右の境界lとrもあるとすると、lとrの間に値が存在するルート内のすべてのノードの数を見つける必要があります。 したがって、入力が次のような場合 l =7、r =13の場合、8、10、12の3つのノードがあるため、出力は3になります。 これを解決するために、次の手順に従います- スタック：=スタックと最初にルートを挿入し、カウント：=0 スタックが空でないときに、実行します node：=スタックの最上位要素、およびポップ要素 ノードがnullでない場合、 l<=ノードのデータ<=rの場合、 count：=count + 1