注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex 77 Combinations  

2015-05-15 22:02:03|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
排列问题,严格来说不难,可是,递归调试了我好久的。

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],
而且刚开始的时候,排列的总个数计算错了导致程序memory error,想一下,C20  10,这是一个什么概念。。。。

void swap(int*a, int*b)
{
int temp = a[0];
a[0] = b[0];
b[0] = temp;
}
void Perm(int *wList, int start, int end,int k, int*list,int**result, int* returnSize,int depth)
{
int i = 0;
if (depth>=k)
{
//退出条件 一定需要递归深度来进行判断
// list用来保存临时变量 wList是原来的序列
// k是要挑选的个数 result最后返回的, returnSize记录个数 其实可以不用
memcpy(result[returnSize[0]], list, k*sizeof(int));
returnSize[0]++;
}
else
{
for (i = start; i <= end; i++)
{
list[depth] = wList[i];
Perm(wList, i + 1, end,k, list, result, returnSize,depth+1);
}
}
}
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *columnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int** combine(int n, int k, int** columnSizes, int* returnSize) {

returnSize[0] = 0;
int len = 1, i;
int num = n;
int count = k; //先求排列组合一共有多少种,开始算错了
//没有除以 1 2 3 。。。 k导致len特别大,提交到 oj又runtime error
if (k > n / 2)
{
count = n - k;
}
for (i = 0; i<count ; i++)
{
len *= num;
num--;
}
for (i = 0; i<count; i++)
{
len /= (i+1);
}
//if (len > 10000)
//return NULL;
int**result = (int**)malloc(len*sizeof(int*));
//第一个恶心的runtime error说的是要求自己分配columSizes的空间!!!!!!!
//columnSizes = (int**)malloc(len*sizeof(int*));
for (i = 0; i < len; i++)
{
result[i] = (int*)malloc(k*sizeof(int));

}
columnSizes[0] = (int*)malloc(len*sizeof(int));


int end = n - 1, start = 0;
int *list = (int*)malloc(k*sizeof(int));
int *wList = (int*)malloc(n*sizeof(int));
for (i = 1; i <= n; i++)
{
wList[i-1] = i;
}
int depth = 0;
Perm(wList, start, end, k, list, result, returnSize,depth);
for (i = 0; i < len; i++)
{
columnSizes[0][i] = k;
}
return result;
}


update java version 2015/12/3/

import java.util.ArrayList;
import java.util.List;
public class Combinations {
public List<List<Integer>> combine(int n, int k) {
return helper(n, k);
}
private List<List<Integer>> helper(int n, int k) {
int depth = 0;
ArrayList<Integer> src = new ArrayList<>();
for (int i = 0; i < n; ++i) {
src.add(i + 1);
}
List<List<Integer>> result = new ArrayList<>();
ArrayList<Integer> ls = new ArrayList<>();
int start = 0;
dfs(result, ls, src, depth, k, start);
return result;
}
private void dfs(List<List<Integer>> result, ArrayList<Integer> ls,
ArrayList<Integer> src, int depth, int k, int start) {
// result 保存最后结果
// ls 临时结果
// src原list
// depth递归深度
if (depth >= k) {
result.add((List<Integer>) ls.clone());
return;
}else {
for (int i = start; i < src.size(); ++i ) {
ls.add(src.get(i));
dfs(result, ls, src, depth + 1, k, i + 1);
ls.remove(ls.size() - 1);
}
}
}
}



  评论这张
 
阅读(6)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017