笔试题之一:字符串相关问题

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}。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 202,802评论 5 476
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,109评论 2 379
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 149,683评论 0 335
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,458评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,452评论 5 364
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,505评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,901评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,550评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,763评论 1 296
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,556评论 2 319
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,629评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,330评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,898评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,897评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,140评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,807评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,339评论 2 342

推荐阅读更多精彩内容