文档章节

Submission Details

Cobbage
 Cobbage
发布于 2015/01/15 00:17
字数 317
阅读 12
收藏 0

一、非递归的实现

      都要借助于10然后移动位置

      1.1 就是10才变换位置

      1.2如果当前位置移动了,那么后面的1要重新移动

举个例子来就是

1 2 3 4
-------------
1 1 0 0

1 0 0 1-〉关键地方
0 1 0 1-> 本来 但是要下面的
0 1 1 0
public List<List<Integer>> subsets(int[] S) {
	 ArrayList<List<Integer>>result=new ArrayList<List<Integer>>();
	 result.add(new ArrayList<Integer>());
     Arrays.sort(S);
	 for(int i=1;i<=S.length;i++){
		 result.addAll(getCombine(S,i));
	 }
	return result;
 }

/**
 * 多数的做法都是声明一个数组
 */
 public List<List<Integer>> getCombine(int [] s,int length){
	 if(length>s.length||length<=0)
		 return new ArrayList<List<Integer>>();
	 //初始化一个数组保存自己选择组合
	 int [] choice=new int[s.length];
	 for(int i=0;i<s.length;i++){
		 if(i<length)choice[i]=1;
		 else choice[i]=0;
	 }
	 ArrayList<List<Integer>>result=new ArrayList<List<Integer>>();
	 int position=-1;
	do{
		 if(position!=-1){
			 choice[position]=0;
			 choice[position+1]=1;
			  
			  if(choice[choice.length-1]==1){
				  int count=2;
				  for(int i=position+2;i<choice.length;i++){
					  if(choice[i]==1){
						  choice[i]=0;
						  choice[position+count++]=1;
					  }
						  
				  }
			  }
		  }
		 
		 ArrayList<Integer> now=new ArrayList<Integer>();
		 for(int i=0;i<choice.length;i++){
			 if(choice[i]==1)
				 now.add(new Integer(s[i]));
		 }
		 result.add(now);
	 } while((position=getPosition(choice))!=-1);
	 
	 return result;
 }
 
 public int getPosition(int[] a){
	 int position=-1;
	 for(int i=0;i<a.length-1;i++)
		 if(a[i]==1&&a[i+1]==0)
			 position=i;
	 
     return position;	 
 }

 

 

二、组合的作用

      和排列组合起来就是解

 

© 著作权归作者所有

共有 人打赏支持
上一篇: 收藏夹解析
下一篇: Trapping Rain Water
Cobbage

Cobbage

粉丝 51
博文 148
码字总数 73732
作品 1
闵行
QA/测试工程师
私信 提问
Gerrit 2.12 Release

版权声明:本文为博主原创文章,未经博主允许不得转载。 马哥私房菜的github地址 https://github.com/mageSFC/myblog https://blog.csdn.net/mmh19891113/article/details/83902354 Gerrit ...

马哥私房菜
2018/11/09
0
0
iphone提交几次了总是说证书错误,真不知道错什么地方了?

Dear developer, We have discovered one or more issues with your recent delivery for "xxxx". To process your delivery, the following issues must be corrected: Invalid Signature -......

10yuecf
2014/01/09
590
1
(hdu step 3.2.3)Super Jumping! Jumping! Jumping!(DP:求最长上升子序列的最大和)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/caihongshijie6/article/details/43672839 在写题解之前给自己打一下广告哈~。。抱歉了,希望大家多多支持我在...

黄俊东
2015/02/09
0
0
ServiceStack 项目实例 004 建立第一个服务--添加信息

下面我建立一个服务的Operation,实现添加一条信息的功能,在SOA模式开发中,Operation相当于MVC框架中的一个Action,但是SOA服务中是没有视图层和显示页面的,它对外提供的是数据服务,通常...

鼎六智能
2016/10/02
19
0
bryce1010专题训练——线段树习题汇总

版权声明:时间是有限的,知识是无限的,那就需要在有限的时间里最大化的获取知识。 https://blog.csdn.net/Firetocheat_/article/details/78424696 延迟标记: 除了在修改指令中直接划分成的...

bryce1010
2017/11/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

intellJ IDEA搭建java+selenium自动化环境(maven,selenium,testng)

1.安装jdk1.8; 2.安装intellJ; 3.安装maven; 3.1 如果是单前用户,配置用户环境变量即可,如果是多用户,则需配置系统环境变量,变量名为MAVEN_HOME,赋值D:\Application\maven,往path中...

不最醉不龟归
40分钟前
2
0
聊聊ShenandoahGC的Brooks Pointers

序 本文主要研究一下ShenandoahGC的Brooks Pointers Shenandoah Shenandoah面向low-pause-time的垃圾收集器,它的GC cycle主要有 Snapshot-at-the-beginning concurrent mark包括Init Mark(P......

go4it
昨天
2
0
Makefile通用编写规则

#简单实用的Makefile模板: objs := a.o b.o test:$(objs) gcc -o test $^ # .a.o.d .b.o.d dep_files := $(foreach f,$(objs),.$(f).d) dep_files := $(wildcard $(dep_files)) ifneq ($(d......

shzwork
昨天
1
0
《万历十五年》的读后感作文4000字

《万历十五年》的读后感作文4000字: 万历十五年,即1587年,距今已过去432年。在明朝276的历史中,这一年很平淡,并没有什么特别之处。黄仁宇的《万历十五年》一书,有别于其他的历史叙述方...

原创小博客
昨天
1
0
vue组件系列4、Table封装下

知道了slot 怎么用,才可以理解table这样封装的原因 table插件部分 <template> <div> <!-- 关键字部分 --> <div class="pre_search" v-show="show_key"> <label>关键字:......

轻轻的往前走
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部