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

HT·生活

123

 
 
 

日志

 
 

ex78 Subsets  

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

  下载LOFTER 我的照片书  |

Given a set of distinct integers, nums, return all possible subsets.

Note:

  • Elements in a subset must be in non-descending order.
  • The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

求子集,以前老师讲过,可以用递归的,相当于搜索一棵二叉树,0或者1,最后到了叶子节点的时候判断一下就可以了,这个是没有重复元素的ex90是有重复元素的。

int *mark;
int traverse(int*nums, int n, int**columnSizes, int *returnSize, int depth, int**result)
{
if (depth >= n)
{
//递归退出条件
int counter = 0;
for (int i = 0;i < n; i++)
{
if (mark[i] == 1)
{
counter++;
}
}
columnSizes[0][returnSize[0]] = counter;
result[returnSize[0]] = (int*)malloc(counter*sizeof(int));
counter = 0;
for (int i = 0; i < n; i++)
{
if (mark[i] == 1)
{
result[returnSize[0]][counter] = nums[i];
counter++;
}
}
returnSize[0]++;
return 0;
}
else
{
traverse(nums, n, columnSizes, returnSize, depth + 1, result);
mark[depth] = 1 - mark[depth];
traverse(nums, n, columnSizes, returnSize, depth + 1, result);
return 0;
}
}

int** subsets(int* nums, int numsSize, int** columnSizes, int* returnSize) {
if (numsSize <= 0)
return NULL;
int**result = NULL;
int len = pow(2, numsSize);
int i,j;
mark = (int*)malloc(numsSize*sizeof(int));
for (i = 0; i < numsSize; i++)
{
mark[i] = 0;
}
int temp;
for (i = 0; i < numsSize; i++)
{
for (j = i; j < numsSize; j++)
{
if (nums[j] < nums[i])
{
temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
}
for (i = 0; i < numsSize; i++)
{

//printf("%d", nums[i]);;
}
returnSize[0] = 0;
result = (int**)malloc(len*sizeof(int*));
columnSizes[0] = (int*)malloc(len*sizeof(int));
traverse(nums, numsSize, columnSizes, returnSize, 0, result);
return result;
}


update java version 2015/12/3

import java.util.*;

public class Subsets {
public List<List<Integer>> subsets(int[] nums) {
return helper(nums);
}
Comparator<Integer> cmp = new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
if (o1 > o2) {
return 1;
} else if (o1 < o2) {
return -1;
} else {
return 0;
}
}
};
private List<List<Integer>> helper(int[] nums) {
// List<List<Integer>> result = new ArrayList<>();
// int[] mark = new int[nums.length];
// Arrays.fill(mark, 0);
// int depth = 0;
// dfs(mark, result, nums, depth);
// return result;
return iterative(nums);
}
private List<List<Integer>> iterative(int[] nums) {
int len = (int)Math.pow(2, nums.length);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < len; ++i) {
ArrayList<Integer> tmp = new ArrayList<>();
for (int j = 0; j < nums.length; ++j) {
if ((i & (1<<j)) != 0) {
tmp.add(nums[j]);
}
}
Collections.sort(tmp, cmp);
result.add(tmp);
}
return result;
}
private void dfs(int[] mark,List<List<Integer>> result, int[] nums, int depth) {
if (depth == nums.length) {
// 递归到了底部
List<Integer> ret = new ArrayList<>();
for (int i = 0; i < nums.length; ++i) {
if (mark[i] != 0) {
ret.add(nums[i]);
}
}
Collections.sort(ret, cmp);
result.add(ret);
} else {
mark[depth] = 0;
dfs(mark, result, nums, depth + 1);
mark[depth] = 1;
dfs(mark, result, nums, depth + 1);
}
}
}


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

历史上的今天

评论

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

页脚

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