找出其平方形式为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

嗯，这种格式的最小数目是具有平方根1010101010.10...的1020304050607080900。这种格式的最大数量是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。还要注意，这是我找到的与模式匹配的only编号，而不仅仅是最小值。

Answer 2

一个简单但可能效率不高的解决方案是使用BigInteger，并(从下往上)迭代数字，直到找到n，使n.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()

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

编辑：

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