关于n个数里选k个的不同方法及一些思考
给出两个整数n和k，返回从1到n中取k个数字的所有可能的组合
例如：
如果n=4，k=2，结果为
[↵ [2,4],↵ [3,4],↵ [2,3],↵ [1,2],↵ [1,3],↵ [1,4],↵]
这题本身并不是特别的难,但是不同方法的复杂度差很多,而且响应了之前碰到的那句:
求所有符合的结果用深度递归(及时修剪),求最优结果或结果数量用动态规划;
最先想到的方式:
方法一:
用走迷宫的思路暴力递归,n个数每一个都可以看做迷宫的一步,有选和不选两种选择:
class Solution {
public ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
public void go(int n,int k,int i,ArrayList<Integer> list){
if(list.size()==k){
result.add(list);
return;
}
if(i>n) return;
// 不把当前位置的数选入
go(n,k,i+1,list);
ArrayList<Integer> newList = new ArrayList<Integer>(list);
newList.add(i);
// 把当前位置的数选入
go(n,k,i+1,newList);
}
public List<List<Integer>> combine(int n, int k) {
go(n,k,1,new ArrayList<Integer>());
return result;
}
}
这种方式表面上像一颗二叉树一样展开n个数有2^n次方种递归,但是对二叉树进行适当裁剪,对不要对枝叶不再扩展,勉强通过了测试55 ms 42.3 MB;
方法二:
层序递归的思路,一层层的去求,求f(n,1),f(n,2),......,f(n,k)---->n个数选1个的集合,选2个的集合....k个的集合;这种方式会建立大量的集合;
一开始我这样做,0-k的每一位上有1-n种选择,表面上感觉是k*n的复杂度,但是由于是不重复的,每次为了避免前面选过的数再次被选我用的HashSet不断判断的方式来避免重复加入,最后直接超时了;
class Solution {
public List<List<Integer>> combine(int n, int k) {
//
HashSet<Set<Integer>> result = new HashSet<Set<Integer>>();
result.add(new HashSet<Integer>());
for(int i=1;i<=k;i++){
HashSet<Set<Integer>> newResult = new HashSet<Set<Integer>>();
for(int j=1;j<=n;j++){
for(Set<Integer> set:result){
if(!set.contains(j)){
HashSet<Integer> newSet = new HashSet<Integer>(set);
newSet.add(j);
newResult.add(newSet);
}
}
}
result=newResult;
}
ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
for(Set<Integer> set:result){
ArrayList<Integer> temp = new ArrayList<Integer>(set);
res.add(temp);
}
return res;
}
}
方法三:
动态规划的背包思路: dp[i][j]--->∑dp[i-1][j]+∑f(dp[i-1][j-1],i);利用前面的结果,二维的一格格的求,(方法二相当于一维的f(n,1)->f(n,2)->f(n,3)->.....->f(n,k),n恒定,一层层的求), 这种方式比方法二快,但比走迷宫暴力并剪枝的方式慢4倍, 213 ms -270.3 MB勉强通过;
(之前华为那道题两个数组互相交换,最后最小值,那道题则用动态规划转为背包问题最好,映证了那句话:求所有符合的结果用深度递归(及时修剪),求最优结果或结果数量用动态规划;)
class Solution {
public List<List<Integer>> combine(int n, int k) {
// dp[i][j]--->dp[i-1][j]+f(dp[i-1][j-1],i);
ArrayList<List<Integer>>[][] dp= new ArrayList[n+1][k+1];
for(int i=0;i<=n;i++){
for(int j=0;j<=k;j++){
if(i==0||j==0){
ArrayList<List<Integer>> temp = new ArrayList<List<Integer>>();
temp.add(new ArrayList<Integer>());
dp[i][j]=temp;
}else{
ArrayList<List<Integer>> newResult = new ArrayList<List<Integer>>();
for(List<Integer> list:dp[i-1][j-1]){
ArrayList<Integer> newList = new ArrayList<Integer>(list);
newList.add(i);
newResult.add(newList);
}
for(List<Integer> list:dp[i-1][j]){
if(list.size()==j){
newResult.add(new ArrayList<Integer>(list));
}
}
dp[i][j]=newResult;
}
}
}
return dp[n][k];
}
}
方法四:
用DFS深度优先遍历,类似于走迷宫但是每一步横向铺开,方法一的每一步都只考虑两种情况,选和不选,这里直接扩散到 i到n-(k-size)+1 (其中size是前面递归过来的已经选了的情况数;
)中的任意位置,类似于棋盘不只上下左右走了,棋子♟可以跳到任意位置;
在每一次递归前list.add(i),执行go(next)递归之后,又及时的进行删除动作,list.remove(last);只在最后符合要求时clone这个list,并放入结果集合;(不保存中间结果)
最后只用了2ms 42MB;
class Solution {
public ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
public void go(int n,int k,int i,ArrayList<Integer> list){
if(list.size()==k){
// 这里与方法一不同,需要克隆后放入结果集;因为递归后还要撤销给for的下一个用;
result.add(new ArrayList<Integer>(list));
return;
}
if(i>n) return;
int size = list.size();
for(int index = i;index<=n-(k-size)+1;index++){
list.add(index);
go(n,k,index+1,list);
// 每一层及每一次调用都及时删除,方便下一次for循环恢复;
list.remove(size);
}
}
public List<List<Integer>> combine(int n, int k) {
go(n,k,1,new ArrayList<Integer>());
return result;
}
}
