笔试题之一:字符串相关问题
1、字符的左右移动
给定一个字符串，这个字符串为*号和26个字母的任意组合。现在需要把字符串的*号都移动到最左侧，而把字符串中的字母移动到最右侧并保持相对顺序不变，要求时间复杂度和空间复杂度最小。
分析：用point表示尾部的第一个*的位置， 然后从point出发,用指针let指向point之前的第一个字母，依次交换point和let指向的元素，再继续找下一个*和字母的序列，直到point和let有一个指向字符串的首地址。
要从后往前扫描，把距*最近的字母相交换，这样可以保证后面的字母交换后，仍然在后面。
java代码如下：
import java.util.*;
class moveStr
{
public static void moveChar(char[] ch,int len)
{
int point=len-1;
int let=len-1;
while(point!=0&&let!=0)
{
while(ch[point]!='*'&&point!=0) //first * from the end
{
point--;
}
if(point==0) //all ch are *
return;
let=point;
while(ch[let]=='*'&&let!=0) //the first letter before *
{
let--;
}
while(ch[let]!='*'&&ch[point]=='*')
{
char tem=ch[let];
ch[let]=ch[point];
ch[point]=tem;
if(point!=0)
point--;
if(let!=0)
let--;
}
}
}
public static void main(String[] args)
{
String str="abc**gh*58*r";
char[] ch=str.toCharArray();
moveChar(ch,str.length());
System.out.println(ch);
}
}
2、字符串反转
实现字符串反转函数。例如，"July"反转后变成"yluJ"。
1)首先使用字符数组遍历字符串长度一半就可以实现:
public static string ReverseByCharBuffer(string original)
{
char[] c = original.ToCharArray();
int l = original.Length;
for (int i = 0; i < l / 2; i++)
{
char t = c[i];
c[i] = c[l - i - 1];
c[l - i - 1] = t;
}
return new string(c);
}
2).栈是一个很神奇的数据结构。我们可以使用它后进先出的特性来对数组进行反 转。先将数组所有元素压入栈，然后再取出，顺序很自然地就与原先相反了。
public static string ReverseByStack(this string original)
{
Stack<char> stack = new Stack<char>();
foreach (char ch in original)
{
stack.Push(ch);
}
char[] c = new char[original.Length];
for (int i = 0; i < original.Length; i++)
{
c[i] = stack.Pop();
}
return new string(c);
}
3)其他方法参考此网址:http://blog.sina.com.cn/s/blog_6997f0150100tpse.html
3、字符串整体反转,单词不反转
写一个函数，将字符串翻转，翻转方式如下：“I am a student”反转成“student a am I”，不借助任何库函数。
分析:利用正则表达式"\\W+"分割字符串成字符串数组,然后从后向前重新排序
public static String reverse(String word){
String[] arr = word.split("\\W+");
StringBuffer sb = new StringBuffer();
int len = arr.length;
for(int i=len-1;i>=0;i--){
sb.append(arr[i]).append(" ");
}
return sb.substring(0,sb.length()-1);
}
如果用C++等写程序:方法是先反转整个字符串，然后再反转字串;但是代码写起来很费劲的.
4、字符个数的统计
给定一个字符串，写一个函数，查找出字符串中每个字符出现的次数，要求区分大小写，且时间复杂度为O(n)。
5、字符串的匹配
在一篇英文文章中查找指定的人名，人名使用26个英文字母（可以是大写或小写）、空格及两个通配符（和？）组成。通配符表示零个或多个任意字母，通配符？表示一个任意字母。例如，"J*Smi??"可以匹配"John Smith"。
6、字符串空格的压缩
给定一个字符串，将其中连续出现的空格压缩为1个后，将其中以空格分隔的每个字符串逆序打印出来。例如，"abc efg hij"的打印结果为"cba gfe jih"。
7、重复字符的压缩
通过键盘输入一串小写字母（a-z)组成的字符串。请编写一个字符串压缩编程序，对字符串中连续出现的重复字母进行压缩，并按要求输出压缩后的字符串。
具体压缩规则是：仅压缩连续重复出现的字符。例如，字符串"abcbc"由于无连续重复字符，压缩后的字符串还是"abcbc"。压缩后输出的格式要求为有重复的字符按“字符重复的次数+字符”输出，无格式的字符原样输出。例如，字符串"xxxyyyyyyz"压缩后输出为"3x6yz"，字符串"cccddecc"压缩后输出为"3c2de2c"，字符串"adef"压缩后输出为"adef"，字符串"pppppppp"压缩后输出为"8p"。
8、第一个只出现一次的字符
在一个字符串中找到第一个只出现一次的字符。例如，输入"abaccdeff"，则输出b。
9、删除特定的字符
给定一个原始字符串和模式字符串，要求在原始字符串中删除所有在模式字符串中出现过的字符，对应位置用空格占位。要求性能最优。例如，原始字符串为"They are students."，模式字符串为"aeiou"，那么删除之后得到的字符串为"Thy r stdnts."。
10、字符串集合的合并
给定一些字符串的集合，要求将其中交集不为空的集合合并，且合并完成后的集合之间无交集。例如，当给定这些字符串的集合{aaa,bbb,ccc}、{bbb,ddd}、{eee,fff}、{ggg}、{ddd,hhh}，结果应输出{aaa,bbb,ccc,ddd,hhh}、{eee,fff}、{ggg}。
提示：这种不相交集合的合并及查询问题，可以考虑使用并查集解决。
11、集合的差集
已知集合A和集合B的元素分别用不含头结点的单向链表存储，求集合A与集合B的差集，并将结果保存在集合A的单向链表中。例如，若集合A={5,10,20,15,25,30}，集合B={5,15,35,25}，它们的差集为A={10,20,30}。
