黑马基础测试题

前两天走黑马的流程，遇到一道测试题，自己想了两天才弄一个效率超低的，从网上查了一个答案，居然用了四层循环，看的还不太明白，分享下，希望大神能给我指导指导，有什么更好的方法也希望能告诉小弟，谢谢
6、编程列出一个字符串的全字符组合情况，原始字符串中没有重复字符，例如：
题目：原始字符串是"abc"，打印得到下列所有组合情况：
"a" "b" "c"
"ab" "bc" "ca" "ba" "cb" "ac"
"abc" "acb" "bac" "bca" "cab" "cba"
网上答案：

package com.itheima;
import java.util.LinkedList;
public class Test12 {
static int n=0,count = 0;
static char[] array = { 'a', 'b','c','d'};
static LinkedList <char[]> list = new LinkedList<char[]> ();//转化为集合
static int[] indexs = new int[array.length];
static int len = array.length;
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
getSub ();
for ( char[] cs : list ){
System.out.println(cs);
}
}
private static LinkedList<char[]> getSub () //获取
{
while (count <= len){
recursionSub (-1);
count++;
}
return list;
}
//
private static LinkedList <char[]> recursionSub ( int start )
{
start++;
if (start > count - 1){
return null;
}
for ( indexs[start] = 0; indexs[start] < len; indexs[start]++ ){
recursionSub (start);
if (start == count - 1){
char[] temp = new char[count];
for ( int i = count - 1; i >= 0; i-- ){
temp[start - i] = array[indexs[start - i]];
}
boolean flag = true;
for ( int i = 0; i < temp.length; i++ ){
for ( int j = i+1; j < temp.length; j++ ){
if (temp[i] == temp[j]){
flag = false;
break;
}
}
}
if (flag){
list.add (temp);
}
}
}
return list;
}
}

复制代码

HPU--spring87 · HPU--spring87

弄个数组，按1个，2个，3个，遍历。

宝安 · 宝安

HPU--spring87 发表于 2014-7-23 21:21
弄个数组，按1个，2个，3个，遍历。

输入的字符串长度不一定是3，可能是4,5………………10000000000

黎志勇 · 黎志勇

每次看到这题我都会重新写一遍。

package test;
public class Test5 {
public static void main(String[] args) {
printStringCombination("abcd");
}
//封装一下
public static void printStringCombination(String string){
String[] selected = {""};//初始化已选择字符串数组
String[] toSelect = {string};//初始化待选择字符串数组
combine(selected, toSelect, string.length());//开始选择
}
//打印组合的具体实现，需要递归
private static void combine(String[] selected,String[] toSelect,int length) {
if(length==0){//length为待选择字符串的长度，长度为0则退出方法
return;
}
/*
* ------------初始------------
* 已选择：空串对应未选择:abc
* ------------选第一个------------
* 已选择：对应未选择：
* a bc
* b ac
* c ab 共 1*3=3种
* ------------选第二个------------
* 已选择：对应未选择：
* ab c
* ac b
* ba c
* bc a
* ca b
* cb a 共 3*2=6种
* 每次选择得到的组合数为上次已经选择的组合数*待选择字符串的长度
*/
int combinations = selected.length*length;//每次选择得到的组合数
String[] newSelected = new String[combinations];//新一轮已选择的组合
String[] newToSelect = new String[combinations];//新一轮待选择的组合
int count = 0;
for (int i = 0; i < selected.length; i++) {
for (int j = 0; j < length; j++) {
newSelected[count] = selected[i]+toSelect[i].charAt(j);//选择一个字符拼接到已选择字符串上
//把选择的字符从原待选择字符串中剔除
newToSelect[count] = toSelect[i].substring(0,j)+toSelect[i].substring(j+1);
System.out.print(newSelected[count++]+" ");//打印最新得到的组合
}
}
System.out.println();//换行
combine(newSelected, newToSelect, length-1);//递归进行一下次选择
}
}

复制代码

花花公子 · 花花公子

受教了，也在看这个题

宝安 · 宝安

花花公子发表于 2014-7-23 22:59
受教了，也在看这个题

与君共勉

David.L · David.L

最基础的应该是用数组吧，利用length确定实际个数

DSY · DSY

