`
zha_zi
  • 浏览: 593204 次
  • 性别: Icon_minigender_1
  • 来自: 西安
社区版块
存档分类
最新评论

合并字符串中所有的子字符串

面试J#算法CC++ 
阅读更多

网上看了一个面试题，感觉挺有意思，试着实现了一下，如下代码

package order;

/**
 * @author ty93
 * @难度   ***
 * @算法： 合并一个字符串中的所有子字符串 例如12342343454565678789->123456789
 *                                         11223344->11223344 
 *                                         123423434545656787898901121512->1234567890115
 */
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)) {
						if (tempString.charAt(0) == tempString.charAt(1)) {
							fatherString += tempString.substring(1);
						} else {
							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.toString() + "_" + fatherString.toString());
		if (stmp != "")
			return getString(stmp);
		return fatherString;
	}

	public static void main(String[] args) {
		StringBuffer str = new StringBuffer("123423434545656787898901121512");
		System.out.println(getString(str.toString()));
	}
}

分享到：
| ecplise下配置c++运行环境
评论
27 楼 zha_zi 2011-06-14  
luwenbin006 写道
楼主你的代码怎么在mian方法中打印那段 怎么打印n个出来！

  System.out.println(stmp + "_" + fatherString); 我自己测试用的， 把这一句去掉就ok了
26 楼 zp820705 2011-06-14  
不可以用StringBuffer?

public class Wuliao_StringCombin
{
   
    public static void main(String[] args)
    {
        System.out.println(Wuliao_StringCombin.getStringCombin("asdfasdf12341234"));
    }
   
   
    public static String getStringCombin(String source){
        StringBuffer target = new StringBuffer(source.length());
        for(int i=0;i<source.length();i++){
            char ch = source.charAt(i);
            if(target.toString().indexOf(ch) == -1){
                target.append(ch);
            }
        }
       
        return target.toString();
    }
}
25 楼 zk7019311 2011-06-13  
看了这么多讨论，好像不明确啊
24 楼 zhouxi1987 2011-06-13  
<div class="quote_title">loookto 写道</div>
<div class="quote_div">
<pre name="code" class="java">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&gt;=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);
}
}</pre>
<p> <img src="/images/smiles/icon_sad.gif" alt="">暂不支持特殊字符~~</p>
</div>
<p> 和我思路差不多</p>
<pre name="code" class="java"> public static void main(String[] args) {  
String str="12342343454565678789";
         
System.out.println(sort(null,str));  
}

public static String sort(StringBuffer sb,String str){
   if(sb==null){
   sb=new StringBuffer();
   }
       if("".equals(str)){  
           return sb.toString();  
        }else{
        String s=String.valueOf(str.charAt(0));
        //System.out.println("the s:"+s);
        sb.append(s); 
           str=str.replaceAll(s, "");  
            return sort(sb,str);  
        }  
   }  </pre>
23 楼 king_唐 2011-06-12  
我也来一个 
	public static void merge(String str) {
		StringBuffer sb = new StringBuffer(str) ;
		for(int i=0;i<sb.length();i++) {
			int index = sb.indexOf(String.valueOf(sb.charAt(i)), (i+1)) ;
			while(index != -1) {
				sb.deleteCharAt(index) ;
				index = sb.indexOf(String.valueOf(sb.charAt(i)),index) ;
			}
		}
		
		System.err.println(sb.toString());
	}
22 楼 xxinsong 2011-06-12   
public static void main(String[] args) {
		String str = "112233444556778899";
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < str.length(); i++) {
			String s = String.valueOf(str.charAt(i));
			if (sb != null) {
				if (i == 0) {
					sb.append(s);
				}else{
					if (sb.indexOf(s) != -1) {
						continue;
					} else {
						sb.append(s);
					}
				}
			}
		}
		System.out.println(sb.toString());
	}
21 楼 rola 2011-06-12  
ptma 写道
其实就是去除重复字符，原字符串里面的单个字符也是子串。

利用HashMap 
public static String getString(String str) {
		Map<String,String> strMap = new LinkedHashMap<String,String>();
		for (int i = 0; i < str.length(); i++) {
			String ch = String.valueOf(str.charAt(i));
			if(!strMap.containsKey(ch)){
				strMap.put(ch, ch);
			}
		}

		StringBuffer sb = new StringBuffer();
		Set<Entry<String, String>> entrySet = strMap.entrySet();
		for (Entry<String, String> entry : entrySet) {
			sb.append(entry.getValue());
		}
		return sb.toString();
	}



程序有问题
随便给个字符串“123423543454565678789”
20 楼 enefry 2011-06-11  
感觉和 lzw算法的字典法有相似之处.
19 楼 luwenbin006 2011-06-11  
楼主你的代码怎么在mian方法中打印那段 怎么打印n个出来！
18 楼 loookto 2011-06-11  
<pre name="code" class="java">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&gt;=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);
}
}</pre>
<p> <img src="/images/smiles/icon_sad.gif" alt="">暂不支持特殊字符~~</p>
17 楼 uin57 2011-06-11  
首先要确定这个字串的定义 以及如何确定剔除算法
例如
一个字符也算字串的话就变成剔除重复字符了.
再以异常哥的说法双字以上为子串
剔除的时候就有两种
1.在剔除的时候是找到子串就剔除 1345134 剔除的是13  结果就是 13454
2.找到第一次最长字串再剔除 这时候剔除的就是134  结果是 1345
所以说这个题出的很不严谨...
16 楼 cd_cd 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;
}
15 楼 wanbin021614 2011-06-10  
哦 我明白你的意思了 呵呵 我对于这个命题理解错了
14 楼 shanga 2011-06-10  
zha_zi 写道
两层for不算多了

合并算法
13 楼 zha_zi 2011-06-10  
两层for不算多了
12 楼 shanga 2011-06-10  
<div class="quote_title">zha_zi 写道</div>
<div class="quote_div">
<p>网上看了一个面试题，感觉挺有意思，试着实现了一下，如下代码</p>
<pre name="code" class="java">package sort;

/**
* @author ty93
* @难度   ***
* @算法： 合并一个字符串中的所有子字符串 例如12342343454565678789-&gt;123456789
*/
public class StringCombin {
public static String fatherString = "";

public static String getString(String str) {
String stmp = "";
int i;
c: for (i = fatherString.length(); i &lt; 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 &lt; str.length(); j++) {
String innString = str.substring(origin, j);
if (fatherString.contains(innString)) {
} else {
if (j - origin &gt; 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()));
}
}
</pre>
如果是有多层for循环的，考虑以下其他算法吧 </div>
<p> </p>
11 楼 shanga 2011-06-10  
<div class="quote_title">zha_zi 写道</div>
<div class="quote_div">
<p>网上看了一个面试题，感觉挺有意思，试着实现了一下，如下代码</p>
<pre name="code" class="java">package sort;

/**
* @author ty93
* @难度   ***
* @算法： 合并一个字符串中的所有子字符串 例如12342343454565678789-&gt;123456789
*/
public class StringCombin {
public static String fatherString = "";

public static String getString(String str) {
String stmp = "";
int i;
c: for (i = fatherString.length(); i &lt; 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 &lt; str.length(); j++) {
String innString = str.substring(origin, j);
if (fatherString.contains(innString)) {
} else {
if (j - origin &gt; 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()));
}
}
</pre>
  尽量少层for循环，这样才不会死机</div>
<p> </p>
10 楼 shanga 2011-06-10  
<div class="quote_title">zha_zi 写道</div>
<div class="quote_div">
<p>网上看了一个面试题，感觉挺有意思，试着实现了一下，如下代码</p>
<pre name="code" class="java">package sort;

/**
* @author ty93
* @难度   ***
* @算法： 合并一个字符串中的所有子字符串 例如12342343454565678789-&gt;123456789
*/
public class StringCombin {
public static String fatherString = "";

public static String getString(String str) {
String stmp = "";
int i;
c: for (i = fatherString.length(); i &lt; 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 &lt; str.length(); j++) {
String innString = str.substring(origin, j);
if (fatherString.contains(innString)) {
} else {
if (j - origin &gt; 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()));
}
}
</pre>
 </div>
<p>又是合并算法的运用</p>
9 楼 zha_zi 2011-06-10  
wanbin021614 写道
这道面试题肯定不是让你用set来实现的。 这属于jdk自带功能，本来就是要考你的想法

贴个自己写的 没考虑那么多 总之是实现了功能 

   /**
     * 合并一个字符串中的所有子字符串 例如12342343454565678789->123456789 
     * 
     * @param input
     * @return merge result
     */
    public static String mergeAll(String input) {
        final int length = input.length();
        char[] output = new char[length];
        final char[] inputArr = input.toCharArray();
        int i = 0;
        int index = 0;
        for (char c : inputArr) {
            boolean exist = false;
            for (int j = 0; j < i; j++) {
                if (inputArr[j] == c) {
                    exist = true;
                    break;
                }
            }
            if (!exist) {
                output[index++] = c;
            }
            i++;
        }
        return new String(output).trim();
    }



要求是剔除重复的子字符串，
我认为剔除的过程 例如
13456234523745892375923857
下边是人工剔除步骤
步骤1：13456234523745892375923857 剔除345得到结果   13456223745892375923857
    2：13456223745892375923857    剔除45得到结果    134562237892375923857  
    3：134562237892375923857      剔除237得到结果   134562237895923857     
    4：134562237895923857         剔除23 得到结果   1345622378959857   
最后结果是  1345622378959857   
     得到结果1345622378959857 这个结果才是没有含有任何重复的子字符串
而且要考虑剔除节点的问题，和字符串末尾的处理


    

8 楼 wanbin021614 2011-06-10  
没有这么面试的。。。如果用set会明说

freish 写道
说不定人家就是考你set相关内容呢？！不要乱揣测


zha_zi 写道
抛出异常的爱 写道
ptma 写道
其实就是去除重复字符，原字符串里面的单个字符也是子串。

利用HashMap 
public static String getString(String str) {
		Map<String,String> strMap = new LinkedHashMap<String,String>();
		for (int i = 0; i < str.length(); i++) {
			String ch = String.valueOf(str.charAt(i));
			if(!strMap.containsKey(ch)){
				strMap.put(ch, ch);
			}
		}

		StringBuffer sb = new StringBuffer();
		Set<Entry<String, String>> entrySet = strMap.entrySet();
		for (Entry<String, String> entry : entrySet) {
			sb.append(entry.getValue());
		}
		return sb.toString();
	}


双字以上才叫子串吧。。。。

我感觉应该是双字或者以上才能叫字符串，应该是不能用set不然这道题的难度就大打折扣了，


发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    字符串的操作， 字符串的合并 截取

    - **查找**：`find()`函数用于查找子字符串在主字符串中的位置，`find_last_of()`查找指定字符或子字符串最后一次出现的位置。 - **替换**：`replace()`函数可以替换字符串的一部分。例如，`str.replace(pos, len, ...

    sql 多行合并某一列字符串拼接的示例

    这个函数主要用于替换字符串中的子串，但通过巧妙的应用，它也可以实现字符串的拼接。在上述示例中，`STUFF()`函数被用作多行字符串拼接的关键技术。 #### 示例解析 考虑以下SQL查询： ```sql SELECT Year, week1,...

    合并字符串和统计字符串出现的次数

    上述例子中，`count()`方法返回了子字符串"Python"在原始字符串中出现的次数。需要注意的是，`count()`方法区分大小写，所以如果需要不区分大小写地统计，我们需要先将字符串转换为全大写或全小写。 除了`count()`...

    QT中字符串的比较、查找、替换等操作 - 大存的博客1

    可以使用`indexOf()`或`lastIndexOf()`函数来查找子字符串在主字符串中的位置，如果找到则返回起始位置索引，否则返回-1。 9. **分割字符串**： `split()`函数可以按照指定的分隔符将字符串分割成字符串列表，这...

    十六进制字符串至普通转化_十六进制字符串转普通字符串_labview十六进制_

    4. 合并字符：将得到的ASCII字符合并成一个字符串输出。 在提供的"16至普通转化.vi"虚拟仪器中，很可能包含了实现这些步骤的子VI或函数。打开这个VI，我们可以看到其内部结构，通常会有一个循环来处理每个十六进制...

    vb字符串分隔与合并的程序实例

    VB中用于合并字符串的主要方法是`Join()`函数，它接收一个字符串数组和可选的分隔符，然后返回一个由数组元素连接成的新字符串。例如，如果我们有之前分隔得到的`fruits`数组，可以使用以下代码合并它们： ```vb ...

    linux下c字符串操作常用方法

    `strchr()`函数用于查找子串的第一个字符，`strstr()`则可以查找子串在整个字符串中的位置。结合这两个函数，我们可以方便地提取子字符串。 4. 大小写转换： 使用`tolower()`和`toupper()`函数可以轻松实现字符的...

    在一个以知的字符串中截取满足一定条件的字符串

    在本篇文章中，我们将深入探讨如何在一个已知的字符串中截取满足特定条件的子字符串。这个主题在软件开发和编程领域中极为常见，尤其是在处理大量文本数据时。通过具体的例子，我们将逐步解析如何实现这一功能，并...

    python字符串学习笔记.python字符串操作方法.doc

    - `replace()`用于替换字符串中的子字符串，例如`'hello'.replace('l', 'x')`返回`'hexxo'`。 - `split()`, `rsplit()`, `splitlines()`用于分割字符串，`partition()`, `rpartition()`找到子字符串并返回三部分。...

    修改过后的字符串处理程序

    - **替换（Replace）**：用新的字符串替换原字符串中的某个或所有子字符串。 - **插入（Insert）**：在字符串的特定位置插入新的字符或字符串。 - **删除（Delete）**：删除字符串中的特定字符或子字符串。 - **反转...

    VB源码：字符串分隔与合并的程序实例.rar

    这个函数将一个字符串按照指定的分隔符切分为多个子字符串，返回一个数组。例如，如果有一个字符串`str = "apple,banana,orange"`，我们可以使用逗号作为分隔符，如下所示： ```vb Dim str As String = "apple,...

    字符串操作封装函数

    3. **查找与替换**：`find()`和`replace()`函数分别用于查找子字符串的位置和替换子字符串。 4. **大小写转换**：`upper()`、`lower()`和`title()`函数可以将字符串转换为全大写、全小写和首字母大写的形式。 5. **...

    字符串操作完全演示

    - `replace(old, new)`：替换字符串中所有出现的`old`子串为`new`。 - `split(separator)`：根据`separator`分隔字符串并返回子字符串列表。 - `join(iterable)`：使用字符串作为连接符，合并`iterable`中的元素成新...

    C#字符串处理的所有函数

    - 截取子字符串：`string subStr = str.Substring(startIndex, length);` 4. **字符串比较** - `==`运算符：比较字符串内容是否相等，不区分大小写。 - `Equals()`方法：区分和不区分大小写的比较。 - `Compare...

    java 分割字符串

    在Java编程语言中，分割字符串是一项常见的操作，它允许我们将一个长字符串分解成多个子字符串，每个子字符串对应原字符串中的某一部分。这通常通过使用`split()`方法来实现，该方法是`String`类的一个实例方法。让...

    JS实现字符串中去除指定子字符串方法分析

    在JavaScript中，处理字符串是一项常见的任务，而去除字符串中的指定子字符串则是其中的一个重要操作。本文将详细介绍两种主要的方法来实现这一功能：使用`replace()`函数和通过字符串的`split()`与`join()`组合使用...

    字符串检测VC

    减法操作通常不适用于字符串，因为字符串是不可变的，但我们可以创建一个新的字符串，从一个字符串中去除另一个字符串的部分。 2. **空串判断**： 判断一个字符串是否为空有多种方法。对于字符数组，我们可以检查...

    javascript将字符串中的多个空格替换为一个空格的正则实例.docx

    ### JavaScript将字符串中的多个空格替换为一个空格的正则实例 在Web开发与日常编程中，我们经常需要处理字符串。特别是在用户输入或者文本处理过程中，常常会遇到需要清理字符串中的多余空格的情况。例如，当从...

    字符串处理的12个例子

    `str.find(substring)`用于查找子字符串在原字符串中的位置，返回第一个匹配的起始索引；如果未找到，则返回-1。 6. **字符串替换**： `str.replace(old, new)`方法可以将字符串中的某个子串替换为新的子串。 7....

Magicbox
Global site tag (gtag.js) - Google Analytics