Java中的双人广场(Facebook黑客杯2011)

Question

所以它工作正常,所需的两个主要变化只是检查x的平方根(还需要将我的检查案例从checkign翻转到余数到检查取幂).另一个变化是使用双倍显然是鲁莽的,因为数字将超过最大双倍.

这是CodeEval的一个挑战,我想Facebook首先提出这个问题.这就是我的大脑立即吐出的东西.它通过所有手动测试案例(例如10-> 1,25-> 2,3-> 0).我还没有看到任何其他解决方案,因为我想先看看我是如何用自己的想法做的.如果我离开基地,这将永远不会奏效,我会很感激有人这么说:P.如果这永远不会奏效,我必须找到一条新的方法,我会花更多的时间来讨论这个问题.

我不会立即看到任何不满足的情况......但这不是问题.我从来都不擅长计算运行时复杂度,但我认为我已经有太多的嵌套了.

我想从右边和左边检查(这在代码中更清楚一点),我会严重减少运行时间.我不确定这是不是就像我想的那样有效,或者其他循环仍然太多......或者两者兼而有之.

有什么想法吗？这是可以挽救的,还是应该废弃它并以新的方式思考？

问题和代码如下.谢谢你看:-)

致谢:这一挑战出现在2011年的Facebook黑客杯中.
双方数是一个整数X,可以表示为两个完美正方形的总和.例如,10是双平方,因为10 = 3 ^ 2 + 1 ^ 2.在给定X的情况下,您在此问题中的任务确定了可以将其写为两个方格的总和的方式.例如,10只能写为3 ^ 2 + 1 ^ 2(我们不计算1 ^ 2 + 3 ^ 2不同).另一方面,25可以写成5 ^ 2 + 0 ^ 2或4 ^ 2 + 3 ^ 2.
注意:不要尝试暴力攻击.不起作用.以下约束成立:
0 <= X <= 2147483647
1 <= N <= 100

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;

public class DoubleSquares {
    public static void main(String[] args) throws IOException {
        File file = new File(args[0]);
        BufferedReader in = new BufferedReader(new FileReader(file));
        String line;
        while ((line = in.readLine()) != null) {
            int total = 0;
            String[] lineArray = line.split("\\s");
            if (lineArray.length > 0) {
                double x = (double) Integer.parseInt(lineArray[0]);
                if (x == 0){total++;} //special case if input is 0
                double sLeft = 0.00;  //left boundary to indicate where to stop (so we dont repeat e.g. 4+1 and 1+4)
                for(double sRight = x; sRight > sLeft; sRight--){
                    if (Math.sqrt(sRight) % 1 == 0){//has no remainder then it's a candidate..
                        double needed = x-sRight;
                        if (Math.sqrt(needed) % 1 == 0){//check of solution to what makes sRight == x is a perfect square.
                            total++; //increment if so.
                        }
                        sLeft = needed;
                    }
                }
            }
            System.out.println(total);
        }
    }
}

为了更清楚一点,这似乎工作得很好,但是当我提交到CodeEval自动分级器时,它会在运行10秒后终止.毫无疑问,太慢或陷入一些大输入.

Answer 1

Edsgar Dijkstra在其1976年出版的"编程学科"一书中讨论了这个问题.Dijkstra在一次通过中找到所有对,因为x从n的整数平方根向下扫过,y从零向上扫过.考虑B(x, y)返回x和y之间所有合适对的函数,由以下三个递归规则和一个递归基数引导:

• 如果x²+y²<n,则B(x,y)= B(x,y + 1),因为没有可能的解(u,v)x≥u,因为这意味着u²+v²<n.
• 如果x²+ y2 = n,那么对(x,y)是解,B(x,y)=(x,y)⋃B(x-1,y + 1),并且扫描继续.
• 如果x²+y²> n,则B(x,y)= B(x-1,y),因为没有任何x的可能解.
• 最后,如果x <y,则B(x,y)为空集,并且递归停止.

以下是我在博客中使用Scheme编写解决方案的方法; 我会留给你翻译成Java:

(define (squares n)
  (let loop ((x (isqrt n)) (y 0) (zs '()))
    (cond ((< x y) zs)
          ((< (+ (* x x) (* y y)) n) (loop x (+ y 1) zs))
          ((< n (+ (* x x) (* y y))) (loop (- x 1) y zs))
          (else (loop (- x 1) (+ y 1) (cons (list x y) zs))))))

以下是一些示例,您可能会发现它们可用作测试用例:

> (squares 50)
((5 5) (7 1))
> (squares 48612265)
((5008 4851) (5139 4712) (5179 4668) (5243 4596) (5432 4371)
 (5613 4136) (5656 4077) (5691 4028) (5832 3821) (5907 3704)
 (6048 3469) (6124 3333) (6213 3164) (6259 3072) (6384 2803)
 (6404 2757) (6413 2736) (6556 2373) (6576 2317) (6637 2136)
 (6651 2092) (6756 1723) (6772 1659) (6789 1588) (6853 1284)
 (6899 1008) (6917 876) (6944 627) (6948 581) (6952 531)
 (6971 132) (6972 59))
> (squares 999)
()