1

私は質問を受けました：

文字列のリストとクエリのリスト (START と END) が与えられます。どちらも文字列です。[START, END) の範囲内にある文字列の数を見つける必要があります。

例: 文字列A, AA, AB, CD, ZS, XYZ のリスト: クエリのリスト:

A, AA
A, CC
AB, ZZ
AC, CD

出力は次のようになります。

1
3
3
0

私がこの問題に取り組む方法は次のとおりです。文字列のリストを繰り返し処理しながら、新しい文字列を 1 つずつ挿入して AVL ツリーを作成します。(最初はアンバランスBSTを使っていたのですが、Time Limitをつけてしまいました。) 比較をするときはjava StringのcompareTo関数を使います。

AVL ツリーを作成した後、[start, end) からカウントするクエリを実行します。私のやり方は、

1. let v = root.

2. if v==null -> return 0 

   else if v.value < start -> count(v.right)

   else if v.value >= end -> count(v.left)

   else 1 + count(v.right) + count(v.left)

しかし、私はまだ制限時間のパーナリティを持っています:(

そこで、メソッドを変更して double にハッシュしてハッシュ関数を作成し、compareTo を使用する代わりに、代わりにハッシュ値を比較しました。

でも、まだ時間制限があります！

そのため、サブツリー サイズの値を各頂点に格納し、count または時間を使用する代わりに条件文を追加します。その一部は、count 関数を再帰的に呼び出す代わりにサブツリーのサイズを使用できます。

特定の時間に実行するための提案はありますか? :\

4

1 に答える 1

0

注文統計ツリーを使用します: http://en.wikipedia.org/wiki/Order_statistic_tree

これは基本的に、各ノードがそのサブツリーのサイズを格納する修正されたバランスの取れた bst であり、log(n) 時間で特定のアイテムの前にいくつのアイテムがあるかについてのクエリに答えることができます。

于 2013-08-24T09:39:27.673 に答える