x******8
发帖数: 48 | 1 给一个List>,打印出所有组合
eg.
{
{a, b},
{c, d, e},
{f, g}
}
打印出来：
{a, c, f}
{a, c, g}
{a, d, f}
{a, d, g}
{a, e, f}
{a, e, g}
{b, c, f}
......
lc原题，letter combinations of a phone number的变种
很容易想到的解法是
先计算前两个list的组合{a, c} {a, d} {a, e} {b, c} {b, d} {b, e}，得到结果再
与第三个list计算，最后打印出来，但这样需要额外的空间保存中间结果
怎么优化空间复杂度，不需要维护中间结果，使空间复杂度为O(1)
即找到一个combination就打印，然后找下一个combination。 | c****8
发帖数: 76 | | c*******e
发帖数: 373 | 3 这不是for循环就搞定了吗？
唯一的特别之处，是循环层数不定，所以没法直接用多层for语句来写，循环计数器变
量个数不定，所以数组来存，然后自己模拟多层for语句
int[] ijkl = new int[list.size()];
把 ijkl[0] 作为最内层循环计数器，ijkl[list.size() - 1]作为最外层循环计数器
- 每次处理，内层循环计数器加1，如果没有超出当前层的元素个数，就输出一次，然
后继续循环
- 如果计数器加1后，过界了，则充值为0，并且把外一层计数器加1，直到不再过界，
则继续循环
- 如果所有计数器都过界了，当然任务完成，退出程序 | a****r
发帖数: 87 | 4 同意chenm8. 就是一个backtracking.
有k个position, and each position can have list[k] 可能。 | c******n
发帖数: 4965 | 5 放水题啊， 该感谢出题的
【在 x******8 的大作中提到】
: 给一个List>,打印出所有组合
: eg.
: {
: {a, b},
: {c, d, e},
: {f, g}
: }
: 打印出来：
: {a, c, f}
: {a, c, g}
| r********7
发帖数: 102 | 6 抛个砖~ 自己写了一个， stack 然后 backtracking。 其实写完感觉stack多此一
举，不想改了。 请大神们无视
public class Solution {
public void printCombo(List> input){
if (input == null || input.size()==0){
return;
}
Stack> stc = new Stack>();
for (int i=0; i
stc.push(input.get(i));
}
List> res = new ArrayList>();
while(!stc.isEmpty()){
List tmp = stc.pop();
if (res.isEmpty()){
for (int j=0;j
List newList = new ArrayList();
newList.add(tmp.get(j));
res.add(newList);
}
}else {
List> res2 = new ArrayList>();
for (List cur : res){
for (int j=0; j
List newList = new ArrayList();
newList.addAll(cur);
newList.add(0,tmp.get(j));
res2.add(newList);
}
}
res = res2;
}
}
for (List cur : res){
System.out.println();
for(int tmp : cur){
System.out.print(tmp);
}
}
}
} | n******n
发帖数: 12088 | 7 经典递归题。
【在 c*******e 的大作中提到】
: 这不是for循环就搞定了吗？
: 唯一的特别之处，是循环层数不定，所以没法直接用多层for语句来写，循环计数器变
: 量个数不定，所以数组来存，然后自己模拟多层for语句
: int[] ijkl = new int[list.size()];
: 把 ijkl[0] 作为最内层循环计数器，ijkl[list.size() - 1]作为最外层循环计数器
: - 每次处理，内层循环计数器加1，如果没有超出当前层的元素个数，就输出一次，然
: 后继续循环
: - 如果计数器加1后，过界了，则充值为0，并且把外一层计数器加1，直到不再过界，
: 则继续循环
: - 如果所有计数器都过界了，当然任务完成，退出程序
| n******n
发帖数: 12088 | 8 太罗嗦。白板写不下。
【在 r********7 的大作中提到】
: 抛个砖~ 自己写了一个， stack 然后 backtracking。 其实写完感觉stack多此一
: 举，不想改了。 请大神们无视
: public class Solution {
: public void printCombo(List> input){
: if (input == null || input.size()==0){
: return;
: }
: Stack> stc = new Stack>();
: for (int i=0; i: stc.push(input.get(i));
| G*****m
发帖数: 5395 | 9 这不就是backtrack吗？
【在 x******8 的大作中提到】
: 给一个List>,打印出所有组合
: eg.
: {
: {a, b},
: {c, d, e},
: {f, g}
: }
: 打印出来：
: {a, c, f}
: {a, c, g}
|
|
