一个组合加全排列的面试算法题及其解

简介: 题目:         给定“abcdefg” 7个字母,写一个程序将其中任意的字母组合输出,要求每种组合中每个字母最多出现一次,字母的不同位置顺序算不同的组合,例如ab和ba是不同的组合。

题目:

        给定“abcdefg” 7个字母,写一个程序将其中任意的字母组合输出,要求每种组合中每个字母最多出现一次,字母的不同位置顺序算不同的组合,例如ab和ba是不同的组合。

分析:

       刚拿到题目时我就想用for循环穷举式的列出,但分析了一半分析不下去,因为是口述的题目,没有笔和纸来草算,所以当时没答上来。

      后来我回顾,用笔和纸演算时发现了一个规律:

  

     这个规律来自于“斐波那契数列”,就是每增加一个字母,这个结果就是这个字母与上一个结果的一个组合(交换顺序的组合)。于是我用java按照这种思想写了一个实现:

import java.util.ArrayList;
import java.util.List;

public class Test {

	//a,b,ab,ba,c,ac,ca,bc,cb,abc,cab,bac,d,ad,da,bd,db,abd,bad,cd,acd,bcd,adcd,bacd,...
	
	
	public static List<String> p(char c, List<String> li) {
		int length = li.size();
		li.add(String.valueOf(c));
		for(int i =0;i<length;i++){
			li.add(String.valueOf(c) + li.get(i));
			li.add(li.get(i) + String.valueOf(c));
		}
		return li;
	}

	public static void main(String[] args) {
		long start = System.currentTimeMillis();
		String s = "abcdefg";
		List<String> li = new ArrayList<String>();
		li.add(String.valueOf(s.charAt(0)));
		for (int i = 1; i < s.length();i++) {
			char c1 = s.charAt(i);
			li = p(c1, li);
		}
		for(String ss : li){
			System.out.print(ss +",");
		}
		System.out.println(li.size());
		System.out.println(System.currentTimeMillis() - start);
	}

}

结果是1093个组合,如下:

