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

一意の二分探索木の数をカウントするプログラムは、Pythonで0からnの値で形成できます

1つの数nがあるとすると、[0、n）からの数で生成できる一意のBSTの数を見つける必要があります。答えが非常に大きい場合、結果は10 ^ 9 + 7

になります。

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

一意の二分探索木の数をカウントするプログラムは、Pythonで0からnの値で形成できます

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

  • 数値：=1
  • denom：=n + 1
  • 1からnの範囲のiについては、
    • numer：=numer * n + i
    • numer：=numer mod m
    • denom：=denom * i
    • denom：=denom mod m
  • numer：=numer *（denom ^（m-2））mod m
  • return numer mod m

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

例

class Solution:
   def solve(self, n):
      m = 10 ** 9 + 7
      numer = 1
      denom = n + 1
      for i in range(1, n + 1):
         numer *= n + i
         numer %= m
         denom *= i
         denom %= m
         numer *= pow(denom, m-2, m)
      return numer % m
ob = Solution()
print(ob.solve(4))

入力

4

出力

14

  1. Pythonのバイナリツリーから偶数の値を持つすべての葉を削除するプログラム

    二分木があるとすると、値が偶数のすべての葉を繰り返し削除します。すべてを削除した後、値が偶数のルートしかない場合は、それも削除されます。 したがって、入力が次のような場合 その場合、出力は次のようになります これを解決するには、次の手順に従います- 関数solve（）を定義します。これが定着します ルートがnullの場合、 nullを返す ルートの左側：=solve（ルートの左側） ルートの権利：=solve（ルートの権利） ルートがリーフで、ルートのデータが偶数の場合、 nullを返す ルートを返す

  2. 連続する1’のないバイナリ文字列の数をカウントするPythonプログラム

    この記事では、以下に示す問題ステートメントの解決策について学習します。 問題の説明 −正の整数Nが与えられているので、文字列に連続する1が存在しないように、長さNで使用可能なすべての可能な個別のバイナリ文字列をカウントする必要があります。 次に、以下の実装のソリューションを見てみましょう- 例 # count the number of strings def countStrings(n):    a=[0 for i in range(n)]    b=[0 for i in range(n)]    a[0] = b[0]