|
锁定老帖子 主题：合并字符串中所有的子字符串
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-06-10
zha_zi 写道
网上看了一个面试题，感觉挺有意思，试着实现了一下，如下代码 package sort;
/**
* @author ty93
* @难度 ***
* @算法： 合并一个字符串中的所有子字符串 例如12342343454565678789->123456789
*/
public class StringCombin {
public static String fatherString = "";
public static String getString(String str) {
String stmp = "";
int i;
c: for (i = fatherString.length(); i < str.length(); i++) {
if (fatherString.contains(String.valueOf(str.charAt(i)))) {
int origin = i;
int j;
if (i == str.length() - 1) {
String tempString = str.substring(str.length() - 2);
if (!fatherString.contains(tempString))
fatherString += tempString;
break;
} else if (i == str.length()) {
fatherString += str.substring(str.length() - 1);
break;
}
for (j = origin + 1; j < str.length(); j++) {
String innString = str.substring(origin, j);
if (fatherString.contains(innString)) {
} else {
if (j - origin > 2) {
StringBuffer sb = new StringBuffer(str);
stmp = sb.delete(origin, j - 1).toString();
fatherString = "";
break c;
} else {
stmp = str;
fatherString = fatherString
+ str.substring(origin, j - 1);
break;
}
}
}
} else {
fatherString = fatherString + String.valueOf(str.charAt(i));
}
}
if (i == str.length()) {
return fatherString;
}
System.out.println(stmp + "_" + fatherString);
return getString(stmp);
}
public static void main(String[] args) {
StringBuffer str = new StringBuffer("12342343454565678789");
System.out.println(getString(str.toString()));
}
}
又是合并算法的运用 |
| 返回顶楼 | |
|
发表时间：2011-06-10
zha_zi 写道
网上看了一个面试题，感觉挺有意思，试着实现了一下，如下代码 package sort;
/**
* @author ty93
* @难度 ***
* @算法： 合并一个字符串中的所有子字符串 例如12342343454565678789->123456789
*/
public class StringCombin {
public static String fatherString = "";
public static String getString(String str) {
String stmp = "";
int i;
c: for (i = fatherString.length(); i < str.length(); i++) {
if (fatherString.contains(String.valueOf(str.charAt(i)))) {
int origin = i;
int j;
if (i == str.length() - 1) {
String tempString = str.substring(str.length() - 2);
if (!fatherString.contains(tempString))
fatherString += tempString;
break;
} else if (i == str.length()) {
fatherString += str.substring(str.length() - 1);
break;
}
for (j = origin + 1; j < str.length(); j++) {
String innString = str.substring(origin, j);
if (fatherString.contains(innString)) {
} else {
if (j - origin > 2) {
StringBuffer sb = new StringBuffer(str);
stmp = sb.delete(origin, j - 1).toString();
fatherString = "";
break c;
} else {
stmp = str;
fatherString = fatherString
+ str.substring(origin, j - 1);
break;
}
}
}
} else {
fatherString = fatherString + String.valueOf(str.charAt(i));
}
}
if (i == str.length()) {
return fatherString;
}
System.out.println(stmp + "_" + fatherString);
return getString(stmp);
}
public static void main(String[] args) {
StringBuffer str = new StringBuffer("12342343454565678789");
System.out.println(getString(str.toString()));
}
}
尽量少层for循环，这样才不会死机
|
| 返回顶楼 | |
|
发表时间：2011-06-10
zha_zi 写道
网上看了一个面试题，感觉挺有意思，试着实现了一下，如下代码 package sort;
/**
* @author ty93
* @难度 ***
* @算法： 合并一个字符串中的所有子字符串 例如12342343454565678789->123456789
*/
public class StringCombin {
public static String fatherString = "";
public static String getString(String str) {
String stmp = "";
int i;
c: for (i = fatherString.length(); i < str.length(); i++) {
if (fatherString.contains(String.valueOf(str.charAt(i)))) {
int origin = i;
int j;
if (i == str.length() - 1) {
String tempString = str.substring(str.length() - 2);
if (!fatherString.contains(tempString))
fatherString += tempString;
break;
} else if (i == str.length()) {
fatherString += str.substring(str.length() - 1);
break;
}
for (j = origin + 1; j < str.length(); j++) {
String innString = str.substring(origin, j);
if (fatherString.contains(innString)) {
} else {
if (j - origin > 2) {
StringBuffer sb = new StringBuffer(str);
stmp = sb.delete(origin, j - 1).toString();
fatherString = "";
break c;
} else {
stmp = str;
fatherString = fatherString
+ str.substring(origin, j - 1);
break;
}
}
}
} else {
fatherString = fatherString + String.valueOf(str.charAt(i));
}
}
if (i == str.length()) {
return fatherString;
}
System.out.println(stmp + "_" + fatherString);
return getString(stmp);
}
public static void main(String[] args) {
StringBuffer str = new StringBuffer("12342343454565678789");
System.out.println(getString(str.toString()));
}
}
如果是有多层for循环的，考虑以下其他算法吧
|
| 返回顶楼 | |
|
发表时间：2011-06-10
两层for不算多了
|
| 返回顶楼 | |
|
发表时间：2011-06-10
zha_zi 写道 两层for不算多了
合并算法 |
| 返回顶楼 | |
|
发表时间：2011-06-10
哦 我明白你的意思了 呵呵 我对于这个命题理解错了
|
| 返回顶楼 | |
|
发表时间：2011-06-10
public static void main(String[] args) {
String strs="12342343454565678789"; Test t=new Test(); ArrayList<String> list= t.getStr(strs); ArrayList<String> listtwo=new ArrayList<String>(); for(int i=0;i<list.size();i++){ String s= strs.substring(i+1,strs.length()); boolean b= s.contains(list.get(i)); if(!b){ listtwo.add(list.get(i)); } } String ss=""; for(String str:listtwo){ ss=ss+str; } System.out.println(ss); } public ArrayList<String> getStr(String str){ ArrayList<String> arry=new ArrayList<String>(); for(int i=0;i<str.length();i++){ arry.add(str.substring(i,i+1)); } return arry; } |
| 返回顶楼 | |
|
发表时间：2011-06-11
首先要确定这个字串的定义 以及如何确定剔除算法
例如 一个字符也算字串的话就变成剔除重复字符了. 再以异常哥的说法双字以上为子串 剔除的时候就有两种 1.在剔除的时候是找到子串就剔除 1345134 剔除的是13 结果就是 13454 2.找到第一次最长字串再剔除 这时候剔除的就是134 结果是 1345 所以说这个题出的很不严谨... |
| 返回顶楼 | |
|
发表时间：2011-06-11
最后修改：2011-06-11
public static void main(String[] args) {
// TODO Auto-generated method stub
String str="12342343454565678789";
System.out.println(sort(str,0));
}
public static String sort(String str,int i){
if(i>=str.length()){
return str;
}else{
String s=String.valueOf(str.charAt(i));
str=str.replaceFirst(s, "#@#");
System.out.println("the s:"+s);
str=str.replaceAll(s, "");
str=str.replaceFirst("#@#", s);
return sort(str,++i);
}
}
|
| 返回顶楼 | |
|
发表时间：2011-06-11
楼主你的代码怎么在mian方法中打印那段 怎么打印n个出来！
|
| 返回顶楼 | |
暂不支持特殊字符~~