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

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增长时，对于相同的值，getSteps有大量的重复调用。如果让getSteps缓存其每个k的返回值，并在进入昂贵的循环之前调用缓存时查阅缓存，则会大大加快速度

Answer 2

溢出

如果要计算的值为^{，则开始发生错误

您的结果是-2147483648，这是。。。。是的，整数。最大值+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

如果您需要/希望维护该代码，这将是一种变通方法

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

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

---

---

保留插入顺序

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

对于这种情况，两者都是不好的，但具体地说TreeSet就是不好的

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

我等了3个小时（真的），但那件事没有结束。它使你相信你的计算机的处理能力低于90年代中期的计算机

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

---

我的最佳尝试

测试后，最佳性能是使用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;
  }