为什么我在使用最大整数值时会得到荒谬的值？

Question

我有一个问题陈述 - 给定 n，找到总和为 n 的最少完全平方数。

由于某些原因，我正在尝试基于公式 -

的效率最低的蛮力方法

perfectSquaresRequired(n) = (perfectSquaresRequired(n-k) + 1) for all k which is perfect square<=n

我在java中写了一个递归函数来实现它。这里 numSquares 是被调用的函数，getSteps 是实现递归逻辑的函数。

Set<Integer> squares;    
public int numSquares(int n) {
    squares = new HashSet();
    for (int i=1; i*i<=n; i++)
        squares.add(i*i);
    
    return getSteps(n);
}

public int getSteps(int k) {
    if (squares.contains(k))
        return 1;
    int min=Integer.MAX_VALUE, cur;
    for (Integer square : squares) {
        if (square>k)
            break;
        cur = getSteps(k-square) + 1;
        min = Math.min(cur, min);
    }
    return min;
}

问题是我从这段代码中得到了荒谬的值。但是，如果我在语句 int min = Integer.MAX_VALUE 中使用 Integer.MAX_VALUE 以外的任何值，即任何小于 2147483647（甚至 2147483646）的值，我都会得到正确答案。

我学习DSA才一个月。谁能解释为什么会这样？

Answer 1

for (Integer square : squares) {
    if (square>k)
        break;
    ...
}

此循环期望方块从最小到最大迭代。问题是 HashSet 没有可预测的顺序。如果较早遇到大方块，则在考虑所有其他较小方块之前循环中断。

为了确保顺序，您需要使用 SortedSet。切换到 TreeSet 修复程序：

squares = new TreeSet<>();

旁注，我强烈建议您添加更多 memoization。当 n 增长时，有 lot 重复调用 getSteps 以获得相同的值。如果你 getSteps 为每个 k 缓存其 return 值并在它进入昂贵的循环之前调用它时查询缓存，你将获得显着的加速。

Answer 2

溢出！

如果要计算的值是 >=17，则错误开始发生。

你的结果是 `-2147483648` 这是....是的，Integer.MAX_VALUE+1

中的递归操作数t+1:

 for (Integer square : squares) {
      if (square>k)
           break;
    cur = getSteps(k-square) + 1;
    min = Math.min(cur, min);
 }
return min;

cur如操作号t溢出，返回min，值为Integer.MAX_VALUE。

这使得

cur = Integer.MAX_VALUE + 1 // --> -2147483648

从那里，Math.min(cur,min) 找到了它的最终值：-2147483648

这只会发生一次，这就是为什么如果您将 Integer.MAX_VALUE-1 设置为 min，不会失败，因为 它不会溢出 （也不会被选为最小值).

廉价的解决方法：long

如果您need/wish维护该代码，这将是一种解决方法。

不，只是不要这样做。正如约翰在下面评论的那样，这只会使失败变得不那么明显

从一开始就是正确的解决方案

保留插入顺序

检索 squares 时必须遵守插入顺序。 这是这里的关键，正如 John 正确指出的那样 。有两种类型的集合符合这一点：LinkedHashSet 和 TreeSet.

对于这种情况，两者都是糟糕，但具体来说 TreeSet 只是糟糕。

对于 TreeSet、add、contains 和 remove 表示 ~O(log(N))。这里不开玩笑，只是测试它执行 numSquares(99)。这是一个很小的数字，但我注意到在某些值 (55-60) 之后时间呈指数增长。所以99足以证实这一点。

我等了 3 个小时（真的），但那件事没有完成。它让您相信您的计算机的处理能力低于 90 年代中期的计算机 LCD videoconsoles。

约翰的回答也正确指出了这一点。

我尽力了

经过测试，性能最好的代码是使用 HashSet 和 ArrayList 的混合方法。该机制可以在以下时间恢复：

将元素添加到 ArrayList（它将遵循插入顺序）
调用HashSet.addAll(ArrayList)
HashSet.contains是条件检查
for (Integer square : ArrayList)是循环机制

这是代码：

 Set<Integer> sqSet;  
 List<Integer> sqArr;
 //...
 public int numSquares(int n)
 {
     sqSet = new HashSet<>((n/10)+2);
     sqArr = new ArrayList<>((n/10)+2);  //avoids grow()

     for (int i=1; i*i<=n; i++)
         sqArr.add(i*i);
    
     sqSet.addAll(sqArr);
     return getSteps(n);
 }

 public int getSteps(int k) 
 {
    if (sqSet.contains(k))
       return 1;
    int min=Integer.MAX_VALUE;
    int cur;
    for (Integer square : sqArr) 
    { 
       if (square>k)
         break;
       cur = getSteps(k-square) + 1;
       min = Math.min(cur, min);
     }   
     return min;
  }

为什么我在使用最大整数值时会得到荒谬的值？

Why I am getting absurd values on using maximum integer value?

java

recursion

integer-overflow

溢出！

你的结果是 `-2147483648` 这是....是的，Integer.MAX_VALUE+1

从一开始就是正确的解决方案

保留插入顺序

我尽力了

为什么我在使用最大整数值时会得到荒谬的值？

Why I am getting absurd values on using maximum integer value?

java

recursion

integer-overflow

溢出！

你的结果是 -2147483648 这是....是的，Integer.MAX_VALUE+1

从一开始就是正确的解决方案

保留插入顺序

我尽力了

你的结果是 `-2147483648` 这是....是的，Integer.MAX_VALUE+1