3

我刚刚接受了关于 codility 的编码面试

我被要求实施以下内容，但我无法在 20 分钟内完成，现在我来这里是为了从这个社区获得想法

编写一个函数public int whole_cubes_count ( int A,int B )，它应该返回范围内的整个立方体

例如，如果 A=8 和 B=65，范围内所有可能的立方体是 2^3 =8 、 3^3 =27 和 4^3=64，所以函数应该返回计数 3

我无法弄清楚如何将一个数字识别为整个立方体。我该如何解决这个问题？

A 和 B 的范围可以从 [-20000 到 20000]

这是我尝试过的

import java.util.Scanner;
class Solution1 {
  public int whole_cubes_count ( int A,int B ) {
      int count =0;

    while(A<=B)
    {
        double v = Math.pow(A, 1 / 3); // << What goes here?
        System.out.println(v);
        if (v<=B)
            {
            count=count+1;
            }
        A =A +1;
    }
    return count ;
  }

  public static void main(String[] args) 
  {
    System.out.println("Enter 1st Number");
    Scanner scan = new Scanner(System.in);
    int s1 = scan.nextInt();
    System.out.println("Enter 2nd Number");
    //Scanner scan = new Scanner(System.in);
    int s2 = scan.nextInt();
    Solution1 n = new Solution1();
     System.out.println(n.whole_cubes_count (s1,s2));
  }
}
4

5 回答 5

7

对于正立方体：

i = 1
while i^3 < max
    ++i

对于负立方体也是如此，但在比较中具有绝对值。

为了使这更普遍，您需要找到iwhere的值，i^3 >= min如果min和max都是正数。如果两者都为负min，则类似的解决方案有效。max

于 2012-10-10T02:51:35.070 回答
7

肮脏和肮脏，这就是我所说的。

如果你只有 20 分钟，那么他们不应该期望超级优化的代码。所以不要尝试。发挥系统的限制条件，即只有 +20,000 到 -20,000 作为范围。您知道立方体值必须在 27 以内，因为 27 * 27 * 27 = 19683。

public int whole_cubes_count(int a, int b) {
    int count = 0;
    int cube;
    for (int x = -27; x <= 27; x++) {
        cube = x * x * x;
        if ((cube >= a) && (cube <= b))
            count++;
    }
    return count;
}
于 2012-10-10T02:52:20.267 回答
1

好吧，它可以用 O(1) 复杂度计算，我们需要找到适合该范围的最大立方体和最小的立方体。所有介于两者之间的人显然也会在里面。

def n_cubes(A, B):
    a_cr = int(math.ceil(cube_root(A)))
    b_cr = int(math.floor(cube_root(B)))

    if b_cr >= a_cr:
        return b_cr - a_cr + 1
    return 0

只需确保您的 cube_root 返回实际立方体的整数即可。完整的解决方案作为要点https://gist.github.com/tymofij/9035744

于 2014-02-16T20:46:24.283 回答
0 
int countNoOfCubes(int a, int b) {
        int count = 0;
        for (int startsCube = (int) Math.ceil(Math.cbrt(a)); Math.pow(
                startsCube, 3.0) <= b; startsCube++) {
            count++;
        }
        return count;
    }
于 2013-11-04T11:47:54.253 回答
0

@Tim 建议的解决方案比 @Erick 提供的解决方案更快，尤其是当 A...B 范围增加时。让我在这里引用 github 的基础：“人们可以注意到 x³ > y³ 对于任何 x > y。（这称为单调函数）因此对于位于 ∛A ≤ x ≤ ∛B 中的任何 x，立方体将适合：A ≤ x³ ≤ B

因此，要获得位于 A..B 内的立方体数，您可以简单地计算 ∛A 和 ∛B 之间的整数个数。两个数字之间的整数个数就是它们的差。”

这似乎完全正确，不是吗？它适用于任何电源，不仅适用于立方体。这是我的用于 java 的 cube_root 方法的端口：

/*
 * make sure your cube_root returns integers for actual cubes
 */
static double cubeRoot(int x) {
    //negative number cannot be raised to a fractional power
    double res = Math.copySign(Math.pow(Math.abs(x), (1.0d/3)) , x);
    long rounded_res = symmetricRound(res);
    if (rounded_res * rounded_res * rounded_res == x)
        return rounded_res;
    else
        return res;
}

private static long symmetricRound( double d ) {
    return d < 0 ? - Math.round( -d ) : Math.round( d );
}

我知道 java 中的 Math.cbrt 但是使用 Math.pow 方法很容易将解决方案推广到其他指数。

于 2018-01-26T07:24:23.880 回答