为什么我的算法返回stackoverflow异常？

Question

我必须做一个算法，用随机（0到2）数字填充二维数组，唯一的条件是我可以在水平和垂直方向上有相同的数字3次或更多次。 例如

[0,0,1,2,1 
0,1,2,1,2 
1,2,0,1,0] 

是确定

[0,0,0,2,1 
0,1,2,1,2 
1,2,0,1,0] 

或

[0,0,1,2,1 
0,1,1,1,2 
1,2,1,1,0] 

是错误的。

因此，这里是我的算法：

public class CandyHelper { 

    private final int minimumChainLength = 3; 
    private final int searchChainSize = 3; 

    public Candy[][] randomInit(int rowCount, int columnCount) { 
     Candy[][] map = new Candy[rowCount][columnCount]; 
     for (int row = 0; row < rowCount; ++row) { 
      for (int column = 0; column < columnCount; ++column) { 
       // Fill square with random candy. 
       Random rand = new Random(); 
       int value = rand.nextInt(3); 
       Candy candy = new Candy(); 
       candy.setType(value); 
       map[row][column] = candy; 
      } 
     } 

     if (findHint(map)) { 
      //System.out.println("Winning conditions"); 
      map = null; 
      map = randomInit(rowCount, columnCount);   
     } else { 
      System.out.println("no wining"); 
     } 

     return map; 
    } 

    // Function which searches for match of at least `MinimumChainLength`. 
    private boolean findHint(Candy[][] map) { 
     int rowCount = map.length; 
     int columnCount = map.length; 

     List<Candy> hintMove = new ArrayList<Candy>(); 

     // Search rows. 
     for (int row = 0; row < rowCount; ++row) { 
      // Search for chain. 
      for (int chainStart = 0; chainStart < columnCount - searchChainSize; ++chainStart) { 
       // Add initial cell in chain. 
       hintMove.clear(); 
       hintMove.add(map[row][chainStart]); 
       for (int nextInChain = chainStart + 1; nextInChain < columnCount; ++nextInChain) { 
        if (map[row][nextInChain].getType() == hintMove.get(0).getType()) { 
         hintMove.add(map[row][nextInChain]); 
        } else { 
         break; 
        } 
       }   
       // Was a chain found? 
       if (hintMove.size() >= minimumChainLength) 
        return true; 
      } 
     } 

     // Search columns. 
     for (int column = 0; column < columnCount; ++column) { 
      // Search for chain. 
      for (int chainStart = 0; chainStart < rowCount - searchChainSize; ++chainStart) { 
       // Add initial cell in chain. 
       hintMove.clear(); 
       hintMove.add(map[chainStart][column]); 
       for (int nextInChain = chainStart + 1; nextInChain < rowCount; ++nextInChain) { 
        if (map[nextInChain][column].getType() == hintMove.get(0).getType()) { 
         hintMove.add(map[nextInChain][column]); 
        } else { 
         break; 
        } 
       } 
       // Was a chain found? 
       if (hintMove.size() >= minimumChainLength) 
        return true; 
      } 
     } 

     // No chain was found, so clear hint. 
     hintMove.clear(); 
     return false;  
    } 

} 

和我的POJO：

public class Candy { 
    private int type; 

    public int getType() { 
     return type; 
    } 

    public void setType(int type) { 
     this.type = type; 
    } 

    @Override 
    public String toString() { 
     return "Candy{" + "type=" + type + '}'; 
    } 

} 

当我从10×10阵列我开始越来越堆栈溢出错误开始。 我应该怎么做才能纠正它们？

在此先感谢。

Answer 1

你的问题是这一行：

map = randomInit(rowCount, columnCount); 

基本上每次findHint返回true，你要递归调用randomInit。这意味着FindHint返回true的概率越大，堆栈溢出的机会就越高。在你的情况下，你的网格越大，FindHint将返回true的概率就越高，我猜在10号的时候，几乎肯定会在一个堆栈溢出中结束。

我都诚实我不确定为什么你在这里再次调用randomInit而不是仅仅返回地图？

Answer 2

如果没有运行您的代码，我会猜想它与randomInit()自己调用，如果findHint()为真。我的代码findHint()的代码没有问题（除了一些性能调整 - 例如，你不需要构建一个匹配列表来计算它的数量），但事实上你可能只会遇到这个问题在10x10网格是告诉。任何只有三种类型的10x10个对象网格很可能会有三个 - 很可能足以导致您的自我调用足够多次以使您的堆栈溢出。

我不是100％确定要randomInit()要做什么。如果你想让它继续生成一个随机网格，直到没有N组，那么我会建议把网格生成代码放在一个单独的方法中（称为generate()），然后让randomInit()在一个while循环中调用它：

boolean setFound; 
do { 
    map = generate(rowCount, columnCount); 
    setFound = findHint(map); 
} while (setFound);