a,b,ba,ab,c,ca,ac,cb,bc,cba,bac,cab,abc,d,da,ad,db,bd,dba,bad,dab,abd,dc,cd,dca,cad,dac,acd,dcb,cbd,dbc,bcd,dcba,cbad,dbac,bacd,dcab,cabd,dabc,abcd,e,ea,ae,eb,be,eba,bae,eab,abe,ec,ce,eca,cae,eac,ace,ecb,cbe,ebc,bce,ecba,cbae,ebac,bace,ecab,cabe,eabc,abce,ed,de,eda,dae,ead,ade,edb,dbe,ebd,bde,edba,dbae,ebad,bade,edab,dabe,eabd,abde,edc,dce,ecd,cde,edca,dcae,ecad,cade,edac,dace,eacd,acde,edcb,dcbe,ecbd,cbde,edbc,dbce,ebcd,bcde,edcba,dcbae,ecbad,cbade,edbac,dbace,ebacd,bacde,edcab,dcabe,ecabd,cabde,edabc,dabce,eabcd,abcde,f,fa,af,fb,bf,fba,baf,fab,abf,fc,cf,fca,caf,fac,acf,fcb,cbf,fbc,bcf,fcba,cbaf,fbac,bacf,fcab,cabf,fabc,abcf,fd,df,fda,daf,fad,adf,fdb,dbf,fbd,bdf,fdba,dbaf,fbad,badf,fdab,dabf,fabd,abdf,fdc,dcf,fcd,cdf,fdca,dcaf,fcad,cadf,fdac,dacf,facd,acdf,fdcb,dcbf,fcbd,cbdf,fdbc,dbcf,fbcd,bcdf,fdcba,dcbaf,fcbad,cbadf,fdbac,dbacf,fbacd,bacdf,fdcab,dcabf,fcabd,cabdf,fdabc,dabcf,fabcd,abcdf,fe,ef,fea,eaf,fae,aef,feb,ebf,fbe,bef,feba,ebaf,fbae,baef,feab,eabf,fabe,abef,fec,ecf,fce,cef,feca,ecaf,fcae,caef,feac,eacf,face,acef,fecb,ecbf,fcbe,cbef,febc,ebcf,fbce,bcef,fecba,ecbaf,fcbae,cbaef,febac,ebacf,fbace,bacef,fecab,ecabf,fcabe,cabef,feabc,eabcf,fabce,abcef,fed,edf,fde,def,feda,edaf,fdae,daef,fead,eadf,fade,adef,fedb,edbf,fdbe,dbef,febd,ebdf,fbde,bdef,fedba,edbaf,fdbae,dbaef,febad,ebadf,fbade,badef,fedab,edabf,fdabe,dabef,feabd,eabdf,fabde,abdef,fedc,edcf,fdce,dcef,fecd,ecdf,fcde,cdef,fedca,edcaf,fdcae,dcaef,fecad,ecadf,fcade,cadef,fedac,edacf,fdace,dacef,feacd,eacdf,facde,acdef,fedcb,edcbf,fdcbe,dcbef,fecbd,ecbdf,fcbde,cbdef,fedbc,edbcf,fdbce,dbcef,febcd,ebcdf,fbcde,bcdef,fedcba,edcbaf,fdcbae,dcbaef,fecbad,ecbadf,fcbade,cbadef,fedbac,edbacf,fdbace,dbacef,febacd,ebacdf,fbacde,bacdef,fedcab,edcabf,fdcabe,dcabef,fecabd,ecabdf,fcabde,cabdef,fedabc,edabcf,fdabce,dabcef,feabcd,eabcdf,fabcde,abcdef,g,ga,ag,gb,bg,gba,bag,gab,abg,gc,cg,gca,cag,gac,acg,gcb,cbg,gbc,bcg,gcba,cbag,gbac,bacg,gcab,cabg,gabc,abcg,gd,dg,gda,dag,gad,adg,gdb,dbg,gbd,bdg,gdba,dbag,gbad,badg,gdab,dabg,gabd,abdg,gdc,dcg,gcd,cdg,gdca,dcag,gcad,cadg,gdac,dacg,gacd,acdg,gdcb,dcbg,gcbd,cbdg,gdbc,dbcg,gbcd,bcdg,gdcba,dcbag,gcbad,cbadg,gdbac,dbacg,gbacd,bacdg,gdcab,dcabg,gcabd,cabdg,gdabc,dabcg,gabcd,abcdg,ge,eg,gea,eag,gae,aeg,geb,ebg,gbe,beg,geba,ebag,gbae,baeg,geab,eabg,gabe,abeg,gec,ecg,gce,ceg,geca,ecag,gcae,caeg,geac,eacg,gace,aceg,gecb,ecbg,gcbe,cbeg,gebc,ebcg,gbce,bceg,gecba,ecbag,gcbae,cbaeg,gebac,ebacg,gbace,baceg,gecab,ecabg,gcabe,cabeg,geabc,eabcg,gabce,abceg,ged,edg,gde,deg,geda,edag,gdae,daeg,gead,eadg,gade,adeg,gedb,edbg,gdbe,dbeg,gebd,ebdg,gbde,bdeg,gedba,edbag,gdbae,dbaeg,gebad,ebadg,gbade,badeg,gedab,edabg,gdabe,dabeg,geabd,eabdg,gabde,abdeg,gedc,edcg,gdce,dceg,gecd,ecdg,gcde,cdeg,gedca,edcag,gdcae,dcaeg,gecad,ecadg,gcade,cadeg,gedac,edacg,gdace,daceg,geacd,eacdg,gacde,acdeg,gedcb,edcbg,gdcbe,dcbeg,gecbd,ecbdg,gcbde,cbdeg,gedbc,edbcg,gdbce,dbceg,gebcd,ebcdg,gbcde,bcdeg,gedcba,edcbag,gdcbae,dcbaeg,gecbad,ecbadg,gcbade,cbadeg,gedbac,edbacg,gdbace,dbaceg,gebacd,ebacdg,gbacde,bacdeg,gedcab,edcabg,gdcabe,dcabeg,gecabd,ecabdg,gcabde,cabdeg,gedabc,edabcg,gdabce,dabceg,geabcd,eabcdg,gabcde,abcdeg,gf,fg,gfa,fag,gaf,afg,gfb,fbg,gbf,bfg,gfba,fbag,gbaf,bafg,gfab,fabg,gabf,abfg,gfc,fcg,gcf,cfg,gfca,fcag,gcaf,cafg,gfac,facg,gacf,acfg,gfcb,fcbg,gcbf,cbfg,gfbc,fbcg,gbcf,bcfg,gfcba,fcbag,gcbaf,cbafg,gfbac,fbacg,gbacf,bacfg,gfcab,fcabg,gcabf,cabfg,gfabc,fabcg,gabcf,abcfg,gfd,fdg,gdf,dfg,gfda,fdag,gdaf,dafg,gfad,fadg,gadf,adfg,gfdb,fdbg,gdbf,dbfg,gfbd,fbdg,gbdf,bdfg,gfdba,fdbag,gdbaf,dbafg,gfbad,fbadg,gbadf,badfg,gfdab,fdabg,gdabf,dabfg,gfabd,fabdg,gabdf,abdfg,gfdc,fdcg,gdcf,dcfg,gfcd,fcdg,gcdf,cdfg,gfdca,fdcag,gdcaf,dcafg,gfcad,fcadg,gcadf,cadfg,gfdac,fdacg,gdacf,dacfg,gfacd,facdg,gacdf,acdfg,gfdcb,fdcbg,gdcbf,dcbfg,gfcbd,fcbdg,gcbdf,cbdfg,gfdbc,fdbcg,gdbcf,dbcfg,gfbcd,fbcdg,gbcdf,bcdfg,gfdcba,fdcbag,gdcbaf,dcbafg,gfcbad,fcbadg,gcbadf,cbadfg,gfdbac,fdbacg,gdbacf,dbacfg,gfbacd,fbacdg,gbacdf,bacdfg,gfdcab,fdcabg,gdcabf,dcabfg,gfcabd,fcabdg,gcabdf,cabdfg,gfdabc,fdabcg,gdabcf,dabcfg,gfabcd,fabcdg,gabcdf,abcdfg,gfe,feg,gef,efg,gfea,feag,geaf,eafg,gfae,faeg,gaef,aefg,gfeb,febg,gebf,ebfg,gfbe,fbeg,gbef,befg,gfeba,febag,gebaf,ebafg,gfbae,fbaeg,gbaef,baefg,gfeab,feabg,geabf,eabfg,gfabe,fabeg,gabef,abefg,gfec,fecg,gecf,ecfg,gfce,fceg,gcef,cefg,gfeca,fecag,gecaf,ecafg,gfcae,fcaeg,gcaef,caefg,gfeac,feacg,geacf,eacfg,gface,faceg,gacef,acefg,gfecb,fecbg,gecbf,ecbfg,gfcbe,fcbeg,gcbef,cbefg,gfebc,febcg,gebcf,ebcfg,gfbce,fbceg,gbcef,bcefg,gfecba,fecbag,gecbaf,ecbafg,gfcbae,fcbaeg,gcbaef,cbaefg,gfebac,febacg,gebacf,ebacfg,gfbace,fbaceg,gbacef,bacefg,gfecab,fecabg,gecabf,ecabfg,gfcabe,fcabeg,gcabef,cabefg,gfeabc,feabcg,geabcf,eabcfg,gfabce,fabceg,gabcef,abcefg,gfed,fedg,gedf,edfg,gfde,fdeg,gdef,defg,gfeda,fedag,gedaf,edafg,gfdae,fdaeg,gdaef,daefg,gfead,feadg,geadf,eadfg,gfade,fadeg,gadef,adefg,gfedb,fedbg,gedbf,edbfg,gfdbe,fdbeg,gdbef,dbefg,gfebd,febdg,gebdf,ebdfg,gfbde,fbdeg,gbdef,bdefg,gfedba,fedbag,gedbaf,edbafg,gfdbae,fdbaeg,gdbaef,dbaefg,gfebad,febadg,gebadf,ebadfg,gfbade,fbadeg,gbadef,badefg,gfedab,fedabg,gedabf,edabfg,gfdabe,fdabeg,gdabef,dabefg,gfeabd,feabdg,geabdf,eabdfg,gfabde,fabdeg,gabdef,abdefg,gfedc,fedcg,gedcf,edcfg,gfdce,fdceg,gdcef,dcefg,gfecd,fecdg,gecdf,ecdfg,gfcde,fcdeg,gcdef,cdefg,gfedca,fedcag,gedcaf,edcafg,gfdcae,fdcaeg,gdcaef,dcaefg,gfecad,fecadg,gecadf,ecadfg,gfcade,fcadeg,gcadef,cadefg,gfedac,fedacg,gedacf,edacfg,gfdace,fdaceg,gdacef,dacefg,gfeacd,feacdg,geacdf,eacdfg,gfacde,facdeg,gacdef,acdefg,gfedcb,fedcbg,gedcbf,edcbfg,gfdcbe,fdcbeg,gdcbef,dcbefg,gfecbd,fecbdg,gecbdf,ecbdfg,gfcbde,fcbdeg,gcbdef,cbdefg,gfedbc,fedbcg,gedbcf,edbcfg,gfdbce,fdbceg,gdbcef,dbcefg,gfebcd,febcdg,gebcdf,ebcdfg,gfbcde,fbcdeg,gbcdef,bcdefg,gfedcba,fedcbag,gedcbaf,edcbafg,gfdcbae,fdcbaeg,gdcbaef,dcbaefg,gfecbad,fecbadg,gecbadf,ecbadfg,gfcbade,fcbadeg,gcbadef,cbadefg,gfedbac,fedbacg,gedbacf,edbacfg,gfdbace,fdbaceg,gdbacef,dbacefg,gfebacd,febacdg,gebacdf,ebacdfg,gfbacde,fbacdeg,gbacdef,bacdefg,gfedcab,fedcabg,gedcabf,edcabfg,gfdcabe,fdcabeg,gdcabef,dcabefg,gfecabd,fecabdg,gecabdf,ecabdfg,gfcabde,fcabdeg,gcabdef,cabdefg,gfedabc,fedabcg,gedabcf,edabcfg,gfdabce,fdabceg,gdabcef,dabcefg,gfeabcd,feabcdg,geabcdf,eabcdfg,gfabcde,fabcdeg,gabcdef,abcdefg


