algorithm - 数字が与えられたら、それが素晴らしいかどうかを見つけてください

Question

これは、次のようなプログラミング パズルです。

例 : 263 (2, 6, 3, 2*6 = 12, 6*3 = 18) は見事です。

しかし、236 (2, 3, 6 , 2*3 = 6 , 3*6 = 18) は見事ではありません。

サブシーケンスではなく、部分文字列のみを取ります。

積の計算が繰り返されるため、ここで動的計画法を適用できるのではないかと考えていました。他にどのような解決策がありますか? (これは宿題の質問ではありません。)

Answer 1

動的計画法を使用してこれを解決する 1 つの方法を次に示します。

入力として数値d ₀ d ₁ ... d _Nがあるとします。

アイデアは、セル ( i , j ) が積d _i · d _i+1 · ... · d _jを格納するテーブルを作成することです。( i , j )のセルは( i -1, j )の数値にd _iを掛けることで計算できるため、これは効率的に実行できます。

i (開始インデックス) はj (終了インデックス)以下でなければならないため、テーブルの左下の三角形に注目します。

テーブルを生成した後、重複するエントリをチェックします。

入力 2673 の具体的なソリューション例を次に示します。

1. 次元が 4 × 4の行列Mを割り当てます。

   

2. 対角線M _i,iをd _iで埋めることから始めます。

   

3. 次に、行ごとに進み、M _i,jをd _i · M _{i-1,jで埋めます。}

   

4. 結果は次のようになります

   

5. 重複をチェックするために、製品 (2、12、6、84、42、7、252、126、21、3) を収集し、それらを並べ替え (2、3、6、7、12、21、42、84、 126, 252) をループして、2 つの連続する数値が等しいかどうかを確認します。そうであれば false を返し、そうでなければ true を返します。

Java コードの場合:

これが実用的な DP ソリューション O(n ² ) です。

public static boolean isColorful(int num) {

    // Some initialization
    String str = "" + num;
    int[] digits = new int[str.length()];
    for (int i = 0; i < str.length(); i++)
        digits[i] = str.charAt(i) - '0';
    int[][] dpmatrix = new int[str.length()][str.length()];

    // Fill in diagonal: O(N)
    for (int i = 0; i < digits.length; i++)
        dpmatrix[i][i] = digits[i];

    // Fill in lower left triangle: O(N^2)
    for (int i = 0; i < str.length(); i++)
        for (int j = 0; j < i; j++)
            dpmatrix[i][j] = digits[i] * dpmatrix[i-1][j];

    // Check for dups: O(N^2)
    int[] nums = new int[digits.length * (digits.length+1) / 2];
    for (int i = 0, j = 0; i < digits.length; i++, j += i)
        System.arraycopy(dpmatrix[i], 0, nums, j, i+1);

    Arrays.sort(nums);

    for (int i = 0; i < nums.length - 1; i++)
        if (nums[i] == nums[i+1])
            return false;

    return true;
}

DP に関心のある読者には、ここでやや似た質問/回答をお勧めします。

• 文字列内のサブシーケンスの出現回数を見つける

Answer 2

動的計画法のソリューションは実際には必要ありません。桁数の多い鮮やかな数字は存在しないためです(数字が 2 回以上表示される場合、その数字は華麗ではありません)。

これがすべての素晴らしい数字のリストです。全部で 57,281 あります。

このファイルは、動的プログラミングを使用しなくても、PC で生成するのに 1 秒もかかりませんでした :)

Answer 3

n は数値を含む文字列です。

障害状態の前に数字が 8 桁を超えることはできないため、O(1) になります。

function isBrill(n) {
  var set = {};
  set[parseInt(n.charAt(0))] = true;
  for(var i=0; i < n.length - 1; i++) {
    var a = parseInt(n.charAt(i));
    var b = parseInt(n.charAt(i+1));
    if(set[b] === true) { return false; }
    set[b] = true;
    if(set[a * b] === true) { return false; }
    set[a * b] = true;
  }
  return true;
}
isBrill("263"); // true
isBrill("236"); // false

Answer 4

数値を大きな文字列と見なさない場合は、ハッシュが役立ちます。

 int brill(int A) {
    map<long long int,bool> m;
    vector<int> arr(10,0);
    int i=0;
    while(A){
        arr[i++]=A%10;
        A/=10;
    }

    for(int j=0;j<i;j++){

        long long int temp=1;

        for(int k=j;k>=0;k--){
            temp*=arr[k];

            if(m.find(temp)!=m.end()){
                return 0;
            }
            else{
                m[temp]=true;
            }
        }
    }
    return 1;

}