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约为平方根。1389026623.11.

从下限开始，并迭代到上限。您使用正则表达式甚至基本的字符串字符匹配，只需检查第一个字符是 1，第三个字符是 2，等等。

另外，我认为 along就足够了。

编辑：

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

于 2012-12-09T00:51:37.113 回答
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()

当且仅当匹配模式matches()时才会返回 truemyString

编辑：

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

于 2012-12-09T00:45:34.077 回答