java - 为什么我的递归 Java 方法中的字段会发生变化？

Question

我已经学习 Java 大约一个月了，通过阅读本网站上其他人的问题(和答案)，我学到了很多东西。我认为以前没有人问过这个问题(但如果有的话，我将不胜感激……)

在下面的代码中，几乎所有未缩进的内容都是错误检查打印输出，因此代码比看起来要短得多。该代码是我尝试使用递归来列出 numBalls 的所有方式。球可以放置在 numBins垃圾箱。

主要问题:该方法适用于 numBins < 3. 一旦numBins设置为 3，即 endList字段(在递归调用中)有超过 1 个“行”，一旦 j 在下面的循环中达到 1，indexList字段发生变化。例如，calling testList = distributeBallsInBins(1,3,"");在 main 方法中(按照配置)，导致 indexList 第二行发生变化从 {0 1 0} 到 {0 0 1} (如输出所示)，但是当我所做的一切都移到下一个 j (即从 j=0 到 j= 1)

第二个问题:我已经替换了所有Integer[]出现 int[]似乎没有什么区别。应该有吗？我想我需要更多地了解原始类型和引用类型之间的区别，但我并不真正理解这里的区别。

预先感谢您，迈克

import java.util.*;

public class testRecursion
{
     public static List<Integer[]> distributeBallsInBins(int numBalls, int numBins, String tmpTxt)
    {
        if (numBins==1)
        {
            List<Integer[]> lastList = new ArrayList<Integer[]>();
            lastList.add((new Integer[] {numBalls}));
            return lastList;
        }
        else if (numBalls==0)
        {
            List<Integer[]> lastList = new ArrayList<Integer[]>();
            Integer[] tmpNum = new Integer[numBins];
            for (int k=0; k<numBins; k++)
                tmpNum[k] = 0;
            lastList.add(tmpNum);
            return lastList;
        }
        else
        {
            List<Integer[]> indexList = new ArrayList<Integer[]>();
            for (int i=numBalls; i>=0; i--)
            {
                Integer[] newLine = new Integer[numBins];
                newLine[0] = i;
                List<Integer[]> endList = distributeBallsInBins((numBalls-i), (numBins-1), (tmpTxt + "    "));
                for (int j=0; j<endList.size(); j++)
                {
                    Integer[] newLineEnd = endList.get(j);
                    for (int k=0; k<numBins-1; k++)
                        newLine[k+1] = newLineEnd[k]; 
                    indexList.add(newLine);
                }
            }
        return indexList;
        }
    }

    public static void main(String[] args)
    {
        List<Integer[]> testList = distributeBallsInBins(1,3,"");
    }
}

Answer 1

您的问题是，您总是修改相同的数组并将其插入到结果列表中。由于 Java 处理每个引用的所有对象，因此您最终会得到一个一遍又一遍地包含相同数组的列表。

因此，您需要在将数组添加到列表之前克隆该数组:

indexList.add(newLine.clone());

或者在每次迭代 j-loop 时创建新的 newLine 数组:

for (int j = 0; j < endList.size(); j++) {
    Integer[] newLine = new Integer[numBins];
    newLine[0] = i;
    Integer[] newLineEnd = endList.get(j);
    for (int k = 0; k < numBins - 1; k++)
        newLine[k + 1] = newLineEnd[k];
    indexList.add(newLine);
} // next j

关于对象与基元:更改为 int[] 没有帮助，因为 array 本身仍然是一个 Object ，因此通过引用传递.