求平方形式为 1_2_3_4_5_6_7_8_9_0 的最小数。其中"_"可以是任何 1 位数字

Question

在我最近的面试中，面试官让我

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.我坚持了下来。

任何人都可以帮助我实现逻辑吗？

Answer 1

好吧，该格式的最小数量是1020304050607080900具有平方根1010101010.10...。 该格式的最大数量是1929394959697989990，其平方根近似。 1389026623.11 .

从下限开始，一直循环到上限。 您使用正则表达式甚至基本的字符串字符匹配，只需检查第一个字符是否为 1，第三个字符是否为 2，依此类推。

另外，我认为一个long就足够了。

编辑：

我只是在我的机器上运行这个，花了大约 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（这是平方数）。 因此，根数为 1389019170 。 另请注意，这是我发现的唯一与模式匹配的数字，而不仅仅是最小值。

Answer 2

一个简单但可能效率不高的解决方案是使用 BigInteger ，并迭代数字（从下到上），直到找到n.multiply(n).toString()与模式匹配n。

在

对生成的平方数进行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()

当且仅当myString与模式匹配时，matches()将返回 true，当且仅

当<小时 />

编辑：

使用 @The111 建议的优化来提高性能，这个想法仍然存在 - 迭代并检查结果是否与模式匹配。