面试题求答案
public ArrayList getChar(String str){
}
要求算出一个字符串的多种不同的组合形式。
比如："abcd" 可以算出a,b,c,d,ab,ac,ad,abc,acd,bc,bd,bcd,cd,abcd
问题点数：20、回复次数：39Top
1 楼Hmilyl（水源越来越像天涯～～）回复于 2006-08-06 17:15:02 得分 0
这个不难罢 自己先想一下罢Top
2 楼my6cncn（）回复于 2006-08-06 17:21:07 得分 0
L=getLength()
CL1(排列组合)
CL2(其中L是长度)
或者PllTop
3 楼wangbiao（卡卡西）回复于 2006-08-06 17:27:45 得分 0
具体写一下阿 小弟没做出来Top
4 楼zx2002027（http://www.netyi.net/in.asp?id=zx2002027）回复于 2006-08-06 17:35:03 得分 0
有重复字符怎么处理
如aba
Top
5 楼my6cncn（）回复于 2006-08-06 17:40:41 得分 0
应该用math包里的
排列组合计算！
看数学了！呵呵
http://my.6cncn.cnTop
6 楼magi803（magi）回复于 2006-08-06 17:46:51 得分 0
public ArrayList getChar(String str){
int strlen=str.length;
for(int i=0;i<strlen;i++){
for(int j=0;j<strlen;j++){
}
}
Top
7 楼magi803（magi）回复于 2006-08-06 17:47:22 得分 0
我还没写完,按错键,发上去了Top
8 楼mt_sea（学习ING）回复于 2006-08-06 18:02:37 得分 0
我就是写着看看!
结果是对.但需要改进
你自己改吧!
String str = "abcde";
int length = str.length();
for(int i=0;i<length;i++){
System.out.println(str.substring(i, i + 1));
}
for (int j = 0; j < length ; j++) {// 首字母
for (int i = 1; i < length - 1; i++) {// 字符串个数
for (int k = j; k < length - i; k++) {//
System.out.println(str.substring(j, j + 1)
+ str.substring(k + 1, k + i + 1));
}
}
}
System.out.println(str);Top
9 楼jobs002（Oh! Office）回复于 2006-08-06 18:09:46 得分 0
这个问题关注一下Top
10 楼hbwhwang（【生病了，好好休息中...】）回复于 2006-08-06 19:06:43 得分 0
算法应该是这样的：
在每个字符之间，有2种选择：(1)没有间隔(2)有间隔，那么可以算出，可以穷举的可能共有2的n-1次方(n是字符的个数)
用一个循环把所有的可能性过一遍。每个可能性把“没有间隔”的字符串合并。
Top
11 楼hbwhwang（【生病了，好好休息中...】）回复于 2006-08-06 19:24:08 得分 0
import java.util.*;
public class InciseString {
private static void process(char[] c,int[] p,Set a){
String temp=""+c[0];
for (int i=0;i<p.length;i++){
if (p[i]==0){
temp+=c[i+1];
}else{
a.add(temp);
temp=""+c[i+1];
}
}
a.add(temp);
}
private static boolean isLast(int[] operator){
for (int i=operator.length-1;i>=0;i--){
operator[i]++;
if (operator[i]>=2){
operator[i]=0;
}else{
return false;
}
}
return true;
}
public static ArrayList getChar(String str) {
Set s=new TreeSet();
char[] c=str.toCharArray();
int[] p=new int[c.length-1];
do {
process(c,p,s);
}while(!isLast(p));
ArrayList a=new ArrayList(s);
return a;
}
public static void main(String[] args) {
System.out.println(getChar("abcd"));
}
}Top
12 楼wangbiao（卡卡西）回复于 2006-08-06 21:44:16 得分 0
楼上的解法不对答案不完全
高人指点阿
Top
13 楼hbwhwang（【生病了，好好休息中...】）回复于 2006-08-06 21:48:57 得分 0
sorry,看错题目了。
等下有空再来Top
14 楼yandebin2006（成长ing）回复于 2006-08-06 22:09:02 得分 0
import java.lang.*;
import java.io.*;
public class NubOfSubString{
public static void main(String[] args){
InputStreamReader isr=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(isr);
String str=new String("");
Transmit trm=new Transmit();
System.out.println("输入要组合的字符串：");
try {
str=br.readLine();
br.close();
}catch(IOException e){}
System.out.println("输出组合后的字符串:\n"+trm.getSubstring(str));
}
}
class Transmit{
public String getSubstring(String st){
String substrings=new String("");
String s=new String(st);
int numbs=1;
for(int i=0;i<st.length();i++)numbs=numbs*2;//得出所有组合的个数
for(int i=1;i<=numbs-1;i++){
String sr=Integer.toBinaryString(i);//换成2进制数值串
for(int j=0;j<st.length()-1&&sr.length()<st.length();j++){
sr="0"+sr;
}//位数不够的补零，统一成标准的位数，便于形成一对一的映射关系
for(int k=0;k<sr.length();k++){
if(sr.charAt(k)=='1')
substrings=substrings+Character.toString(st.charAt(k));
}//字符1对应的位置取出
if(i%4==0)substrings=substrings+"\n";
else substrings=substrings+"\t";
}
return substrings;
}
}
//刚写的，有漏洞，不过得的出答案。偶也是JAVA初学者。有机会学习一下。。qq:511498938
Top
15 楼tommyk123（）回复于 2006-08-06 22:09:04 得分 0
import java.util.Vector;
public class StringCal
{
public static void main(String[] args)
{
String str = "abcd";
Vector temp;
cal cc = new cal(str);
temp = cc.Cal();
for(int i= 0; i < temp.size(); i++)
{
System.out.println((String)temp.elementAt(i));
}
}
}
class cal
{
String tempStr;
public cal(String _s)
{
tempStr = _s;
}
public Vector Cal()
{
Vector v = new Vector();
Vector v1= new Vector() ;
v.addElement(tempStr);
String[] str = {};
int count = 0;;
String temp = tempStr;
String oldstr= "";
char[] a = new char[1];
String lastStr = "" ;
int i = 0;
while( i != temp.length())
{
a[0] = temp.charAt(i);
for(int j= 0; j< temp.length();j++)
{
if(a[0] == temp.charAt(j))
{
oldstr = new String(a);
while(temp.indexOf(oldstr) >= 0)
{
if(oldstr.equals(temp.substring(0,1)))
{
lastStr = temp.substring(temp.indexOf(oldstr)+1);
}
else
{
lastStr = temp.substring(0, temp.indexOf(oldstr))
+ temp.substring(temp.indexOf(oldstr) +1);
}
break;
//
}
}
}
v1.removeAllElements();
v1.addElement(lastStr);
//
String hh = " ";
hh = oldstr;
for(int k = 0; k < lastStr.length();k++)
{
v.addElement((String)(hh+lastStr.substring(k)));
count++;
}
//
i++;
}
return v;
}
}Top
16 楼hbwhwang（【生病了，好好休息中...】）回复于 2006-08-06 22:18:45 得分 0
用递归实现：
import java.util.*;
public class InciseString2 {
private static void getSub(ArrayList list,String str){
String substr1=str.substring(0,1);
String substr2=str.substring(1,str.length());
if (substr2.length()>=1){
getSub(list,substr2);
}
int len=list.size();
for (int i=0;i<len;i++){
list.add(substr1+(String)list.get(i));
}
list.add(substr1);
}
public static ArrayList getChar(String str){
ArrayList data=new ArrayList();
getSub(data,str);
return data;
}
public static void main(String[] args) {
ArrayList l=getChar("abcd");
Collections.sort(l,new Comparator(){
public int compare(Object o1, Object o2){
String s1=(String)o1;
String s2=(String)o2;
return s1.length()-s2.length()!=0?(s1.length()-s2.length()):s1.compareTo(s2);
}
});
System.out.println(l);
}
}Top
17 楼wangbiao（卡卡西）回复于 2006-08-06 22:40:40 得分 0
mark
Top
18 楼zliloveu（小刁）回复于 2006-08-06 22:50:35 得分 0
对题目的一点疑问:
1.如果字母重复了怎么处理?比如"abca",怎么算.
2.算出一个字符串的组合形式,比如字符串是"cba",那组合应该是c,b,a,cb,ca,ba,cba还是a,b,c,ab,ac,bc,abc??Top
19 楼NikeUser（NikeUser）回复于 2006-08-06 23:31:51 得分 0
关注Top
20 楼wolaiye3（魔幻之光）回复于 2006-08-07 09:08:26 得分 0
呵呵，这个写足彩分析器时写过，用的是递归，做个记号，一会写Top
21 楼Imain（imain）回复于 2006-08-07 09:13:35 得分 0
upTop
22 楼usxue（尘飞扬）回复于 2006-08-07 09:32:37 得分 0
上面的各位也太复杂了吧，看看我写的这个：
import java.util.ArrayList;
public class Test2 {
/**
* @param args
*/
public static void main(String[] args) {
Test2 te = new Test2();
ArrayList list = te.getChar("abcd");
for(int i=0; i<list.size(); i++) {
System.out.println(list.get(i));
}
}
public ArrayList getChar(String str){
ArrayList<String> nums = new ArrayList<String>();
for(int i=0; i<str.length(); i++) {
int k = nums.size();
for(int j=0; j<k; j++) {
String ss = nums.get(j) + str.substring(i, i+1);
nums.add(ss);
}
nums.add(str.substring(i,i+1));
}
return nums;
}
}Top
23 楼championmajian（小马||目前酒力：白的半斤，啤的3瓶）回复于 2006-08-07 09:52:36 得分 0
关注Top
24 楼jounyc（江湖萧萧生）回复于 2006-08-07 09:57:18 得分 0
markTop
25 楼water621（浅水蛟）回复于 2006-08-07 10:16:36 得分 0
markTop
26 楼MYLiao（醉书生）回复于 2006-08-07 10:16:44 得分 0
markTop
27 楼billmo1986（潘安+宋玉）回复于 2006-08-07 11:44:05 得分 0
markTop
28 楼fredonline（天天挨踢）回复于 2006-08-07 12:41:10 得分 0
第一，楼主给出的题目要求不明确，例子不恰当，因为就“abcd”四个字符来说，排列的种类绝非“a,b,c,d,ab,ac,ad,abc,acd,bc,bd,bcd,cd,abcd”这么少。很明显，既然能有“ac”，为什么不能有“ca”？题目到底有没有要求一定的顺序？
第二，相比来说，很明显，在要求有顺序的时候，这道题比较简单，只需要从头开始取数字即可
所以可以用上面usxue(尘飞扬)的程序，不过要改一下
return new ArrayList((new HashSet(nums)));
目的是在最后return之前去除重复记录，否则输入字符串为“aa”的时候就错了。
如果没有顺序要求，即可出现“ac”和“ca”，则用递归程序，
public ArrayList getChar(String str) {
ArrayList list = new ArrayList();
if (str.length() == 1) {
list.add(str);
} else {
for (int i = str.length() - 1; i >= 0; i--) {
String lastChar = str.substring(i, i + 1);
ArrayList subList = getChar((new StringBuffer(str).deleteCharAt(i)).toString());
for (Iterator iter = subList.iterator(); iter.hasNext();) {
String element = (String) iter.next();
list.add(element);
element = element + lastChar;
list.add(element);
}
}
}
return new ArrayList((new HashSet(list)));
}
递归效率还是非常低的，尤其是在非顺序条件下，8个不同字符就会有109600种结果，当9个不同字符时，我这里就已经OutOfMemoryError了。Top
29 楼hbwhwang（【生病了，好好休息中...】）回复于 2006-08-07 12:45:27 得分 0
fredonline(天天挨踢) ：
递归的效率跟普通函数调用一样，不存在“非常低”的说法！
按楼主题目的意思，很明显是有顺序的。
Top
30 楼fredonline（天天挨踢）回复于 2006-08-07 13:45:35 得分 0
hbwhwang(我是catmiw的马甲)：
谢谢提醒！我错了。
递归只是内存开销比循环的方法大。Top
31 楼wanguanghai（心灵鸡汤）回复于 2006-08-07 15:51:54 得分 0
顶Top
32 楼pcno1（金木水火土）回复于 2006-08-08 18:10:01 得分 0
学习Top
33 楼if_else6789（我可帮不了你！！！）回复于 2006-08-08 18:29:58 得分 0
挺好，还有更简单的方法吗？一会我试试。Top
34 楼kinsey0514（春天的老黄牛）回复于 2006-09-18 07:40:47 得分 0
做个记号
Top
35 楼Areslp（努力ING）回复于 2006-09-18 10:56:08 得分 0
package test;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class CharZuhe {
public static List getChar(String str){
if(str.length()>1){
String s1=str.substring(0,1);
String s2=str.substring(1,str.length());
System.out.println("s1:"+s1);
System.out.println("s2:"+s2);
List l=getChar(s2);
System.out.println("up:l:"+l);
List r=new ArrayList();
Iterator it=l.iterator();
while(it.hasNext()){
String sl=(String)it.next();
String temp=null;
if(sl!=null){
temp=s1+sl;
}else{
temp=s1;
}
r.add(sl);
r.add(temp);
}
System.out.println("r:"+r);
return r;
}else{
List l=new ArrayList();
l.add(str);
l.add(null);
System.out.println("down:l:"+l);
return l;
}
//ArrayList l=getChar(s2);
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("result:"+CharZuhe.getChar("abcd"));
}
}
markTop
36 楼figoren（figoren）回复于 2006-12-22 11:18:27 得分 0
上面求的是5个字母全组合 C51+C52+C53+C54+C55=31 如果是全排列呢 P55=120Top
37 楼uloveu（自己爱自己）回复于 2006-12-23 15:12:23 得分 0
public ArrayList getChar(String str){
ArrayList list = new ArrayList();
int length = str.length();
char tmpChar;
for(int i = 0; i <= length - 1; i++){
tmpChar = str.charAt(i);
list.add(tmpChar + "");
int tmpInt = i + 1;
while(tmpInt < length){
for(int j = tmpInt + 1; j <= length; j++){
list.add(tmpChar + str.substring(tmpInt,j));
}
tmpInt++;
}
}
return list;
}
//写的匆忙，用的循环不太好Top
38 楼nicky_hk（）回复于 2007-01-02 00:12:26 得分 0
mark
Top
39 楼Lt_smile（穷开心）回复于 2007-03-26 20:50:17 得分 0
markTop
