`
zha_zi
  • 浏览: 584734 次
  • 性别: 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不然这道题的难度就大打折扣了，


发表评论

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

相关推荐

    合并字符串.vi

    软键盘vi，一维数组转换为符号分隔字符串vi等的子vi

    Visual C# 2005编程技巧大全源代码(第五部分)

    206. 如何从分隔符字符串中析取子字符串 207. 如何合并字符串数组中的字符串元素 208. 如何在字符串中删除指定的子字符串 209. 如何在字符串中替换指定的子字符串 210. 如何在字符串中附加格式化的字符串 211. ...

    将子表信息合并为一个字符串的例子

    举个例子，如何实现将子表的数据与主表数据显示在一起。

    二级上机真题例典—编程

    全国计算机等级考试二级C上机题例典 ...子字符串查找 字符统计 字符串逆置 回文数 数字字符串转换成整数 比较字符串长度 子字符串移动 字符串连接 在链表中查找元素 结构体和链表排序 求链表中的极值

    mufasa：μJS有限状态自动机字符串分析器

    μFASA（μJS有限状态自动机字符串分析器）是一种基于静态解释的字符串静态分析器，用于JavaScript的子语言μJS的跨过程版本。 有关μFASA的完整详细信息，请参见第七届国际验证和程序转换研讨会（VPT 2019）上介绍...

    oracle学习文档 笔记 全面 深刻 详细 通俗易懂 doc word格式 清晰 连接字符串

     删除HKEY_CURRENT_USER/SOFTWARE/Microsoft/windows/CurrentVersion/Explorer/MenuOrder/Start Menu/Programs中所有以oracle 开头的键。  删除HKDY_LOCAL_MACHINE/SOFTWARE/ODBC/ODBCINST.INI中除Microsoft ...

    Competitive-Programming:使用C ++解决的每个编码问题的主列表

    打印字符串的所有子字符串 查找二维数组中总和最大的行或列 以正弦波顺序打印2D阵列的元素 以螺旋形式打印2D阵列的元素 检查两个字符串是否彼此置换 从适当的字符串中删除连续的重复字符 反转字符串中的每个单词 从...

    CCJ多功能文件处理与编译器-&amp;amp;amp;gt;可将图片与文字编译成bin文件直接下载到MCU中

    * 字符串常量编译 将不同长度的字符串常量信息，按“可选字符串个数 + 索引头阵列 + 字符串数据”方式编译为一个bin文件 * 图片转换与图片数据提换功能：提取.wbm/.bmp/.gif/.png格式中的，纯图像数据，供嵌入式...

    LeetCode解题总结

    3.16 反转字符串中的单词 3.16.1 字符串前后和中间可能存在多个空格 3.16.2 不存在前后和中间的多余空格 3.17 一个编辑距离 4. 栈 4.1 验证括号的正确性 4.2 最长的正确括号表达式 4.3 柱状图中的最大矩形面积 4.4 ...

    LeetCode判断字符串是否循环-leetcode-js:我用JavaScript编写的leetcode答案

    LeetCode判断字符串是否循环 leetcode-js My leetcode answers written in JavaScript. # 题目 解答 难度 备注 1 两数之和 简单 2 两数相加 中等 3 无重复字符的最长子串 中等 4 寻找两个有序数组的中位数 困难 7 ...

    LeetCode题目分类与面试问题整理，附带所有java算法代码

    q387_字符串中的第一个唯一字符 链表操作 q2_两数相加 q19_删除链表的倒数第N个节点 q25_k个一组翻转链表 q61_旋转链表 q138_复制带随机指针的链表 q160_相交链表 q206_反转链表 双指针遍历/滑动窗口 q3_无重复字符...

    leetcode卡-leetCodeByPython:用python刷leetCode初级题目

    字符串中的第一个唯一字符 有效的字母异位词 验证回文字符串 字符串转换整数 (atoi) 实现 strStr() 报数 最长公共前缀 3.链表 删除链表中的节点 删除链表的倒数第N个节点 反转链表 合并两个有序链表 回文链表 环形...

    LeetCode判断字符串是否循环-leetcode:麦铭熙的LeetCode做题记录

    LeetCode判断字符串是否循环 LeetCode 解题记录 编号 名称 完成日期 简要题解 难度 0001 两数之和 2020-07-26 暴力算法 ★ 0007 整数反转 2020-08-02 字符串，类型转换 ★ 0008 字符串转换整数 2021-02-07 经典字符...

    30个初级常用python实现脚本 中文pdf高清版

    6、把一个list中所有的字符串变成小写： 7、输出某个路径下的所有文件和文件夹的路径 8、输出某个路径及其子目录下的所有文件路径 9、输出某个路径及其子目录下所有以.html为后缀的文件 10、把原字典的键值对颠倒并...

    西工大noj答案完整版.doc

    61.合并字符串 62.猴子分桃 63.火车站 64.获取指定二进制位 65.积分计算 66.级数和 67.计算A+B 68.计算PI 69.计算π 70.计算成绩 71.计算完全数 72.检测位图长宽 73.检查图像文件格式 74.奖金发放 75.阶乘合计 76.解...

    关于C的精粹包含至少200个C语言小程序

    172 删除字符串中的特定字符 173 求解符号方程 174 计算标准差 175 求取符合特定要求的素数 176 统计符合特定条件的数 177 字符串倒置 178 部分排序 179 产品销售记录处理 180 特定要求的字符编码 181 求解...

    字符串整数的余数leetcode-google-interview-questions:谷歌面试问题

    字符串可能的余数数组问题 在所有对中找到不同的位总和。 技巧：对于每一位扫描数组中的所有元素。 O(n.64) 求和等于 k ​​的连续子数组的总数。 技巧：如果整数是非负的，则开窗解决方案。 否则创建 sums 数组并...

    LeetCode题目分类与面试问题整理

    q387_字符串中的第一个唯一字符 链表操作 q2_两数相加 q19_删除链表的倒数第N个节点 q25_k个一组翻转链表 q61_旋转链表 q138_复制带随机指针的链表 q160_相交链表 q206_反转链表 双指针遍历/滑动窗口 q3_无重复字符...

    LeetCode判断字符串是否循环-data-structure-and-algo:C++中的数据结构和算法

    LeetCode判断字符串是否循环 data-structure-and-algo 以C++语言实现了一些常用算法。为了方便调试，每个cpp文件都单独可以运行。...：字符串的翻转转和循环左移、单词翻转、最长公共子序列、最长递增

    最大公共字符串leetcode-lc:液晶显示器

    最大公共字符串leetcode leetcode 关键词： interview 最长回文子串硬币问题 目标 大批 O -&gt; 尝试 agaub X -&gt; 失败 二和 - 买卖股票的最佳时机 - 包含重复 - 数组除自身的乘积 - 最大子阵列 - 最大乘积子阵列 - 在...

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