A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© lpc4276139 中级黑马   /  2014-8-6 11:17  /  1908 人查看  /  11 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

编程列出一个字符串的全字符组合情况,原始字符串中没有重复字符,
例如:原始字符串是"abc",
打印得到下列所有组合情况:
"a" "b" "c"
"ab" "bc" "ca" "ba" "cb" "ac"
"abc" "acb" "bac" "bca" "cab" "cba"

11 个回复

倒序浏览
第二行如下:ab ac ba bc  ca  cb
1.定义一个数组
2.两个for循环嵌套
3一个 变量x  一个变量y分别是两个for的变量
4.int x =0 ; x<3;x++  .int y =0;y<3;y++;
5 内循环中 if (x==y) continue  跳过这次循环  否则输出 两个字符组合
第三行 类似;
三个循环嵌套  最内循环 if(x==y||x==z||y==z) continue
回复 使用道具 举报
关键是两个算法,
1.组合算法(递归)把N个字符组成的字符串从头到尾依次去掉一个字符,形成N种组合,在对形成的组合递归使用该方法,问题是同一次生成的子串再次递归时,生成的组合会有重复的,因此这个最好推荐map,省掉去重。比如abc第一次递归生成bc,ac,ab,第二次递归生生成(b,c),(a,c),(a,b),第二次就产生了重复的组合。这个比较简单,复杂点的是排列的算法,需要对生成的组合调用排列算法,这个算法也是递归的。
2.排列算法,根据排列的定义,从N个字符中任取一个与剩下的去掉该字符的字符串重新组合,有N中可能,对剩下的没有被选择过的n-1个字符形成的串递归这个方法,于是就有了N!种排列。需要循环从没被选择过的字符串里依次取出一个字符,之后将这个字符从原串去掉,建议用StringBuilder的replace(int start, int end, '')方法,将已经被选择过的字符,取出的字符与去掉字符的串三者重新组合,并将结果加入结果集,递归这个方法,得到字符串所有排列。
3.结果集的处理,建议全部用map,在输出的时候格式化一下,通过循环将长度一样的字符串显示在一行。
回复 使用道具 举报
不会,不过看完这个我想到了个递归...但是怎么组合不会.....等级太低
回复 使用道具 举报
冒牌高手 发表于 2014-8-7 19:05
不会,不过看完这个我想到了个递归...但是怎么组合不会.....等级太低

我也想到了递归,但是不会用呀
回复 使用道具 举报
bbdeyouxang 发表于 2014-8-6 23:50
关键是两个算法,
1.组合算法(递归)把N个字符组成的字符串从头到尾依次去掉一个字符,形成N种组合,在对 ...

谢谢你的解释。。。
回复 使用道具 举报
建议不要去使用递归,递归是过去现在以及将来被几乎所有程序员规避的东西
假如,你是在排列一个很长的字符串,就30个字符吧,很可能即使你的程序一点问题都没有,但是它就是栈溢出,没办法,递归的太深了

这道题是可以用非递归的方式做的
你要做的是:
1.顺次获取字符串的每一个排列方式
2.判断方式是不是你需要的
3.输出当前的排列

你可以这么想,假如,一个三位的字符串,里面有3种字符(各不相同)
故,你的排列长度最小是1,最大是3
对于每一种长度(以3为例),你可以将它当成一个3位的,每一位最多有三种情况的三位3进制数,从这个三位数的最小值开始,遍历到其最大值,每一个数都是一个排列的状态

希望上面的对你有用,这个题三言两语说不清楚。
回复 使用道具 举报
基础题吧!!!我也抽到了这道
回复 使用道具 举报
zeus00456 发表于 2014-8-9 14:25
建议不要去使用递归,递归是过去现在以及将来被几乎所有程序员规避的东西
假如,你是在排列一个很长的字符 ...

谢谢您的解释,我正在努力做
回复 使用道具 举报
李利威 发表于 2014-8-9 21:33
基础题吧!!!我也抽到了这道

我就差这道题了,其他基础题,我全做出来。。。
回复 使用道具 举报
yqj 中级黑马 2014-8-10 23:39:47
11#
我也抽到了这道题,做了老久,lz加油!
回复 使用道具 举报
本帖最后由 ddewym123 于 2014-8-11 21:50 编辑

