爲什麼我的算法返回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);