没有思路 - 黑马程序员技术交流社区

package com.study.two;
import java.util.ArrayList;
import java.util.List;
/**
*
* 编程列出一个字符串的全字符组合情况，原始字符串中没有重复字符
例如：
原始字符串是"abc"，打印得到下列所有组合情况
"a" "b" "c"
"ab" "bc" "ca" "ba" "cb" "ac"
"abc" "acb" "bac" "bca" "cab" "cba"
*
*/
/**
* 思路：1.先把字符串转化为数组
* 2.先是进行数组的排列组合
* 例如输入abc,那么输出的组合应该是a,b,c,ab,ac,bc,abc。
* 3. 然后再是数组的全排列
* 如输入的是abc,则输出的是abc,acb,bac,bca,cab,cba。
* 4. 最后结合起来可以得出题目结果
*
*
*/
public class Test5 {
//数组的排列组合,例如输入abc,那么输出的组合应该是a,b,c,ab,ac,bc,abc。
//算法：假设我们想在长度为n得字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符，针对第一个字符有两种选择。
//一种是把该字符放进集合里，然后对剩下的n-1个字符中挑出m-1个字符。
//另一种是不把该字符放进集合里，然后是对剩下的n-1个字符中挑出m个字符。
//combination（char chs[])方法和combine(char []cs,int begin,int number,List <Character> list)
//方法是上面的排列组合的实现。最后再在排列组合的基础上加上（全排列组合）。则可以实现题目的要求。
public static void combiantion(char chs[]){
//如果数组为空则返回空
if(chs==null||chs.length==0){
return ;
}
//定义集合接收排列组合结果
List <Character> list=new ArrayList<Character>();
//字符串的1个，2个，3个....字符总长长度，字符的排列组合
for(int i=1;i<=chs.length;i++){
//从0位置开始扫描
combine(chs,0,i,list);
}
}
//从字符数组中第begin个字符开始挑选number个字符加入list中
public static void combine(char []cs,int begin,int number,List <Character> list){
//当挑选的字符数扫描到0时，将集合中的数据取出来进行全排列组合
if(number==0){
char cc[]=new char[list.size()];
for(int j=0;j<list.size();j++){
cc[j]=list.get(j);
}
//对排列组合后的字符进行全排列
permutation(cc, 0);
return ;
}
//当begin位循环到字符最后时，不再向下扫描，否则抛出数组溢出异常
if(begin==cs.length){
return;
}
//第一种情况，扫描到的第一个字符，加入的集合中去
list.add(cs[begin]);
//从剩下的字符中，扫描number-1个字符到集合中区
combine(cs,begin+1,number-1,list);
//第二种情况，扫描到的第一个字符不加入集合里头去，移除添加到数组中的字符
list.remove((Character)cs[begin]);
//从子符数组下一位挑选number个字符放入list中
combine(cs,begin+1,number,list);
}
//数组的全排列组合
//如输入的是abc,则输出的是abc,acb,bac,bca,cab,cba。
//算法：如abcde 首先是首位是a的情况下，全排列剩下的。然后交换1-2位数字，即首位是b的情况，全排列的。以此类推。
//用permutation自身对剩下的数组进行全排列，在permutation函数内，
//只要判断出来数组中只有一个元素时，无需再排列，直接打印数组即可。
//因为依次对1-2位，2-3位，1-4位进行交换，所以每次交换后，需要再次交换，使数组归位。
public static void permutation(char[]ss,int i){
//为了交换数据，定义中间变量
char temp;
if(ss==null||i<0||i>ss.length){
return;
}
if(i==ss.length){
System.out.println(new String(ss));
//输出排列
}else{
for(int j=i;j<ss.length;j++){
//交换前缀,使之产生下一个前缀
temp=ss[j];
ss[j]=ss[i];
ss[i]=temp;
//对i+1位之后剩下的元素进行全排列
permutation(ss,i+1);
//将前缀换回来,继续做上一个的前缀排列.
temp=ss[j];
ss[j]=ss[i];
ss[i]=temp;
}
}
}
public static void main(String args[]){
String str=new String("abcd");
//字符串转换成数组
char chss[]=str.toCharArray();
combiantion(chss);
}
}

