写出^ 3 + b ^ 3 = c ^ 3 + d ^ 3的所有解

Question

写出a ^ 3 + b ^ 3 = c ^ 3 + d ^ 3的所有解,其中a,b,c,d位于[0,10 ^ 5]之间.

这是一个面试问题,我完全无能为力.

我认为优先队列至少要迭代a和b值.一些提示会很棒,会尝试从那里开始.

Answer 1

使用哈希映射来存储(cube,(a,b)),您可以迭代所有可能的整数对,并在找到所需的多维数据集总和已经在地图中时输出解决方案.

伪代码:

map <- empty hash_map<int,list<pair<int,int>>>
for each a in range(0,10^5):
  for each b in range(a,10^5): //making sure each pair repeats only once
     cube <- a^3 + b^3
     if map.containsKey(cube):
         for each element e in map.get(cube):
            output e.first(), e.last(), a, b //one solution            
     else:
         map.put(cube,new list<pair<int,int>>)
     //for both cases, add the just found pair to the relevant list
     map.get(cube).add(cube,new pair(a,b))  

该解决方案平均为O(n ^ 2)空间⁽¹⁾和O(n ^ 2 + OUTPUT)时间,其中OUTPUT是输出的大小.

编辑:

实际需要的空间O(n^2 logn),其中n是范围(10 ^ 5),因为要表示10^5需要ceil(log_2(10^15)) = 50位的整数.所以,你实际上需要500,000,000,000位(+地图和列表的开销),大约是58.2 GB(+开销).

因为对于大多数机器来说它有点太多了 - 您可能想要考虑将数据存储在磁盘上,或者如果您有64位机器 - 只需将其存储到"内存"中,让操作系统和虚拟内存系统最好地执行此操作.能够.

(1)正如编辑所阐明的,它实际上是O(n^2log(n))空间,但是如果我们将每个整数存储作为O(1)(通常是这种情况),我们得到O(n^2)空间.显然,同样的原则将适用于时间复杂度.

Answer 2

使用优先级队列几乎可以肯定是最简单的解决方案，也是最实用的解决方案，因为它是O（n）存储（如果需要bignums，则带有对数因子）。任何涉及计算所有可能总和并将其放入地图的解决方案都将需要O（n ^ 2）存储，这很快变得不切实际。

我使用优先级队列的未经优化的幼稚实现是O（n ^ 2 log（n））时间。即便如此，使用几兆字节的存储空间，n = 10000花费了不到五秒钟，n = 100000花费了约750秒。当然可以改善。

根据您的评论，基本思想是用一个对（a，a + 1）初始化一个优先级队列，范围为[1，N），然后重复增加最小的第二个值（按立方和） ）元组，直到达到N。如果在任何时候队列中最小的两个元素相等，那么您就有解决方案。（我可以粘贴代码，但您只要求提供提示。）

Answer 3

一个比普通解决方案更快的方法如下：计算 a^3 + b^3 可以具有的所有值，并用它存储 a 和 b 的所有可能值。这是通过循环 a 和 b、将结果 (a^3 + b^3) 存储在二叉树中并具有与每个结果关联的值列表（a 和 b）来完成的。

在此步骤之后，您需要遍历列表，并为每个值选择 a、b、c、d 的每个可能的分配。

我认为这个解决方案需要 O(n^2 log n) 时间和 O(n^2) 空间，但我可能会遗漏一些东西。