虽然循环逻辑缺陷

问题如下：给定两个整数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

虽然循环逻辑缺陷

回答

相关问题