2

最近、インタビュー中に次の質問に出くわしました。

序列あり{a1, a2, a3, a4, ..... aN}。実行は、シーケンスの最大の厳密に増加または厳密に減少する連続部分です。例えば。シーケンスがある場合、、 、、およびの{1,2,3,4,7,6,5,2,3,4,1,2} 5 つの可能な実行があります。{1,2,3,4,7}{7,6,5,2}{2,3,4}{4,1}{1,2}

N4 つの数値, M, K,が与えられLます。N正確に連M数があり、シーケンス内の各K数値が以下であり、隣接する数値間の差が以下である可能性のある数列の数を数えLます。

4

3 に答える 3

1

おそらく、分析的に分析して O(1) ソリューションを考え出す方法があります。ただし、それを理解するには、私よりもはるかに賢い人が必要です:) これが動的プログラミングのソリューションです。

このソリューションでは、すべての値が正でなければならないと仮定しています。さらに、シーケンス内のすべての値が前の値と等しくない必要があると想定しています。これらの条件は両方とも暗示されているように見えますが、質問では明示的に述べられていません.

まず、 、 、、に加えてN、シーケンスの最後の項 a nの値も与えられるように、問題を少し変更してみましょう。また、最後の項が増加または減少シーケンスの一部であったかどうかを表す、さらに別の変数を追加しましょう。次に、これらすべての値が与えられた場合に可能なシーケンスの数を返す関数を定義します。MKLIF

N = 連続する値の数
M = シーケンスの「実行」数
K = 許可される最大値
L = 隣接するシーケンス項間の最大差
I = 最終項が増加しているか減少しているか
a n = シーケンスの最後の用語
F K,L (N,M,I,a n ) = これらすべての値が与えられた場合の可能なシーケンスの数

を計算する方法があれば、a n (1 から K まで)のFすべての可能な値を合計して、問題の答えを得ることができます。 I

I = 「増加する」と仮定しましょう。F K,L (N,M,"increasing",a n )を の「小さい」値で表現したいFので、 の値を再帰的に計算Fして最終値を得ることができます。これを行うには、 a n-1Fのすべての可能な値の値を合計します。つまり、基本的に、 はnで終わる可能性のある長さの有効なシーケンスの数に等しいと言い、それぞれにnを追加することを想像します。FN-1

a nは増加するシーケンス(I = "increasing")の一部であることがわかっているため、a n-1 < a n (すぐに他のケースに進みます)であることがわかります。また、n-1 は n-1の範囲L内になければならないこともわかっています。したがって、max(1, a n - L) <= a n-1 < a nです。

前項a n-1が増加しているか減少しているかに応じて、次の 2 つのケースを考慮する必要があります。

  1. n-1が増加していました。その後、まだ増加しているので、F関心のある値は
    F K,L (N-1,M,"increasing",a n-1 )です。
  2. a n-1は減少していました。 a nは現在増加しているため、値の「実行」がもう 1 つあります。したがって、F関心のある の値は
    F K,L (N-1,M-1,"decreising",a n-1 )です。

F K,L (N,M,"increasing",a n )の値を取得するために、a n-1のすべての可能な値についてこれらすべてのケースを合計します。同様の方法でF K,L (N,M,"decreising",a n )を見つけることができますが、 a n-1をa n < a n-1 <= min(K, a n +L)に制限するだけです。 、ケース #2 ではなくケース # 1 から 1 を引きます。M

最後に、基本ケースを示します。 F K,L (N,M,I,a n ): M < 1 または M > N の場合は 0。N = 1 の場合は 1。

次に、上で述べたように、 F K,L (N,M,I,a n ) の と a n のすべての値を合計して、元の問題に対する答えIを取得します。実行時の複雑さはO(KMN)

于 2012-03-14T18:26:11.990 に答える
0

問題を次のように分解します。実行は増加と減少を交互に繰り返す必要があるため、重要な数値は方向が変わる場所です。上記の例では、重要な番号は次の1 - 7 - 2 - 4 - 2ようにマークされています。

(1,2,3,4,7,6,5,2,3,4,1,2)
 x       x     x   x x x

これらの転換点の位置と値をすでに与えているとします。

(1,7,2,4,1,2)

次に、数字の間にパディングする方法の数を数えたいと思います。これは、およびからの制約を既に使用してそのスケルトンを作成しているため、Nおよびのみに依存します。ここでのルールは、欠落している数字は指定された数字の間で単調であり、 を超えてジャンプしないことです。これは簡単な数え方の問題です (詳細は後述)。LKML

K次に、とのみに依存するスケルトンの数をM数えます (それらを埋めるためのカウントは、 と に基づいて 0 になる場合がありますN) L。これらについて私たちは何を知っていますか？ギャップがなければ、これはとM+1の間の値を持つ長さの交互のシーケンス (上下上下) でなければなりません。繰り返しますが、これはよく研究されており、数えるのは難しくありません。1K

このアプローチについて私が唯一ためらっているのは、これら 2 つのカウントを組み合わせる簡単な方法がないため、きれいな式が得られないことです。ただし、ソリューションを徹底的に列挙するよりも大きな改善であり、おそらくこのアイデアをさらに改善して、閉じた、またはきれいに再帰的な式を与えることができます。

于 2012-03-14T18:54:07.937 に答える
0

ここにいくつかのヒントがあります：

投稿タグは、これが電話インタビューであったことを示唆しているようです。つまり、オイラー数について知っている必要があります。より具体的には、合計 M の昇順と降順の実行を含む N の順列の数は、次のようにも記述される 2*A(N,M/2-1) によって与えられます。

2*  /     N   \
    \ M/2 - 1 /

これは、次の結果の 2 倍として再帰的に解くことができます。

let x = M/2-1; then
A(n,x)=(n-x)*A(n-1,x-1)+(x+1)*A(n-1,x)

さらに 2 つの制限 k と L は、置換サイクルの形式を制御するためのものです。たとえば、L=3 の場合、サイクル [1,2,9] では 9 が大きすぎるため、順列 {9,1,3,6,2} は許可されません。

あなたの履歴書は、おそらくあなたを組み合わせ論の専門家として描いています。つまり、単に学校のノートを確認する必要があるということです。とにかく、これがあなたの道に進むことを願っています。

于 2012-03-19T18:16:53.557 に答える