1

最近のインタビューで、インタビュアーは私にこう尋ねまし
write a Java program to find the least number whose square is of form 1_2_3_4_5_6_7_8_9_0. Where "_" could be any 1 digit number.
た。

実装するロジックを手伝ってくれる人はいますか?

4

2 に答える 2

6

さて、そのフォーマットの最小数は1020304050607080900平方根を持つもの1010101010.10...です。そして、その形式の最大数は、1929394959697989990平方根が約 1 です。1389026623.11.

下限から開始し、上限まで繰り返します。正規表現または初歩的な文字列の文字マッチングを使用して、最初の文字が 1 であること、3 番目の文字が 2 であることを確認するだけです。

longまた、これにはaで十分だと思います。

編集：

これを自分のマシンで実行したところ、約2分かかりました。私は正規表現が苦手なので、原始的なスタイルにしました。

public static void main(String[] args) {
    for (long l = 1010101010; l < 1389026623; l++) {
        long squared = l * l;
        String s = Long.toString(squared);
        if (s.charAt(0) != '1') continue;
        if (s.charAt(2) != '2') continue;
        if (s.charAt(4) != '3') continue;
        if (s.charAt(6) != '4') continue;
        if (s.charAt(8) != '5') continue;
        if (s.charAt(10) != '6') continue;
        if (s.charAt(12) != '7') continue;
        if (s.charAt(14) != '8') continue;
        if (s.charAt(16) != '9') continue;
        if (s.charAt(18) != '0') continue;
        System.out.println(s);
    }
}

結果は1929374254627488900（これは2乗された数です）でした。したがって、ルート番号は1389019170です。また、これはパターンに一致することがわかった唯一の数値であり、最小値だけではないことに注意してください。

于 2012-12-09T00:51:37.113 に答える
2

単純ですが、おそらく効率的ではない解決策は、を使用し、パターンに一致するものBigIntegerが見つかるまで数値を（下から上に）繰り返すことです。nn.multiply(n).toString()

toString()結果の平方数を処理した後、パターンが一致するかどうかを正規表現で簡単に確認できます。

正規表現：

Matcher m = Pattern.compile(
      "1[0-9]2[0-9]3[0-9]4[0-9]5[0-9]6[0-9]7[0-9]8[0-9]9[0-9]0").matcher("");

そして、次のコマンドで呼び出します。

m.reset(myString);
m.matches()

パターンに一致するmatches()場合にのみtrueを返しますmyString

編集：

@ The111によって提案された最適化を使用してパフォーマンスを向上させても、アイデアは変わりません。繰り返して、結果がパターンと一致するかどうかを確認してください。

于 2012-12-09T00:45:34.077 に答える