給出兩個(gè)整數(shù)n和k，返回從1到n中取k個(gè)數(shù)字的所有可能的組合
例如：
如果n=4，k=2，結(jié)果為
[? [2,4],? [3,4],? [2,3],? [1,2],? [1,3],? [1,4],?]
這題本身并不是特別的難,但是不同方法的復(fù)雜度差很多,而且響應(yīng)了之前碰到的那句:
求所有符合的結(jié)果用深度遞歸(及時(shí)修剪),求最優(yōu)結(jié)果或結(jié)果數(shù)量用動(dòng)態(tài)規(guī)劃;
最先想到的方式:
方法一:
用走迷宮的思路暴力遞歸,n個(gè)數(shù)每一個(gè)都可以看做迷宮的一步,有選和不選兩種選擇:
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;
// 不把當(dāng)前位置的數(shù)選入
go(n,k,i+1,list);
ArrayList<Integer> newList = new ArrayList<Integer>(list);
newList.add(i);
// 把當(dāng)前位置的數(shù)選入
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個(gè)數(shù)有2^n次方種遞歸,但是對(duì)二叉樹進(jìn)行適當(dāng)裁剪,對(duì)不要對(duì)枝葉不再擴(kuò)展,勉強(qiáng)通過了測試55 ms 42.3 MB;
方法二:
層序遞歸的思路,一層層的去求,求f(n,1),f(n,2),......,f(n,k)---->n個(gè)數(shù)選1個(gè)的集合,選2個(gè)的集合....k個(gè)的集合;這種方式會(huì)建立大量的集合;
一開始我這樣做,0-k的每一位上有1-n種選擇,表面上感覺是k*n的復(fù)雜度,但是由于是不重復(fù)的,每次為了避免前面選過的數(shù)再次被選我用的HashSet不斷判斷的方式來避免重復(fù)加入,最后直接超時(shí)了;
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;
}
}
方法三:
動(dòng)態(tài)規(guī)劃的背包思路: dp[i][j]--->∑dp[i-1][j]+∑f(dp[i-1][j-1],i);利用前面的結(jié)果,二維的一格格的求,(方法二相當(dāng)于一維的f(n,1)->f(n,2)->f(n,3)->.....->f(n,k),n恒定,一層層的求), 這種方式比方法二快,但比走迷宮暴力并剪枝的方式慢4倍, 213 ms -270.3 MB勉強(qiáng)通過;
(之前華為那道題兩個(gè)數(shù)組互相交換,最后最小值,那道題則用動(dòng)態(tài)規(guī)劃轉(zhuǎn)為背包問題最好,映證了那句話:求所有符合的結(jié)果用深度遞歸(及時(shí)修剪),求最優(yōu)結(jié)果或結(jié)果數(shù)量用動(dòng)態(tài)規(guī)劃;)
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深度優(yōu)先遍歷,類似于走迷宮但是每一步橫向鋪開,方法一的每一步都只考慮兩種情況,選和不選,這里直接擴(kuò)散到 i到n-(k-size)+1 (其中size是前面遞歸過來的已經(jīng)選了的情況數(shù);
)中的任意位置,類似于棋盤不只上下左右走了,棋子?可以跳到任意位置;
在每一次遞歸前l(fā)ist.add(i),執(zhí)行g(shù)o(next)遞歸之后,又及時(shí)的進(jìn)行刪除動(dòng)作,list.remove(last);只在最后符合要求時(shí)clone這個(gè)list,并放入結(jié)果集合;(不保存中間結(jié)果)
最后只用了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){
// 這里與方法一不同,需要克隆后放入結(jié)果集;因?yàn)檫f歸后還要撤銷給for的下一個(gè)用;
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);
// 每一層及每一次調(diào)用都及時(shí)刪除,方便下一次for循環(huán)恢復(fù);
list.remove(size);
}
}
public List<List<Integer>> combine(int n, int k) {
go(n,k,1,new ArrayList<Integer>());
return result;
}
}