我今天做了下这道题。确实好麻烦。
我一开始只想到了递归方法(水平有限,实在没办法)。在参考了7楼zeus00456兄的思路后,写了非递归方法。
下面是我的代码,仅供参考:
  1. import java.util.ArrayList;
  2. import java.util.HashSet;
  3. import java.util.List;
  4. import java.util.Set;
  5. import java.util.regex.Matcher;
  6. import java.util.regex.Pattern;

  7. public class StringDemo {

  8.         public static void main(String[] args) {
  9.                 String str="abcd";
  10.                 //方法一:递归方法
  11.                 List<String> subStrs=getSubStr(str);//获取所有的子串
  12.                 List<String> stringSet=new ArrayList<String>();//用于添加所有的排列组合
  13.                 //获取每个子串的排列情况并添加进stringSet
  14.                 for(String string:subStrs){
  15.                         List<String> oldSet=arrangeStr(string,string.length());
  16.                         for(String arrangedStr:oldSet){
  17.                                 stringSet.add(arrangedStr);
  18.                         }
  19.                 }
  20.                 System.out.println(stringSet);
  21.                
  22.                 //方法二:非递归方法
  23.                 /*char[] chs=str.toCharArray();
  24.                 List<String> stringSet=new ArrayList<String>();
  25.                 int len=str.length();
  26.                 //获取所有的排列组合
  27.                 for (int i = 1; i <= len; i++) {
  28.                         Set<String> oldSet=getArrangedStr(chs,i);
  29.                         for(String string:oldSet){
  30.                                 stringSet.add(string);
  31.                         }
  32.                 }
  33.                 System.out.println(stringSet);*/
  34.         }
  35.         //方法一:递归方法
  36.         //找出该字符串的所有子串
  37.         private static List<String> getSubStr(String str) {
  38.                 List<String> newSet=new ArrayList<String>();       
  39.                 for (int i = 1; i <= str.length(); i++) {       
  40.                         List<String> oldSet=subStr(str,i);
  41.                         for (String string:oldSet) {
  42.                                 newSet.add(string);                       
  43.                         }
  44.                 }
  45.                 return newSet;
  46.         }
  47.         //获取num长度的子串
  48.         private static List<String> subStr(String str,int num){
  49.                 List<String> newSet=new ArrayList<String>();
  50.                 //如果要求子串长度为1,则每个字母都是子串
  51.                 if(num==1){
  52.                         for(int i=0;i<str.length();i++){
  53.                                 newSet.add(str.charAt(i)+"");
  54.                         }
  55.                         return newSet;
  56.                 }
  57.                 //如果要求子串长度为n,在确定首字母的情况下,递归获取剩下n-1位子串,然后拼凑起来
  58.                 for(int i=0;i<str.length()-1;i++){
  59.                         char c=str.charAt(i);
  60.                         List<String> oldSet=subStr(str.substring(i+1),num-1);
  61.                         for(String string:oldSet){
  62.                                 newSet.add(c+string);
  63.                         }
  64.                 }
  65.                 return newSet;
  66.         }
  67.         //排列字符串
  68.         private static List<String> arrangeStr(String str,int len) {
  69.                 List<String> newSet=new ArrayList<String>();       
  70.                 //如果字符串长度为1,则该字符串就只有一种排列情况
  71.                 if(len==1){
  72.                         newSet.add(str);
  73.                         return newSet;
  74.                 }
  75.                 //如果字符串长度为n,在确定首字母的情况下,递归获取剩下n-1长度的字符串的排列情况,然后拼凑起来
  76.                 for (int i = 0; i < len; i++) {
  77.                         StringBuilder sb=new StringBuilder(str);
  78.                         char c=sb.charAt(i);
  79.                         List<String> oldSet=arrangeStr(sb.deleteCharAt(i).toString(),len-1);
  80.                         for (String string:oldSet) {
  81.                                 newSet.add(c+string);                       
  82.                         }
  83.                 }
  84.                 return newSet;
  85.         }
  86.         //方法二:非递归方法
  87.         //获取长度为i的子串的所有排列情况
  88.                 private static Set<String> getArrangedStr(char[] chs, int i) {
  89.                         Set<String> hs=new HashSet<String>();
  90.                         /*对于每一种长度i,将它当成一个i位的,
  91.                         每一位有chs.length种情况的chs.length进制数,
  92.                         从这个0开始遍历到最大值,每一个数都是一种排列情况*/
  93.                         for (int j = 0; j < Math.pow(chs.length, i); j++) {
  94.                                 StringBuilder sb=new StringBuilder();
  95.                                 String string=Integer.toString(j, chs.length);//转换成chs.length进制值
  96.                                 string=String.format("%0"+i+"d", Integer.parseInt(string));//前面补0,保证字符串都是i位的
  97.                                 //产生一种排列情况,即一个子串
  98.                                 for (int k = 0; k < string.length(); k++) {
  99.                                         sb.insert(0,chs[Integer.parseInt(""+string.charAt(k))]);
  100.                                 }
  101.                                 String newStr=sb.toString();
  102.                                 //去除包含重复字母的子串
  103.                                 if(checkStr(newStr))
  104.                                         hs.add(sb.toString());
  105.                                 else
  106.                                         continue;
  107.                         }
  108.                         return hs;
  109.                 }
  110.                 //判断子串是否包含重复字母
  111.                 private static boolean checkStr(String newStr) {
  112.                         String regex="(\\w)\\w*\\1+";
  113.                         Pattern pattern=Pattern.compile(regex);
  114.                         Matcher matcher=pattern.matcher(newStr);
  115.                         return !matcher.find();
  116.                 }
  117. }
复制代码



回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马