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

《字符串高频面试题精讲ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、字符串高频面试题精讲xx提纲字符串简介面试题总体分析一些例题例10-1串交换排序例2字符的替换和复制例3交换星号例4子串变位词例5单词（字符串）翻转总结xx字符串简介字符串(String)通常把它作为字符数组java:String内置类型，不可更改，要更改的话可考虑转StringBuffer,StringBuilder,char[]之类C++:std:：string可更改，也可以考虑用char[](char*)C：只有char[]注意C++中“＋”运算符，复杂度未定义，但通常认为是线性的C++std::stringsubstr和j

2、ava的String的subString参数不同字符范围:C/C++[-128..+127],我们通常转化为unsigned变为[0..+255]Java:［0..65535]xx面试题总体分析和数组相关，内容广泛概念理解：字典序简单操作：插入、删除字符，旋转规则判断（罗马数字转换是否是合法的整数、浮点数）数字运算（大数加法、二进制加法）排序、交换（partition过程）字符计数（hash)：变位词匹配（正则表达式、全串匹配、KMP、周期判断）动态规划(LCS、编辑距离、最长回文子串）搜索（单词变换、排列组合）xx例10-1交换

3、把一个0-1串（只包含0和1的串）进行排序，你可以交换任意两个位置，问最少交换的次数？（国内某公司最新在线笔试题）分析：快排partition?最左边的那些0和最右边的那些1都可以不管00…0001…….0111….1intanswer=0;for(inti=0,j=len–1;ii)&&(a[j]==‘1’);--j);if(i

4、大分析：先删除a,可以利用原来字符串的空间intn=0,numb=0;for(inti=0;s[i];++i){if(s[i]!=‘a’){s[n++]=s[i];}if(s[i]==‘b’){++numb;}}s[n]=0;再复制b，注意字符串要加长先计算字符串里有几个b，得到复制后的长度然后“倒着”复制——惯用技巧xx例2——续intnewLength=n+numb;s[newLength]=0;for(inti=newLength-1,j=n–1;j>=0;--j){s[i--]=s[j];if(s[j]==‘b’)s[i-

5、-]=‘b’;}思考题：如何把字符串的空格变成”%20”?同样，字符数组足够大！xx例3交换星号例3一个字符串只包含*和数字，请把它的*号都放开头。方法1快排partition——数字相对顺序会变化循环不变式：[0..i–1]都是*,[i..j–1]是数字，[j..n–1]未探测for(inti=0,j=0;j

6、4不变i＝1,j=3,交换s[1],s[3]变为**102*4并且i＝2i＝2,j=4，**102*4不变i=2,j=5,交换s[2],s[5]变为***0214且i=3再往后没变化了xx例3续2方法2数字相对顺序不变“倒着”intj=n–1;for(inti=n–1;i>=0;--i)if(isdigit(s[i]))s[j--]=s[i];for(;j>=0;--j)s[j]=‘*’;xx例4子串变位词给定两个串a和b，问b是否是a的子串的变位词。例如输入a=hello,b=lel,lle,ello都是true,但是b=elo

7、是false。（国外某公司最新面试题）滑动窗口的思想动态维护一个“窗口”。比如b的长度是3，我们考察a[0..2],[1..3],[2..4]是否和b是变位词如何与b比较？xx例4——续1我们用一个hash,基于字符串的特殊性，我们可以用[0..255]或者[0..65535]的数组，我们暂且认为它们都是小写英文字母，用[0..25]来表示b中每个单词出现多少次。我们可以存一下有多少个非0次出现的，以后有用intnonZero=0;for(inti=0;i

8、ero;xx例4——续2我们用b中的次数减去a中一个“窗口”内的字符种类，如果结果全是0，则找到这样的子串了。注意num[]的含义变为了字符种类差第一个窗口[0..lenb–1](注意lena