【阳哥专栏】技术分活动第10期

王震阳老师 · 王震阳老师

반야_바라_밀 发表于 2014-8-14 10:10
楼主大好人，抽空看一下吧。

挺好：

import java.util.Scanner;
public class Sort {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("请输入一个长度小于10大于等于3的数组，数组中的元素为0~9的整数！");
Scanner sc=new Scanner(System.in);//接受键盘输入的数据
String in=sc.nextLine();//将键盘输入的数据转换成字符串
String[] array=in.split(" ");//将字符床在空格处进行切割，并将结果赋给字符串数组array
boolean flag=true;//用于判断输入的数据是否在指定范围内
if(array.length<10&&array.length>=3){//判断数组长度是否在指定范围内
int[] buf=new int[array.length];
try {//如果输入的数据不能转换成int型，则抛出异常
for(int i=0;i<array.length;i++){
buf[i]=Integer.parseInt(array[i]);//便利数组array，并将其中的每一个值转换成int型，并赋给buf
if(buf[i]>9||buf[i]<0){
flag=false;//如果输入的数据不在0~9之间，则flag为false
}
}
if(flag==true){
allSort(buf,0,buf.length-1);//符合各项规定后对数组buf进行全排列
}else{
System.out.println("输入数据有误，没有在0~9之间！");
}
} catch (NumberFormatException e) {
// TODO Auto-generated catch block
System.out.println("输入数据有误，不是整数！");
}
}else{
System.out.println("数组长度不合要求！");
}
}
//自定义的全排列算法，采用的是递归的思想
private static void allSort(int[] buf,int start,int end){
if(start==end){//当全排列进行到只对数组中的最后一个元素进行全排列是，此时的数组已经是全排列中的一种了，此时输出这个数组
for(int i=0;i<=end;i++){
System.out.print(buf[i]);
}System.out.println();
}else{
for(int j=start;j<=end;j++){
int temp=buf[start];
buf[start]=buf[j];
buf[j]=temp;//将传入数组的第一个元素开始依次与后面的元素进行交换，包括数组第一个元素本身
allSort(buf,start+1,end);//将第一个元素与后面的元素交换后，对从下一个元素开始到结尾的这段数组进行全排列
buf[j]=buf[start];
buf[start]=temp;//将交换后的两元素再次交换，回复两个数组元素交换前的位置
}
}
}
}

复制代码

王震阳老师 · 王震阳老师

zeus00456 发表于 2014-8-12 22:56
呈交解答，自认为是相对完善的版本了

里面附带一张示意图，用来说明思路，

思维很好，肯动脑子的程序员：