package com.itheima;
import java.util.Scanner;
/**
* 编程列出一个字符串的全字符组合情况，原始字符串中没有重复字符，
* 例如：原始字符串是"abc"，打印得到下列所有组合情况
* "a" "b" "c"
* "ab" "bc" "ca" "ba" "cb" "ac"
* "abc" "acb" "bac" "bca" "cab" "cba"
* @author dong
*
*/
public class Test6 {
private String input; //从输入流中读取的字符串
private void getCollection(String strCollection)
{
if(strCollection.length() == input.length()){
return; //当迭代到子字符串和原始字符串相同长度时，迭代结束，返回
}
else{
for(int i=0;i<input.length();i++){ //循环遍历整个原始数组
if(strCollection.contains(String.valueOf(input.charAt(i)))){ //判断子字符串是否包含下标为i的原始字符串的字符，如果是就继续循环；没有执行else操作
continue;
}
else{
strCollection +=input.charAt(i); //将子字符串中没有的字符添加到子字符串中
System.out.println(strCollection); //打印输出
getCollection(strCollection); //进行下一轮迭代
strCollection = strCollection.substring(0, strCollection.length()-1);//将刚添加到子字符串中的字符去掉。
}
}
}
}
public static void main(String[] args) {
System.out.println("请输入字符串");
Scanner in = new Scanner(System.in);
Test6 test = new Test6();
test.input = in.next();
test.getCollection("");
}
}

复制代码

MGC · MGC

学习了，很不错，多发这种帖子

790324255a · 790324255a

明早试做看

fantacyleo · fantacyleo

三重循环，无递归。

import java.util.ArrayList;
/*
* 输入N个字符,如'a','b','c'，打印出所有组合
* a b c
* ab ac bc ba bc cb
* abc acb bac bca cba cab
*
* 思路：
* 长度为n的字符串排列，是长度为n-1的每个字符串排列的末尾加上一个字符
* 比如，abc是由ab末尾加c得到的；acb是由ac末尾加c得到的。
* 因此，用一个ArrayList不断添加已得到的排列结果。当要排列长度为n的字符串时，让两个指针分别指向长度为n-1的排列在结果集合中的起止下标
*/
public class Permute {
public static void main(String[] args) {
String s = "abc";
printPermute(s);
}
public static void printPermute(String str) {
char[] candidates = str.toCharArray();
int len = str.length();
ArrayList<String> permutations = new ArrayList<String>(); // 存储排列结果
// 长度为1的排列，直接添加
for (char c : candidates)
permutations.add(Character.toString(c));
// 下标指针，分别指向长度为1的字符串排列的起止位置
int start = 0;
int end = permutations.size();
// 长度2到len的排列，用循环完成
for (int i = 2; i <= len; i++) {
// 下面的二重循环，外层循环遍历长度为n-1的每一个字符串排列
for (; start < end; start++) {
String s = permutations.get(start);
// 内层循环则尝试在长度为n-1的字符串排列的尾部添加一个字符，形成一个长度为n的字符串
for (char c : candidates) {
// 只添加不重复的字符
if (s.indexOf(c) == -1)
permutations.add(s + c);
}
}
// 经过循环，start已经指向长度为n-1的字符串排列在结果集合中的起始位置
// 现在让end指向指向长度为n-1的字符串排列在结果集合中的终止位置
end = permutations.size();
// 开始下一次循环，处理长度为n的字符串排列
}
// 打印结果集合及其元素个数
System.out.println(permutations);
System.out.println(permutations.size());
}
}

复制代码

刘小印 · 刘小印

这个问题，貌似做过

王飞163 · 王飞163

我也有这个题目呵呵

黎志勇 · 黎志勇

升级一下我4楼中的算法，这下不用递归了，直接通过while循环搞定，只要定义一个方法就OK。

package test;
public class CopyOfTest5 {
public static void main(String[] args) {
printStringCombination("abcdef");
}
public static void printStringCombination(String string) {
String[] selected = { "" };
String[] toSelect = { string };
int length = string.length();
int combinations;// 每次选择得到的组合数
while (length != 0) {
combinations = selected.length * length;
String[] newSelected = new String[combinations];// 新一轮已选择的组合
String[] newToSelect = new String[combinations];// 新一轮待选择的组合
for (int i = 0, count = 0; i < selected.length; i++) {
for (int j = 0; j < length; j++, count++) {
newSelected[count] = selected[i] + toSelect[i].charAt(j);// 选择一个字符拼接到已选择字符串上
if (length != 1) {// 当待选择数组中的字符串长度为1的时候，就不需要再更改该组合了
newToSelect[count] = toSelect[i].substring(0, j)
+ toSelect[i].substring(j + 1);
}
System.out.print(newSelected[count] + "\t");// 打印最新得到的组合
}
}
System.out.println();
selected = newSelected;// 更新已选择组合
toSelect = newToSelect;// 更新待选择组合
length--;// 待选择组合中的字符串长度减1
}
}
}

复制代码

黎志勇 · 黎志勇

fantacyleo 发表于 2014-7-24 00:46
三重循环，无递归。

我也重写了下。在14楼。

蒲公英在飞 · 蒲公英在飞

赞一个。。。。。。。。

帐号		自动登录	找回密码
密码			加入黑马

黑马基础测试题

16 个回复

点评

黑马骑士勋章