目录
相关文章
|
14天前
|
算法 Java
Java面试题:解释垃圾回收中的标记-清除、复制、标记-压缩算法的工作原理
Java面试题:解释垃圾回收中的标记-清除、复制、标记-压缩算法的工作原理
21 1
|
1月前
|
消息中间件 算法 Java
抖音面试:说说延迟任务的调度算法?
Netty 框架是以性能著称的框架,因此在它的框架中使用了大量提升性能的机制,例如 Netty 用于实现延迟队列的时间轮调度算法就是一个典型的例子。使用时间轮调度算法可以实现海量任务新增和取消任务的时间度为 O(1),那么什么是时间轮调度算法呢?接下来我们一起来看。 ## 1.延迟任务实现 在 Netty 中,我们需要使用 HashedWheelTimer 类来实现延迟任务,例如以下代码: ```java public class DelayTaskExample { public static void main(String[] args) { System.ou
33 5
抖音面试:说说延迟任务的调度算法?
|
14天前
|
算法 Java 程序员
Java面试题:解释Java的垃圾回收机制,包括常见的垃圾回收算法。介绍一下Java的垃圾回收算法中的标记-压缩算法。
Java面试题:解释Java的垃圾回收机制,包括常见的垃圾回收算法。介绍一下Java的垃圾回收算法中的标记-压缩算法。
18 0
|
15天前
|
算法 Java 开发者
Java面试题:Java内存探秘与多线程并发实战,Java内存模型及分区:理解Java堆、栈、方法区等内存区域的作用,垃圾收集机制:掌握常见的垃圾收集算法及其优缺点
Java面试题:Java内存探秘与多线程并发实战,Java内存模型及分区:理解Java堆、栈、方法区等内存区域的作用,垃圾收集机制:掌握常见的垃圾收集算法及其优缺点
16 0
|
15天前
|
存储 算法 Java
Java面试题:解释JVM的内存结构,并描述堆、栈、方法区在内存结构中的角色和作用,Java中的多线程是如何实现的,Java垃圾回收机制的基本原理,并讨论常见的垃圾回收算法
Java面试题:解释JVM的内存结构,并描述堆、栈、方法区在内存结构中的角色和作用,Java中的多线程是如何实现的,Java垃圾回收机制的基本原理,并讨论常见的垃圾回收算法
13 0
|
1月前
|
机器学习/深度学习 存储 算法
Python5种算法回溯+剪枝、字典序、递归交换、计数回溯、迭代法 实现全排列ll【力扣题47】
Python5种算法回溯+剪枝、字典序、递归交换、计数回溯、迭代法 实现全排列ll【力扣题47】
|
1月前
|
存储 算法 Java
面试高频算法题汇总「图文解析 + 教学视频 + 范例代码」之 二分 + 哈希表 + 堆 + 优先队列 合集
面试高频算法题汇总「图文解析 + 教学视频 + 范例代码」之 二分 + 哈希表 + 堆 + 优先队列 合集
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
|
1月前
|
数据采集 算法 数据挖掘
LeetCode 题目 80:删除排序数组中的重复项 II【算法面试高频题】
LeetCode 题目 80:删除排序数组中的重复项 II【算法面试高频题】
|
1月前
|
存储 机器学习/深度学习 算法
python 3种算法 回溯法、字典序生成、递归交换 实现全排列【力扣46题】
python 3种算法 回溯法、字典序生成、递归交换 实现全排列【力扣46题】