字符串高频面试题精讲.ppt

字符串高频面试题精讲.ppt

《字符串高频面试题精讲.ppt》由会员分享，可在线阅读，更多相关《字符串高频面试题精讲.ppt（17页珍藏版）》请在冰点文库上搜索。

字符串高频面试题精讲,七月算法曹鹏2015年4月21日,2/17,提纲,字符串简介面试题总体分析一些例题例10-1串交换排序例2字符的替换和复制例3交换星号例4子串变位词例5单词（字符串）翻转总结,字符串简介,字符串（String）通常把它作为字符数组java:

String内置类型，不可更改，要更改的话可考虑转StringBuffer,StringBuilder,char之类C+:

std:

：

string可更改，也可以考虑用char（char*）C：

只有char注意C+中“”运算符，复杂度未定义，但通常认为是线性的C+std:

stringsubstr和java的String的subString参数不同字符范围:

C/C+-128.+127,我们通常转化为unsigned变为0.+255Java:

0.65535,3/17,面试题总体分析,和数组相关，内容广泛概念理解：

字典序简单操作：

插入、删除字符，旋转规则判断（罗马数字转换是否是合法的整数、浮点数）数字运算（大数加法、二进制加法）排序、交换（partition过程）字符计数（hash）：

变位词匹配（正则表达式、全串匹配、KMP、周期判断）动态规划（LCS、编辑距离、最长回文子串）搜索（单词变换、排列组合）,4/17,例10-1交换,把一个0-1串（只包含0和1的串）进行排序，你可以交换任意两个位置，问最少交换的次数？

（国内某公司最新在线笔试题）分析：

快排partition?

最左边的那些0和最右边的那些1都可以不管000001.0111.1intanswer=0;for（inti=0,j=len1;ii）,5/17,例2字符替换和复制,删除一个字符串所有的a,并且复制所有的b。

注：

字符数组足够大分析：

先删除a,可以利用原来字符串的空间intn=0,numb=0;for（inti=0;si;+i）if（si!

=a）sn+=si;if（si=b）+numb;sn=0;再复制b，注意字符串要加长先计算字符串里有几个b，得到复制后的长度然后“倒着”复制惯用技巧,6/17,例2续,intnewLength=n+numb;snewLength=0;for（inti=newLength-1,j=n1;j=0;-j）si-=sj;if（sj=b）si-=b;思考题：

如何把字符串的空格变成”%20”?

同样，字符数组足够大！

7/17,例3交换星号,例3一个字符串只包含*和数字，请把它的*号都放开头。

方法1快排partition数字相对顺序会变化循环不变式：

0.i1都是*,i.j1是数字，j.n1未探测for（inti=0,j=0;jn;+j）if（sj=）swap（si+,sj）;,8/17,例3续1,样例*01*2*4i0,j=0,*01*2*4交换s0，不变，i=1i1,j=1,*01*2*4不变i=1,j=2,*01*2*4不变i1,j=3,交换s1,s3变为*102*4并且i2i2,j=4，*102*4不变i=2,j=5,交换s2,s5变为*0214且i=3再往后没变化了,9/17,例3续2,方法2数字相对顺序不变“倒着”intj=n1;for（inti=n1;i=0;-i）if（isdigit（si）sj-=si;for（;j=0;-j）sj=*;,10/17,例4子串变位词,给定两个串a和b，问b是否是a的子串的变位词。

例如输入a=hello,b=lel,lle,ello都是true,但是b=elo是false。

（国外某公司最新面试题）滑动窗口的思想动态维护一个“窗口”。

比如b的长度是3，我们考察a0.2,1.3,2.4是否和b是变位词如何与b比较？

11/17,例4续1,我们用一个hash,基于字符串的特殊性，我们可以用0.255或者0.65535的数组，我们暂且认为它们都是小写英文字母，用0.25来表示b中每个单词出现多少次。

我们可以存一下有多少个非0次出现的，以后有用intnonZero=0;for（inti=0;ilenb;+i）if（+numbia=1）+nonZero;,12/17,例4续2,我们用b中的次数减去a中一个“窗口”内的字符种类，如果结果全是0，则找到这样的子串了。

注意num的含义变为了字符种类差第一个窗口0.lenb1（注意lenalenb无解）for（inti=0;ilenb;+i）intc=aia;-numc;if（numc=0）-nonZero;elseif（numc=-1）+nonZero;if（nonZero=0）returntrue;,13/17,例4续3,窗口如何滑动？

向右移动一位新窗口ailenb+1.i旧窗口ailenb.i1扔掉ailenb加入aifor（inti=lenb;ilena;+i）intc=ailenba;+numc;if（numc=1）+nonZero;elseif（numc=0）-nonZero;c=aia;-numc;if（numc=0）-nonZero;elseif（numc=-1）+nonZero;if（nonZero=0）returntrue;思考题Leetcode3,14/17,例5单词翻转,翻转句子中全部的单词，单词内容不变例如Imastudent.变为student.aImin-place翻转字符串第i位到第j位while（ij）swap（si+,sj-）;有什么用？

翻转整个句子：

.tnedutsamI每个单词单独翻转：

student.aIm难点？

如何区分单词？

找空格，split思考题：

字符串循环移位abcd移动1次变为bcda移动2次变为cdab移动3次变为dabc结论：

长度为n，移动m次，相当于移动m%n次前m%n位翻转，后nm%n位翻转总体再翻转一次试验一下？

15/17,总结,我理解的in-place（原地）本身O

（1）空间递归，堆栈空间可以不考虑原地相关的问题字符串循环左移、右移动快排partition相关滑动窗口能达到O（n）的的时间复杂度O

（1）的空间复杂度规则相关细致匹配（暴力）：

KMP比较少见Manacher要求比较高的笔试,16/17,谢谢大家,更多算法视频尽在：

http:

/us：

微博七月算法七月问答曹鹏博士,17/17,