Unique Binary Search Trees leetcode java
4092 ワード
タイトル:
Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example, Given n = 3, there are a total of 5 unique BST's.
よく知っている
カトラン数の友人が発見したかもしれませんが、これはまさに
カトラン数の定義方法であり、典型的な動的計画の定義方法である(実際の条件と繰返し式の結果に基づいて).したがって,メンテナンス量res[i]はi個のノードを含む二叉ルックアップツリーの数を表すことも考えられる.上記の繰返し式から順に1~nの結果を求めればよい.
時間的にi個のノードの二叉ルックアップツリー数を解くたびにiステップのループが必要となり,全体的にn回が要求されるため,総時間複雑度はO(1+2+...+n)=O(n^2)である.空間的にはメンテナンスのために配列が必要であり,前のi個のすべての情報が必要であるためO(n)である."
解釈のもっとはっきりした分析を見て、http://fisherlei.blogspot.com/2013/03/leetcode-unique-binary-search-trees.html:
“
この問題は長いこと考えてやっとはっきりした.実は前例の順序を変えれば、法則が見えてくる.
例えば、1を根にした木がいくつあるかは、2つの要素を持つサブツリーがいくつあるかによって決まります.同様に,2がルートのサブツリーは1つの要素に依存するサブツリーがいくつかある.3をルートとする場合は、1と同じです.Count[i]を[0,i]で生成できるUnique Binary Treeの数として定義し、配列が空の場合、間違いなく1つのBST、すなわち空のツリーのみ、Count[0]=1配列が1つの要素{1}しかなく、1つのBSTのみ、1つのノードCount[1]=1配列に2つの要素{1,2}がある場合、では、1 2/2 1 Count[2]=Count[0]*Count[1](1がルートの場合)+Count[1]*Count[0]の2種類があります.(2がルートの場合.3つの要素の配列をもう一度見てみると、BSTの値の取り方は、Count[3]=Count[0]*Count[2](1がルートの場合)+Count[1]*Count[1](2がルートの場合)+Count[2]*Count[0](3がルートの場合)であることがわかるので、これによって観察すると、Countの繰返し式はCount[i]=ΣCount[0...k]*[k+1....i]0<=k[Note]これはおもしろい問題です.この問題を手に入れたばかりの頃は、そこから手をつけるのか全く分かりませんでしたが、BSTに対してUniqueがあるかどうかは判断しにくいからです.最後に条件を導入すると,配列が1,2,3,4のとき,すぐに明らかになった.i,.. nの場合、iをルートノードとするツリーであり、その左サブツリーが[1,i−1]からなり、右サブツリーが[i+1,n]からなるという原則に基づくBST構築ツリーは一意性を有する.
”
また,繰返し式に基づいてプログラムを書くためには,繰返し式を簡略化する必要がある.
カルトラン数,C 0 Cn+1によればleetcode入力のパラメータはnであるため,混同を避けるためにここで繰返し式はCt+1と書き,初期値はC 0=1である.
元の繰返し式は、Ct+1+=Ci*Ct-i(0<=i<=t)
変数num=t+1、t=num-1
したがって、元の繰返し式は変数としてCnum+=Ci*Cnum-1-i(0<=i<=num-1)に置き換えられる.
一方numの値範囲は[1,n]であり、C 0が既知であるためである.
コードは次のとおりです.
1
public
int numTrees(
int n) {
2
if(n == 0||n == 1)
3
return 1;
4
5
int[] C =
new
int[n+1];
6 C[0] = 1;
7
//
繰返し式はCt+1+=Ci*Ct-i(0<=i<=t)
8
//
num=t+1
9
//
場合t=num-1;
10
//
したがって、プッシュは次のようになります.
11
//
Cnum += Ci*Cnum-1-i(0<=i<=num-1, 1<=num<=n)
12
//
C0 = 1
13
14
for(
int num=1;num<=n;num++){
15
for(
int i=0;i<=num-1;i++){
16 C[num] += C[i]*C[(num-1)-i];
17 }
18 }
19
return C[n];
20 }
Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example, Given n = 3, there are a total of 5 unique BST's.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
：
， ， 。。 ， 。。
Code Ganker(http://blog.csdn.net/linhuanmars/article/details/24761459) ：
“ ， ， 。 ， ，
， ， 。 ：
よく知っている
カトラン数の友人が発見したかもしれませんが、これはまさに
カトラン数の定義方法であり、典型的な動的計画の定義方法である(実際の条件と繰返し式の結果に基づいて).したがって,メンテナンス量res[i]はi個のノードを含む二叉ルックアップツリーの数を表すことも考えられる.上記の繰返し式から順に1~nの結果を求めればよい.
時間的にi個のノードの二叉ルックアップツリー数を解くたびにiステップのループが必要となり,全体的にn回が要求されるため,総時間複雑度はO(1+2+...+n)=O(n^2)である.空間的にはメンテナンスのために配列が必要であり,前のi個のすべての情報が必要であるためO(n)である."
解釈のもっとはっきりした分析を見て、http://fisherlei.blogspot.com/2013/03/leetcode-unique-binary-search-trees.html:
“
この問題は長いこと考えてやっとはっきりした.実は前例の順序を変えれば、法則が見えてくる.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3例えば、1を根にした木がいくつあるかは、2つの要素を持つサブツリーがいくつあるかによって決まります.同様に,2がルートのサブツリーは1つの要素に依存するサブツリーがいくつかある.3をルートとする場合は、1と同じです.Count[i]を[0,i]で生成できるUnique Binary Treeの数として定義し、配列が空の場合、間違いなく1つのBST、すなわち空のツリーのみ、Count[0]=1配列が1つの要素{1}しかなく、1つのBSTのみ、1つのノードCount[1]=1配列に2つの要素{1,2}がある場合、では、1 2/2 1 Count[2]=Count[0]*Count[1](1がルートの場合)+Count[1]*Count[0]の2種類があります.(2がルートの場合.3つの要素の配列をもう一度見てみると、BSTの値の取り方は、Count[3]=Count[0]*Count[2](1がルートの場合)+Count[1]*Count[1](2がルートの場合)+Count[2]*Count[0](3がルートの場合)であることがわかるので、これによって観察すると、Countの繰返し式はCount[i]=ΣCount[0...k]*[k+1....i]0<=k
”
また,繰返し式に基づいてプログラムを書くためには,繰返し式を簡略化する必要がある.
カルトラン数,C 0 Cn+1によればleetcode入力のパラメータはnであるため,混同を避けるためにここで繰返し式はCt+1と書き,初期値はC 0=1である.
元の繰返し式は、Ct+1+=Ci*Ct-i(0<=i<=t)
変数num=t+1、t=num-1
したがって、元の繰返し式は変数としてCnum+=Ci*Cnum-1-i(0<=i<=num-1)に置き換えられる.
一方numの値範囲は[1,n]であり、C 0が既知であるためである.
コードは次のとおりです.
1
public
int numTrees(
int n) {
2
if(n == 0||n == 1)
3
return 1;
4
5
int[] C =
new
int[n+1];
6 C[0] = 1;
7
//
繰返し式はCt+1+=Ci*Ct-i(0<=i<=t)
8
//
num=t+1
9
//
場合t=num-1;
10
//
したがって、プッシュは次のようになります.
11
//
Cnum += Ci*Cnum-1-i(0<=i<=num-1, 1<=num<=n)
12
//
C0 = 1
13
14
for(
int num=1;num<=n;num++){
15
for(
int i=0;i<=num-1;i++){
16 C[num] += C[i]*C[(num-1)-i];
17 }
18 }
19
return C[n];
20 }