3

指定された範囲内に数値の順列が存在するかどうかを確認する必要があります。はいまたはいいえを返すだけです。

例: Number = 122、およびRange = [200, 250]. Yes範囲内に 221 が存在するため、答えは になります。

PS:

  1. 私が手にしている問題では、検索される番号には2つの異なる数字しかありません（1と2のみが含まれます、例：1112221121）。
  2. これは宿題の質問ではありません。インタビューで聞かれました。
  3. 私が提案したアプローチは、指定された数のすべての順列を見つけてチェックすることでした。または、範囲をループして、数値の順列が見つかるかどうかを確認します。
4

5 に答える 5

4

すべての順列をチェックすることは、費用がかかりすぎて不要です。

まず、それらを数字ではなく文字列として見る必要があります。

各桁の位置を個別の変数と見なします。

各変数が保持できる可能な数字のセットが範囲によってどのように制限されるかを検討してください。各桁/変数のペアは、（a）常に有効（b）常に無効です。または（c）その有効性は条件付きで他の特定の変数に依存します。

次に、これらの依存関係と独立性をグラフとしてモデル化します。ケース（c）はまれであるため、O（10N）= O（N）に比例する時間で検索するのは簡単です。

于 2012-06-03T09:28:21.410 に答える
2

数値には、ここで役立つと思われる優れたプロパティがあります。

値 KXXXXの特定の数値aについて 、K が指定されている場合、K0000 <= a < K9999 と推測できます。

このプロパティを使用して、範囲内にある順列の構築を試みることができます。

あなたの例を見てみましょう：

範囲 = [200, 250]

数 = 122

まず、最初の数は 2 でなければならないことを定義できます。2 が 2 つあるので、これまでのところ問題ありません。

2 番目の数値は 0 から 5 の間でなければなりません。1 と 2 の 2 つの候補があります。それでも悪くありません。最初の値 1 を確認しましょう。

ここでは任意の数を使用できますが、まだ未使用の 2 があります。順列 (212) が見つかったので、答えはYesです。

値 1 との矛盾が見つかった場合は、後戻りして値 2 などを試す必要があります。

有効な解がない場合は、Noを返します。

このアルゴリズムは、バックトラッキングを使用して実装でき、各位置でテストする値が 2 つしかないため、非常に効率的です。このアルゴリズムの複雑さは 2^l で、l は要素の数です。

于 2012-06-03T09:44:18.193 に答える
0

与えられた範囲が ABC と DEF (各文字は数字) であるとします。

Algorithm permutationExists(range_start, range_end, range_index, nos1, nos2)

     if (nos1>0 AND range_start[range_index] < 1 < range_end[range_index] and
          permutationExists(range_start, range_end, range_index+1, nos1-1, nos2))
               return true
     elif (nos2>0 AND range_start[range_index] < 2 < range_end[range_index] and
          permutationExists(range_start, range_end, range_index+1, nos1, nos2-1))
               return true
     else
               return false

すべての数字が一連の数字であると想定しています。指定された数値は として表され{numberOf1s, numberOf2s}ます。数字 (最初の 1、次に 2) を範囲内に収めようとしていますが、そうでない場合はプロシージャが false を返します。

PS: 私は本当に間違っているかもしれません。この種のことが機能するかどうかはわかりません。あまり考えていませんでした、本当に..

アップデート

アルゴリズムの表現方法が間違っています。その中で行う必要があるいくつかの変更があります。これは動作するコードです (私のテストケースのほとんどで動作しました): http://ideone.com/1aOa4

于 2012-06-03T09:54:11.497 に答える
0

実際には、考えられる順列のうち最大 2 つをチェックするだけで済みます。

入力数値に数字 X と Y のみが含まれており、X<Y であるとします。あなたの例では、X=1 と Y=2 です。 桁が足りなくなったという特殊なケースはすべて無視します。

フェーズ 1: 共通プレフィックスを処理します。

A を範囲の下限の最初の桁とし、B を範囲の上限の最初の桁とする。A<B の場合、フェーズ 1 は終了し、フェーズ 2 に進みます。

それ以外の場合は、A=B です。X=A=B の場合、順列の最初の桁として X を使用し、次の桁でフェーズ 1 を繰り返します。Y=A=B の場合、順列の最初の桁として Y を使用し、次の桁でフェーズ 1 を繰り返します。

X も Y も A と B に等しくない場合は、停止します。答えはノーだ。

フェーズ 2: 共通プレフィックスで完了。

この時点で、A<B です。A<X<B の場合、順列の最初の桁として X を使用し、残りの桁を必要に応じて入力します。答えはイエスです。(A<Y<B の場合も同様です。)

それ以外の場合は、次の 4 つのケースを確認してください。実際の作業が必要になるのは、多くても 2 つのケースです。

  • A=X の場合、順列の最初の桁として X を使用してみてください。その後にすべての Y が続き、その後に残りの X が続きます。つまり、順列の残りをできるだけ大きくします。この順列が範囲内にある場合、答えはイエスです。 この順列が範囲内にない場合、X で始まる順列は成功しません。
  • B=X の場合、順列の最初の桁として X を使用し、その後に残りの X を使用し、その後にすべての Y を使用してみてください。つまり、順列の残りをできるだけ小さくします。この順列が範囲内にある場合、答えはイエスです。 この順列が範囲内にない場合、X で始まる順列は成功しません。
  • A=Y または B=Y の場合も同様です。

これら 4 つのケースのいずれも成功しない場合、答えは No です。X ケースの最大 1 つと Y ケースの最大 1 つが一致することに注意してください。

このソリューションでは、入力数値と範囲内の 2 つの数値がすべて同じ桁数であると想定しています。少し余分な作業を行うことで、桁数が異なる場合にもアプローチを拡張できます。

于 2012-06-03T15:02:35.817 に答える
0

ある種の二分探索を実装してみることができます:

あなたの数に6つの1と4つの2がある場合、最初に間隔があります

[1111112222; 2222111111]

範囲がこの間隔と重ならない場合は、終了です。この間隔を真ん中で分割すると、次のようになります。

(1111112222 + 222211111) / 2

次に、分割点よりも小さいそれぞれの数の 1 と 2 からなる最大の数を見つけます。(おそらく、このステップは、1 と 2 に基づいて何らかの効率的な方法で分割を直接計算するか、1 と 2 を 2 進数の 0 と 1 として解釈することによって改善される可能性があります。2 つの数値の幾何平均を取ることも考えられます。候補が左右により均等に分散される可能性があるためです。)

[編集: 私はそれを得たと思います: 境界が pq と pr の形式を持っていると仮定します (つまり、p は一般的な接頭辞です)。次に、q と ra 対称文字列 s から、文字列の先頭と末尾に 1 を使用して構築します。真ん中に 2 があり、分割ポイントとして ps を取ります (したがって、1111112222 と 1122221111 から、111122222211 を構築します。プレフィックスは p=11 です)。

この数値が範囲内に含まれていれば完了です。

そうでない場合は、範囲が上か下かを調べ、[古い下限;分割]または[分割;古い上限]で繰り返します。

于 2012-06-03T09:39:30.387 に答える