m*******1
发帖数: 168 | 1 不好意思，我基础太差了，在leetcode上遇到好几道类似的题目，每次在同一个地方总
是弄不明白，希望同学们能帮我讲解下，帮助和我一样有困惑的人，先谢谢大家啦！
Given two integers n and k, return all possible combinations of k numbers
out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
//solution
public ArrayList> combine(int n, int k)
{
ArrayList> res= new ArrayList
>();
ArrayList temp= new ArrayList ();
dfs(res,temp,n,k,1);
return res;
}
void dfs(ArrayList> res,ArrayList temp, int
n, int k, int level)
{
if(temp.size==k)
{
res.add(new ArrayList(temp));
return;
}
for(int i=level;i<=n;i++)
{
temp.add(i);
dfs(res,temp,n,k,i+1);
temp.remove(temp.size()-1); //这个地方为什么要这样处理呢，
remove的不是i本身（上面刚添加的元素），而是remove temp.size()-1
}
} | z****e
发帖数: 54598 | 2 [1,2],
[1,3],
[1,4],
当你做完[1,2]之后，你下一个需要的是[1,3]
那么就remove掉最后一个元素，which is 2
写成代码就是temp.remove(temp.size()-1);
然后再加3，就是temp.add(i); | b****g
发帖数: 192 | 3 没错，很多递归的题都是这么做的：
ArrayList tmp 存的是最终结果的其中一个。
在函数里面，这个tmp还没有完全算完，还在逐步添加以得到最终结果。
所以要先执行tmp.add()，使tmp向结果迈进一步。到这里都很好理解。
然后继续执行递归，递归里面当然还是向最终结果迈进，所以才叫做递归。
现在考虑tmp.remove()这行。
你有没有注意到，tmp.add(); dfs(); tmp.remove() 这几行都在一个for循环里面？
这是因为每次循环都对应tmp的一个值。
具体来说，tmp在执行for循环之前本来就有一个值，干干净净处女之身没被糟蹋过。
第一个执行这个循环，先执行tmp.add()得到一个tmp的值，于是tmp破处了。
于是向最终结果迈进了一步，然后执行递归，继续想最终结果迈进。
这一层一层的递归就先不管他。反正他们都是从dfs()这个递归里开始的。
总之执行完刚刚这个dfs()我们还在第一次循环里面。
假如没有这个tmp.remove()，那就继续执行第二次for循环了。
但是错误就出现了。tmp已经在第一次循环里面通过tmp.add()改变了，已经破处了。
可是我们执行第二次for循环时需要tmp的处女之值，然后继续递归。
所以说我们每次在tmp.add()之后必须用tmp.remove()给tmp做个处女mo修复手术。
翻来覆去车轱辘话我说了这么多，皆因表达能力有限，无法精炼概括，请谅解。
另外文中所用处女一词仅为形象表达，并无色情含义。
但这决不表明我支持非处女：
破了就是破了，你个破罐子，生活中可没有那么多remove函数供你调用。
【在 m*******1 的大作中提到】
: 不好意思，我基础太差了，在leetcode上遇到好几道类似的题目，每次在同一个地方总
: 是弄不明白，希望同学们能帮我讲解下，帮助和我一样有困惑的人，先谢谢大家啦！
: Given two integers n and k, return all possible combinations of k numbers
: out of 1 ... n.
: For example,
: If n = 4 and k = 2, a solution is:
: [
: [2,4],
: [3,4],
: [2,3],
| r**d
发帖数: 316 | 4 其实你的想法是对的，的确是要remove刚刚添加的数，但是ArrayList的remove方法如
果给int作为参数的话，是去掉index为i的那个元素。所以原程序写成了去掉最后一个
元素。
写成
temp.remove(Integer.valueOf(i));
也可以，结果一样的。
【在 m*******1 的大作中提到】
: 不好意思，我基础太差了，在leetcode上遇到好几道类似的题目，每次在同一个地方总
: 是弄不明白，希望同学们能帮我讲解下，帮助和我一样有困惑的人，先谢谢大家啦！
: Given two integers n and k, return all possible combinations of k numbers
: out of 1 ... n.
: For example,
: If n = 4 and k = 2, a solution is:
: [
: [2,4],
: [3,4],
: [2,3],
| m*******1
发帖数: 168 | 5 多谢，这下明白啦~
【在 r**d 的大作中提到】
: 其实你的想法是对的，的确是要remove刚刚添加的数，但是ArrayList的remove方法如
: 果给int作为参数的话，是去掉index为i的那个元素。所以原程序写成了去掉最后一个
: 元素。
: 写成
: temp.remove(Integer.valueOf(i));
: 也可以，结果一样的。
| m*******1
发帖数: 168 | 6 多谢 ^_^
【在 z****e 的大作中提到】
: [1,2],
: [1,3],
: [1,4],
: 当你做完[1,2]之后，你下一个需要的是[1,3]
: 那么就remove掉最后一个元素，which is 2
: 写成代码就是temp.remove(temp.size()-1);
: 然后再加3，就是temp.add(i);
| f****l
发帖数: 8042 | 7 你太牛了，太欢乐了。
【在 b****g 的大作中提到】
: 没错，很多递归的题都是这么做的：
: ArrayList tmp 存的是最终结果的其中一个。
: 在函数里面，这个tmp还没有完全算完，还在逐步添加以得到最终结果。
: 所以要先执行tmp.add()，使tmp向结果迈进一步。到这里都很好理解。
: 然后继续执行递归，递归里面当然还是向最终结果迈进，所以才叫做递归。
: 现在考虑tmp.remove()这行。
: 你有没有注意到，tmp.add(); dfs(); tmp.remove() 这几行都在一个for循环里面？
: 这是因为每次循环都对应tmp的一个值。
: 具体来说，tmp在执行for循环之前本来就有一个值，干干净净处女之身没被糟蹋过。
: 第一个执行这个循环，先执行tmp.add()得到一个tmp的值，于是tmp破处了。
| f*******b
发帖数: 520 | 8
MARK
【在 m*******1 的大作中提到】
: 不好意思，我基础太差了，在leetcode上遇到好几道类似的题目，每次在同一个地方总
: 是弄不明白，希望同学们能帮我讲解下，帮助和我一样有困惑的人，先谢谢大家啦！
: Given two integers n and k, return all possible combinations of k numbers
: out of 1 ... n.
: For example,
: If n = 4 and k = 2, a solution is:
: [
: [2,4],
: [3,4],
: [2,3],
| i****y
发帖数: 84 | 9 不是remove i自己吗？我觉得是啊？
【在 m*******1 的大作中提到】
: 不好意思，我基础太差了，在leetcode上遇到好几道类似的题目，每次在同一个地方总
: 是弄不明白，希望同学们能帮我讲解下，帮助和我一样有困惑的人，先谢谢大家啦！
: Given two integers n and k, return all possible combinations of k numbers
: out of 1 ... n.
: For example,
: If n = 4 and k = 2, a solution is:
: [
: [2,4],
: [3,4],
: [2,3],
| W**********i
发帖数: 136 | 10 请问一下这里， if(temp.size==k)
{
res.add(new ArrayList(temp));
return;
}
为啥要 res.add(new ArrayList(temp));？ 为什么不是res.add(temp);?
我试过res.add(tem)，输出的都是空的了 | l*****a
发帖数: 14598 | 11 你没发现temp被改来改去马？
【在 W**********i 的大作中提到】
: 请问一下这里， if(temp.size==k)
: {
: res.add(new ArrayList(temp));
: return;
: }
: 为啥要 res.add(new ArrayList(temp));？ 为什么不是res.add(temp);?
: 我试过res.add(tem)，输出的都是空的了
|
|
