0

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

这是来自 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 秒后终止。毫无疑问，太慢或卡住了一些大输入。

4

3 回答 3

5

Edsgar Dijkstra 在他 1976 年的著作The Discipline of Programming中讨论了这个问题。当x从n的整数平方根向下扫描并且y从零向上扫描时，Dijkstra 在一次遍历中找到所有对。考虑返回x和yB(x, y)之间所有合适对的函数，由以下三个递归规则和递归基引导：

  • 如果 x² + y² < n，则 B(x, y) = B(x, y+1)，因为 x ≥ u 没有可能的解 (u, v)，因为这意味着 u² + v² < n。
  • 如果 x² + y² = 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)
()
于 2013-10-12T23:26:20.507 回答
1

我的想法：

  • 生成 0 到 2147483647 之间的所有正方形
  • 对于每个 X：
    • 计数 = 0
    • 有 2 个迭代器 - 一个从左边开始，一个从右边开始
    • 如果left + right = X，增加计数，增加左边的迭代器并减少右边的迭代器
    • 如果left + right > X, 减少右边的
    • 如果left + right < X，则增加左一
    • left绕过时停止right

作为一种优化，我们不需要一直从右边开始，我们可以对起始位置进行二分搜索。

测试代码：

private static int binarySearch(long[] a, long key)
{
    int low = 0;
    int high = a.length - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        long midVal = a[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid;
    }
    return Math.min(low, a.length-1);
}

public static void main(String[] args)
{
  long[] squares = new long[46341]; // ceil(sqrt(2147483647)) = 46341
  long val = 0;
  int pos = 0;
  while (true)
  {
     long square = val*val;
     // sanity check, can also use pos >= squares.length
     if (square > 2147483647l)
        break;
     squares[pos++] = square;
     val++;
  }
  int X = 10;
  int left = 0;
  int right = binarySearch(squares, X);
  int count = 0;
  for (; left <= right; )
  {
     //Collections.b
     long l = squares[left] + squares[right];
     if (l == X)
     {
        count++;
        left++;
        right--;
     }
     else if (l > X)
     {
        right--;
     }
     else
     {
        left++;
     }
  }
  System.out.println(count);
}
于 2013-10-12T23:28:48.157 回答
0

我的想法是：

  • 找到我们可以拥有的最大 a 或 b ：int x1 = int(Math.sqrt(x))
  • 列出数组中从 0 到 x1 的所有正方形long[] squares = new long[50000];
  • 现在这个循环：

int right = binarySearch(squares, math.sqrt(x1));

int count = 0;

for(int i = 0 ; i < right; i++){

   if(Math.sqrt(x-squares[i]) == int(Math.sqrt(x-squares[i]))){

      count++;

   } else if(int(Math.sqrt(x-squares[i])) < squares[i]) {

      break;

   }

}

System.out.println(x);

所以每次我们检查 squares 数组中的元素与 X 之间的差是否是完美正方形时，

现在这只是我的想法，所以请，当你发表评论时，请善待！！

于 2013-10-13T00:38:42.510 回答