雖然循環邏輯缺陷

問題如下：給定兩個整數n和k，返回1 ... n中所有可能的k個數的組合。雖然循環邏輯缺陷

例如，如果n = 4且k = 2，一個解決方案是：

[ 
    [2,4], 
    [3,4], 
    [2,3], 
    [1,2], 
    [1,3], 
    [1,4] 
]

我的解決辦法是：

public List<List<Integer>> combine(int n, int k) { 
    Deque<List<Integer>> queue = new LinkedList<List<Integer>>(); 
    List<List<Integer>> result = new LinkedList<List<Integer>>(); 

    for (int i = 1; i <= n; i++) { 
     List<Integer> list = new ArrayList<Integer>(); 
     list.add(i); 
     queue.add(list); 
    } 

    while (!queue.isEmpty()) { 
     List<Integer> list = queue.pollFirst(); 
     if (list.size() == k) 
      result.add(list); 
     else { 
      for (int i = list.get(list.size() - 1) + 1; i <= n; i++) { 
       list.add(i); 
       queue.addLast(list); 
       list.remove(list.size() - 1); 
      } 
     } 
    } 
    return result; 
}

然而while循環進入一個無限循環。我不知道這個邏輯有什麼問題。我追蹤了它幾次，但仍然無法找到此代碼中的邏輯缺陷。

來源

2015-06-22 Bill Cheng

難道是因爲你從來沒有隊列（queue.isEmpty（）！）變空了？ – kosa

我用n = 2和k = 2來追蹤它，並且據推測隊列應該是空的。但是當我編譯它時，它仍然會陷入無限循環。 –

看着第二個'for'循環的主體，看起來你確實有一個錯誤的對象引用的概念。或者說：當你添加一些東西到列表中，然後將該列表添加到隊列中，然後再次從列表中移除該元素，那麼隊列中的列表也將沒有該元素，因爲它是同一個對象。當您將其添加到隊列中時，沒有創建該列表的副本。這應該引導您找到解決方案。祝你好運！ :-) – hoijui

您的問題是，你是多次加入同一列表實例的隊列，所以當你寫：

  list.add(i); // suppose that list had 1 element. After adding 1, 
         // it has two elements 
      queue.addLast(list); // here you add the list with 2 elements to 
           // the queue 
      list.remove(list.size() - 1); // here you remove the added element 
              // so the list you just added 
              // to the queue has just 1 element

您添加到隊列列表仍然與原來的許多元素。

你應該將它添加到隊列之前創建一個新的List實例：

  list.add(i); 
      queue.addLast(new ArrayList<Integer>(list)); 
      list.remove(list.size() - 1);

來源

2015-06-22 20:00:27 Eran

謝謝你的回答。一直在調試它一整天，最後... –

以上，而{}總是正確的

來源

2015-06-22 20:04:03 sriharichander

雖然循環邏輯缺陷

回答

相關問題