复制代码

/*
思路：
a b c 与 a b c 组合得到ab ac ba bc ca cb
ab ac ba bc ca cb 把这个作为数组存起来，再与 a b c组合，如此循环
其中当前一个字串包含后面的字串时，用continue跳过
1、把原始字符串转成字符串类型数组arr1
2、新建一个字符串类型数组变量arr2，用于指向中间的组合，初始指向原始字串数组
3、原始数组与原始数组组合，把得到的结果先成一个字串，每个结果有逗号分开
4、用逗号分割字串得到数组，并用arr2指向该数组
5、用中间组合数组arr2与原始字符串数数组arr1组合，如此循环
*/
class ZhuHe
{
public static void main(String[] args)
{
zhuHe("abcef");
}
public static void zhuHe(String str)
{
char[] arr=str.toCharArray();
String[] arr1=new String[arr.length];
for(int i=0;i<arr.length;i++)
{
arr1[i]=arr[i]+"";
System.out.print(arr1[i]+" ");
}
System.out.println();
String[] arr2=arr1;
for(int x=0;x<arr.length-1;x++) //第一层需要与原始字串数组合的次数
{
String s="";
for(int i=0;i<arr2.length;i++) //第二层控制中间组合数组
{
for(int j=0;j<arr1.length;j++) //第三层控原始的字符串数组
{
if(arr2[i].contains(arr1[j]))
continue;
s=s+arr2[i]+arr1[j]+",";
}
}
s=s.substring(0,s.length()-1);
arr2=s.split(",");
for(int k=0; k<arr2.length;k++)
{
System.out.print(arr2[k]+" ");
}
System.out.println();
}
}
}

复制代码

package test;
public class ZuHe2 {
// main方法控制程序
public static void main(String[] args) {
String s = "abcd";//位数可以随便写，如 a abc abcd abcde。没有添加健壮性判断，如判空、重复等
char[] ch = s.toCharArray();
for (int i = 0; i < ch.length; i++) {
String[] s1 = diguizuhe(i, ch);// 调用递归，来完成字母的组合
print(s1);// 打印组合情况
}
}
// 递归函数，完成字母的组合
private static String[] diguizuhe(int i, char[] ch) {
// 只用一个字母直接返回本身
if (i == 0) {
String[] s = new String[ch.length];
for (int j = 0; j < ch.length; j++) {
s[j] = ch[j] + "";
}
return s;
}
// 大于一个字母，逐层递归
while (i > 0) {
i--;
String[] sum = new String[qiujiecheng(ch.length)];// 设置数组的大小
// 逐层拆解，递归组合
char[] ch2 = new char[ch.length - 1];
int m = 0;
for (int j = 0, count = 0; j < ch.length; j++) {
char ch3 = ch[j];
for (int k = 0, k1 = 0; k < ch.length; k++) {
if (j != k) {
ch2[k1] = ch[k];
k1++;
}
}
String[] s = diguizuhe(i, ch2);// 用拆分后的新字符串去递归
for (int z = 0; z < s.length && (s[z] != null); z++, m++) {
sum[count] = ch3 + s[z];
count++;
}
}
// 将得到的字符串数组去空，返回
String[] s1 = new String[m];
for (int j = 0, x = 0; j < sum.length; j++, x++) {
if (sum[j] != null) {
s1[x] = sum[j];
}
}
return s1;
}
return null;
}
// 打印字符串数组
private static void print(String[] s) {
for (int j = 0; j < s.length && s[j] != null; j++) {
if (j != s.length - 1) {
System.out.print("\"" + s[j] + "\"" + "\t");
} else {
System.out.println("\"" + s[j] + "\"");
}
}
}
// 求阶乘，用于确定数组的大小
private static int qiujiecheng(int n) {
int sum = 1;
for (int i = 1; i <= n; i++) {
sum *= i;
}
return sum;
}
}

复制代码