黑马程序员技术交流社区

标题: 有没有大神能够挑战一下这道题，不用集合 [打印本页]

作者: 探索者 时间: 2015-5-31 23:11
标题: 有没有大神能够挑战一下这道题，不用集合
编程求从n个字符任取m个字符的所有可能情况，不用集合能不能做出来，自己花了一两天没做出来，看这里有没有大神

作者: 唐海 时间: 2015-5-31 23:15
:(等待大神

作者: as604049322 时间: 2015-5-31 23:15
不用集合还真搞不出来，，，我。。。

作者: as604049322 时间: 2015-5-31 23:23
搞出来有5个技术分我就搞

作者: KK要有光 时间: 2015-5-31 23:37
分别取1个字符，2个字符，3个字符……全部的组合形式。用递归。

public class Test {
/**
* @param args
*/
static String string="abc";
public static void main(String[] args) {
// TODO Auto-generated method stub
show(0,new String());
}
public static void show(int len, String temp) {
// TODO Auto-generated method stub
if(len<string.length()){
for(int i=0;i<string.length();i++){
if(!temp.contains(string.substring(i, i+1))){
System.out.print(temp+string.substring(i, i+1)+" ");
show(len+1, new String(temp+string.substring(i, i+1)));
}
}
}
}
}

复制代码

作者: as604049322 时间: 2015-5-31 23:57
其实我还是用了集合

/*
编程列出一个字符串的全字符组合情况，原始字符串中没有重复字符
例如：
原始字符串是"abc"，打印得到下列所有组合情况
"a" "b" "c"
"ab" "bc" "ca" "ba" "cb" "ac"
"abc" "acb" "bac" "bca" "cab" "cba"*/
import java.util.*;
class PermComStr{
public static void main(String[] args){
String[] list=combinations("abcd",2);
System.out.println(Arrays.toString(list));
}
/*思路分析：
每行字符个数都是递增，下一行的字符是建立在上一行的基础上得到的
即在将第一行字符串长度限定为1，第二行为2....，在第一行数据基础上{a,b,c}，创建第二行数据，遍历字符串中所字符，并与第一行数据组合。注意每行字符串长度限制
1、先将原始字符串转换成字符数组ch
2、将原始字符串每个字符添加到Arraylist<String> list集合中
3、遍历list集合用每个元素str去查找是否存在数组ch中的元素，如果ch中的字符c没有被str找到则用str+c作为新集合的值返回;
4、遍历新集合重复3步骤
*/
public static String[] getStringArr(String[] src, char[] ch) {
String[] newStr=new String[16];
int len=0;
for(String str:src){
for(char c:ch){
if(str.indexOf(c)==-1)
newStr[len++]=str+c;
if(len==newStr.length){
String[] temp=new String[newStr.length*2];
System.arraycopy(newStr, 0, temp, 0, len);
newStr=temp;
}
}
}
String[] temp=new String[len];
System.arraycopy(newStr, 0, temp, 0, len);
newStr=temp;
return newStr;
}
public static String[] combinations(String str,int num) {
char[] ch=str.toCharArray();
if(num>ch.length)
num=ch.length;
String[] src=new String[ch.length];
for(int i=0;i<ch.length;i++)
src[i]=ch[i]+"";
for(int i=1;i<num;i++){
src=getStringArr(src, ch);
}
return src;
}
}

复制代码

作者: 柒仴、看雲佉 时间: 2015-6-1 00:14
号厉害的样子啊啊啊嘛啊啊啊

作者: 微凉的暮色 时间: 2015-6-1 00:51
:curse:
我就想想

作者: LoveMyself 时间: 2015-6-1 01:07
用递归算法也可以做出来

作者: 探索者 时间: 2015-6-1 11:27

KK要有光发表于 2015-5-31 23:37
分别取1个字符，2个字符，3个字符……全部的组合形式。用递归。

可能题目的没表达清楚，不是你理解的这个，你回答的这种形式，我用递归已经做出来了，但题目是指从m个字符任取n个字符的所有可能情况，比如：
  从5个字符（a、b、c、d、e）任取3个的所有可能情况是：此时m=5，n=3
  abc
  abd
  abe
  acd
  ace
  ade
  bcd
  bce
  bde
  cde
共有10种可能情况

作者: 探索者 时间: 2015-6-1 11:30

as604049322 发表于 2015-5-31 23:57
其实我还是用了集合

你的答案和楼上理解的一样，要是是这种的话，我自己用递归以前已经做出来了，但题目是指从m个字符任取n个字符的所有可能情况，比如：
  从5个字符（a、b、c、d、e）任取3个的所有可能情况是：此时m=5，n=3
  abc
  abd
  abe
  acd
  ace
  ade
  bcd
  bce
  bde
  cde
共有10种可能情况

作者: 半月 时间: 2015-6-1 11:34

探索者发表于 2015-6-1 11:27
可能题目的没表达清楚，不是你理解的这个，你回答的这种形式，我用递归已经做出来了，但题目是指从m个字 ...

顺序不可变吗?
要不不是应该有60种

作者: 探索者 时间: 2015-6-1 11:35

半月发表于 2015-6-1 11:34
顺序不可变吗?
要不不是应该有60种

不考虑顺序的变化

作者: 李俊超 时间: 2015-6-1 11:38
貌似很有意思。。。

作者: as604049322 时间: 2015-6-1 13:28

探索者发表于 2015-6-1 11:30
你的答案和楼上理解的一样，要是是这种的话，我自己用递归以前已经做出来了，但题目是指从m个字符任取n个 ...

你运行一下试试，，，我只是备注没去掉而已，，结果是满足你的要求的

作者: as604049322 时间: 2015-6-1 13:29
combinations("abcd",2);第2个参数，想取几个就取几个

作者: 半月 时间: 2015-6-1 14:05

public class Test2 {
public static void main(String[] args) {
String str = "abcde";
sort(3,str);
}
/**
   *
   * @param num 排列字符数
   * @param str 要排列的字符串
   */
public static void sort(int num,String str){
char[] arr = str.toCharArray();
getResult(0,new char[num],0,arr);
}

/**
   * @param index 表示获得的字符数
   * @param result 结果数组
   * @param x 表示取到第几个字符
   * @param arr 源数组
   */
public static void getResult(int index,char[] result,int x,char[] arr){
if(index == result.length){
System.out.println(result);
}else{
/*可以获得的字符遍历
   */
for(int i = x;i<=arr.length-result.length+index;i++){
result[index] = arr[i];
getResult(index+1,result,i+1,arr);
}
}

}
}

作者: 小车车 时间: 2015-6-1 14:13
来学习的！

作者: 星辉祝愿 时间: 2015-6-1 14:41
来学习的的

作者: 王建伟 时间: 2015-6-1 15:19
瞅瞅而已。。。。。。

作者: 探索者 时间: 2015-6-1 15:56

as604049322 发表于 2015-6-1 13:29
combinations("abcd",2);第2个参数，想取几个就取几个

不错，但这个程序考虑了顺序的变化，而且如果字符串较大的话，取的数也大一点，会有点问题，例如：combinations("123456789zhong",9) 。这题目要求不需要考虑顺序变化的情况，比喻12和21就属于同一种情况

作者: 探索者 时间: 2015-6-1 16:05

半月发表于 2015-6-1 14:05
public class Test2 {
public static void main(String[] args) {
String str = "abcde";

这个程序可以，用递归做的，结果和题目要求一样，学习了，感谢

作者: 探索者 时间: 2015-6-1 16:08

半月发表于 2015-6-1 14:05
public class Test2 {
public static void main(String[] args) {
String str = "abcde";

这个程序可以，用递归做的，结果和题目要求一样，学习了，感谢

作者: 探索者 时间: 2015-6-1 16:16
怎么回复重复了，其实今天上午我自己又做了一下，用了两种方法做的，第一种和楼上的一样都是用递归做的，第二种用的是数组加循环做的。总算自己也做出来了，非常感谢大家的参与和帮忙

作者: 探索者 时间: 2015-6-1 16:26
分享一下上午做出来的两种方法：（时间太快，没写注释）
1.用递归做的：public class StringSort3 {
public static int count=0;
public static void main(String[] args){
String str="123456789";
sort("",str,7);
System.out.println(count);
}
public static void sort(String strPre,String str,int value){
if(value==0)
return;
String temp="";
String strL="";
for(int x=0;x<=str.length()-value;x++){
temp=strPre;
strPre=strPre+str.substring(x,x+1);
if(value==1){
System.out.println(strPre);
count++;
}
strL=str.substring(x+1,str.length());
value-=1;
sort(strPre,strL,value);
value+=1;
strPre=temp;
}
}
}

第二种方法：数组加循环

public class StringSort2 {
/**
* @param args
*/
public static int count=0;
public static void main(String[] args) {
// TODO Auto-generated method stub
String str="0123456789";
sort(str,4);
System.out.println(count);
}
public static void sort(String str,int value){
int pos1=0,pos2=0;
char[] ch= str.toCharArray();
char[] temp=new char[value];
for(int x=0;x<temp.length;x++)
temp[x]=ch[x];
System.out.println(String.valueOf(temp));
count++;
for(int i=value;i<=ch.length;i++){
if(i<ch.length){
temp[value-1]=ch[i];
System.out.println(String.valueOf(temp));
count++;
}
else
i=ch.length-1;
if(i==ch.length-1){
for(int a=1;a<=value;a++){
if(temp[value-a]!=ch[ch.length-a]){
pos1=a;
break;
}
}
for(int b=0;b<ch.length;b++){
if(temp[value-pos1]==ch[b]){
pos2=b;
break;
}
}
for(int a=pos1,b=pos2;a>0;a--,b++){
temp[value-a]=ch[b+1];
}
System.out.println(String.valueOf(temp));
count++;
if(temp[0]==ch[ch.length-value])
return;
i=pos1+pos2;
}
}
}

复制代码

作者: as604049322 时间: 2015-6-1 16:30
本帖最后由 as604049322 于 2015-6-1 16:33 编辑

探索者发表于 2015-6-1 15:56
不错，但这个程序考虑了顺序的变化，而且如果字符串较大的话，取的数也大一点，会有点问题，例如：combin ...

早知道是不用考虑顺序的我就不用这么蛋疼了。。。

package cn.wangzhe;
import java.util.LinkedList;
/*
在求一个字符串中所有字符的组合的时候，针对一个字符，有两种情况，假设在长度为n的字符串中选择长度为m的组合字符串，
第一是选择长度为n的字符串中的第一个字符，那么要在其余的长度n-1的字符串中选择m-1个字符
第二是不选择长度为n的字符串中的第一个字符，那么要在其余的长度n-1的字符串中选择m个字符
递归结束的条件就是，当m为0，即从字符串中不再选出字符的时候，这个时候已经找到了m个字符的组合，输出即可。
还有一个条件是，当输入的字符串是空，自然是不能从中选出任何字符的。
*/
public class CombinationStr{
public static void main(String[] args) {
// combination("abcd");
combination("abcde",3);
}
public static void combination(String str,int len){
combination("abcde",len,new StringBuilder());
}
private static void combination(String str,int m,StringBuilder result){//c(n,m)
if(m==0){
System.out.print(result+" ");
return ;
}
if(str.length()>0){
result.append(str.charAt(0));
combination(str.substring(1),m-1,result);
result.deleteCharAt(result.length()-1);
combination(str.substring(1),m,result);
}
}
}

复制代码

作者: 张国江 时间: 2015-6-1 17:48
难度系数大，思考思考！！！

作者: 探索者 时间: 2015-6-1 21:06

as604049322 发表于 2015-6-1 16:30
早知道是不用考虑顺序的我就不用这么蛋疼了。。。

感觉考虑顺序比较麻烦，不过做出了不用考虑顺序的程序，再做个可以进行全排的，结合起来就和你那个的效果差不多了

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2