package com.itheima.bbs.activities.hex_conversion;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
/**
*题目：将一组数字、字母或符号进行排列，以得到不同的组合顺序，
*例如1 2 3这三个数的排列组合有：1 2 3、1 3 2、2 1 3、2 3 1、3 1 2、3 2 1。
*要求：用户输入一个整数（0到9）数组（数组长度大于等于3，小于10），
*那么请在控制台打印出该数组中所有成员的排列组合。
*详细代码+测试结果才可获得满分。
* @author Gilgamesh
*/
/**
* 说明：请老师先看这里
*
* 本程序没有使用递归，而使用密码盘（不知道有没有前人早就想到了，并起了名字，我自己想到的，于是瞎起了一个名）的思路，
* 每一种字符用一个数字代替，这些数字的组合方式就是字符组合的方式，状态是一串数字可以用+1的方式更新
* 就像从000-999找密码箱的密码一样。//附密码盘示意图。
*
* 本程序可以完成您题目的要求，但是不限于排列数字（是按照您“题目”的描述做的）代码的注释中注明了该法
* 本程序中支持的排序单位有：数字大小写字母和非空白字符（这些字符，比如制表符，排起来会令人费解）
* 虽然题目中规定长度3-10，可以将本程序中密码盘的状态容器改为int型整数，但是，为了以后强化功能方便，使用int数组
* 虽然题目只需要与输入长度相等的排列，本程序注释中依然提供了显示不足输入长度排列的方式，
* 比如123输出（1,2,3,12,13,……）只需按照注释内容放开对应的被注释语句
* 本程序处理了重复的排列，比如112只输出（112,121,211）三个
* 输入空串或全空白符串（比如一堆制表符）可以退出
*/
/**
*效果测试：
*输入：1 2 3
*输出：123 132 213 231 312 321
*输入： 1 1 2
*输出：112 121 211//去掉了重复
*输入：
*输出：程序结束，谢谢您的使用
*==========
*显示不足输入长度排列的方式中//请您在程序中搜索“列出不足”，并按注释放开注释
*输入： 1 2 3
*输出：1 2 3 12 13 21 23 31 32 123 132 213 231 312 321
*输入：112
*输出：1 2 11 12 21 112 121 211 //去掉了重复
*输入：
*输出：程序结束，谢谢您的使用
*
*在任意种模式，输入不满足条件都会被继续要求输入
*/
public class Permutation_Pombination {
//为了操作方便，直接静态一个容器
static char[] chs =null;
static HashSet<Integer> pastStat = new HashSet<Integer>();//保持排列哈希值
public static void main(String[] args) {
//洁净清爽的主方法
//循环功能
do{//可以省去while中对chs判空，提高效率
chs = getInputInfo();//通过方法获取用户输入
getPermutationAndPombination(chs);//排列
pastStat.clear();
}while(chs[0]!=' ');//退出标记为空格，因为’ ‘为禁用字符
System.out.println("程序结束，谢谢您的使用");
}
/**
* 输入方法
*/
static char[] getInputInfo() {
String s =null;
//打印提示信息
while(!isChsInLaw(s)){//输入不合法就卡在这里吧^_^
System.out.println("本程序用来获得一串数字、字母、符号的排列组合，请您输入您要输入的数字\n" +
"本程序支持对3-10个单位进行排列组合，您可以用空格分隔每个单位，" +
"也可以不分隔，程序将自动识别每个单位" +
"建议您输入不重复的字符，但是本程序已经处理了重复排列");
//开一个流读用来获得用户的输入
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//获得用户输入的字符串
try { s = br.readLine(); } //处理异常
catch (IOException e) {/*我们不希望用户看到任何异常，作为补偿，我们在代码中添加功能保证能获得合法的输入*/}
br=null;//释放流
}//输入合法通过,但是有可能数组中被注入了结束标记' '
return chs;
}
/**
* 判断用户的输入是否合法的方法
*/
private static boolean isChsInLaw(String s) {
if(s==null)//空串非法
return false;
if (s.matches("^ *$")){//字符串全是空格（全是禁用字符）或长度为零（明显是不想玩了）时退出
chs=new char[]{' '};//做个标记而已，让数组中出现禁用字符
return true;//既然不想玩了，就不用非要得到正确输入了
}
String noSpaceString = s.replaceAll("([\\s]*)+", "");//去除空白(非法字符)字符
//将下面的正则变为-->"[0-9]{3,10}"可按题目限定只排数字
if (noSpaceString.matches(".{3,10}")){//允许3-10位数字字母非空符号
chs = noSpaceString.toCharArray();
return true;
}
return false;//不是空串不满足上面条件返回假
}
/**
* 用来排列的方法
*/
private static void getPermutationAndPombination(char[] chs) {
if(chs[0]==' ')return;//带着结束标记不用排
//根据字符串的位数（数组的位数）建立状态（密码）盘
//用chs数组的索引作为该字符的状态码
//0对应数组第一位，1对应数组第二位，2对应数组第三位.....
int[] stat = new int[chs.length];
/*
* 如果需要列出不足数组长度的排列，请解开注释
//将整个密码盘用-1填充，-1表示此位尚未被使用
**/ Arrays.fill(stat, -1);
//获取每一位的最大状态值（就是上面两个数组的最大索引）
int max = stat.length-1;
while(!isComplete(stat)){//如果密码盘没有遍历完成，就继续，否则退出
//每一轮，密码盘的末位+1
stat[max]++;
//如果末位数值达到单个位的上限就向上进位，本位归0（就像数数一样）
for(int i = max ;i>=0 ;i--){
if (stat[i]==max+1){
stat[i]=0;
stat[i-1]++;
}
}//此时，密码盘中保存了一个状态密码
if (isInLaw(stat)){//判断这个状态十分符合要求（没有重复）
//如果这个状态是可用的，就输出状态对应的字符串
int hashValue = getHashValue(stat);//每一种排列的哈希值唯一
if(pastStat.contains(hashValue)) continue;//如果容器中有哈希值，此排列曾出现，跳出
else
pastStat.add(hashValue);//添加没有出现过的哈希值
for(int val : stat)//遍历状态
/*如果需要列出不足数组长度的排列，请解开注释
**/ if(val == -1)continue;//跳过没有使用的位以提高效率
else
System.out.print((char)chs[val]);//打印状态对应的字符
System.out.println();
}
}
}
/**
* 获取排列哈希值的方法
*/
private static int getHashValue(int[] stat) {//相当于复写了char[]的hashCode方法，复写后哈希值对于每一种排列唯一（不绝对但是概率极低）
int hashValue = 0;
for (int i = 0; i<stat.length;i++){
hashValue = hashValue * 31 + ((stat[i]==-1)?0:chs[stat[i]]);
}
return hashValue ;
}
/**
* 判断这个状态十分符合要求，要求是密码盘中没有重复的元素
*/
private static boolean isInLaw(int[] stat) {//在此步无法检测重复排列
boolean flag = true;//定义一个标记
for (int i=0;i<stat.length;i++){
//遍历当前状态的每一位，跳过未使用的位
/*如果需要列出不足数组长度的排列，请解开注释
* */if (stat[i]==-1)continue;
else
//从第一个有效位开始，判断和后面的每一位都不重复
for (int j = i+1;j<stat.length;j++){
if(stat[i]==stat[j]) {//若相等，证明当前位和后面的某位相等，说明有重复位不满足条件
flag = false; //有一次不满足就将标记置为假，跳出
break;
}
}
}
//若被置位为假，返回假；否则返回默认的真
return flag;
}
/**
* 判断密码盘有没有遍历完成，它的完成意味着排列动作的完成
*/
private static boolean isComplete(int[] stat) {//状态的每一位都是最大值时完成排列
int max = stat.length-1 ;//获取状态长度
boolean flag = true;//定义标记
for(int st : stat){//只有标记为真才有判断下一位的必要
if(flag==true)
if(st!=max) {
//只要某一位不等于单个位上的最大值，就将标记置为假，跳出
flag = false;
break;
}
}//若没跳出，返回真，整个密码盘遍历完成；否则说明某一位不满足遍历完成的条件，返回假
return flag;
}
}

复制代码

王震阳老师 · 王震阳老师

萍水相逢发表于 2014-8-11 16:24
代码提交

很好：

import java.util.*;
public class FullSort {
/**
* 递归算法：将数据分为两部分，递归将数据从左侧移右侧实现全排列
*
*/
private static void sort(List<String> datas, List<String> target, int length) {
if (target.size() == length) {
for (Object obj : target)
System.out.print(obj);
System.out.println();
return;
}
for (int i = 0; i < datas.size(); i++) {
List<String> newDatas = new ArrayList<String>(datas);
List<String> newTarget = new ArrayList<String>(target);
newTarget.add(newDatas.get(i));
newDatas.remove(i);
sort(newDatas, newTarget, length);
}
}
public static void main(String[] args) {
System.out.println("请输入一个长度大于等于3，小于10整数：");
// 从System.in中读取一个数
Scanner s = new Scanner(System.in);
//获取输入的数。
String num = s.nextLine();
//使用split进行分割字符串
String data[] = num.split("");
//在创建一个数组，长度少于data
String[] datas = new String[data.length - 1];
//将数组data中的有效字符付给数组datas
for (int x = 0; x < data.length; x++) {
if (x == data.length - 1)
continue;
datas[x] = data[x + 1];
}
// 设置为待排列数组的长度即实现全排列
int length = datas.length;
if(length>=3 && length<10){
System.out.println("数"+num+"的全排列：");
sort(Arrays.asList(datas), new ArrayList<String>(), length);
}else
System.err.print("您输入的数不在范围内！");
}
}

复制代码

沿途小将 · 沿途小将

沿途小将发表于 2014-8-13 21:04
以后还要这种好事，直接找我

不好意思！由于第一次提交错了，后改了，造成提交了两次

刘亚东 · 刘亚东

提交答案，今天提交还来得及么？

yesecongcong · yesecongcong

不知道算不算过期啊，现在，急求分啊

yesecongcong · yesecongcong

yesecongcong 发表于 2014-8-15 20:22
不知道算不算过期啊，现在，急求分啊

这怎么上面答案都出来了，看来我迟到了

单曲循环 · 单曲循环

看题目的

张亚军 · 张亚军

。。。。。。。。。。。。。。。。。。。。。。

子阳zy · 子阳zy

威武……

Fengs · Fengs

令题了啊啊啊

Kikyou · Kikyou

题目题目题目

FireWater · FireWater

虽然过期了就当练习做了

xiong910627 · xiong910627

黑马程序员，我来了！

嘿～～ · 嘿～～

让我看看能拿到技术分不

nadax · nadax

我是来领题的。

Huberry · Huberry

回帖领题

月夜小楠 · 月夜小楠

先来看看题

潘多拉 · 潘多拉

领题，拿分，进黑马，做精英

陶圣虎 · 陶圣虎

看看题目啊

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

【阳哥专栏】技术分活动第10期

评分

黑马骑士勋章