程序员编程艺术:面试和算法心得

所需积分/C币:25 2016-09-07 16:02:17 4.78MB PDF
收藏 收藏
举报

程序员编程艺术:面试和算法心得
第一章字符串本章导读 字符串相关的问题在各大互联网公司笔试面试屮出现的频率极高,比如微软绎典的单词翻转 题:输入“ am a student",则输出“ student.aamT”。 本章重点介绍个经典的字符串问题,分别是旋转字符串、字符串包含、字符串转换成整数 回文判断、最长回文子串、字符串的全排列,这个问题要么从暴力解法入手,然后逐步优 化,要么多种思路多种解法 读亢本章后会发现,好的思路都是在充分考虑到问题本身的特征的前提下,或巧用合适的数据 结构,或选择合适的算法降低时间复杂度(避兔不必要的操作),或选用效率更高的算法。 旋转字符串 题目描述 给定一个字符串,要求把字符串前面的若干个字符移动到字符串的尾部,如把字符串“ abcdef 前面的个字符和移动到字符串的尾部,使得原字符串变成字符串“ defat"。请写一个函 数完成此功能,要求对长度为的字符串操作的时间复杂度为,空间复杂度为 分析与解法 解法一:暴力移位法 初看此题,可能最先想到的方法是按照题目所要求的,把需要移动的字符一个一个地移动到字 符串的尾部,如此我们可以实现一个函数 Leftshiftone(chan*s,intn),以完成移动一个 字符到字符串尾部的功能,代码如下所示 void LeftShiftOne(char* s, int n char t=s[0];/保存第一个字符 for (int i=l:i< n: i++) s[i-1]=s[i] sIn 因此,若要把字符串开头的个字符移动到字符串的尾部,则可以如下操作: void LeftRotatestring (char* s, int n, int m) e (m- LeftShiftOne(s, n) 下面,我们来分析一下这种方法的时间复杂度和空间复杂度 针对长度为的字符串来说,假设需要移动个字符到字符串的尾部,那么总共需要次 操作,同时设立一个变量保存第一个字符,如此,时间复杂度为 空间复杂度为 ,空间复杂度符合题目要求,但时间复尔度不符合,所以,我们得需要寻找其他更好的办 法来降低时间复杂度。 解法二:三步反转法 对于这个问题,换一个角度思考一下。 将一个字符串分成和两个部分,在每部分字符串上定义反转操作,如,即把的所有 字符反转(如, ,那么 ),那么就得到下面的结论: 显 然就解决了字符串的反转问题。 例如,字符串 ,若要让翻转到的前头,只要按照下述个步骤操作即可 首先将原字符串分为两个部分,即, 将反转, ,即得 将反转, 即得 反转上述步骤得到的结果字符串 ,即反转字符串 的两部分(和 )给予反转, 得到 形式化表示为 ,这就实现了整 个反转。 如下图所示 可操作的证明方法-手摇法 如果要将一个具有10个元幸(我们只有10个手指阿)的数组向上旋转5个位置,先让两只手的掌 你自己,左右放在右手上面(其实两只手是同意平面上的),看下图 6 6 翻转左手 翻特右手 两手整体转 代码则可以这么写: void ReverseString(chark s, int from, int to while (from< to) char t=sfrom sIfrom++= stol sLto-- void LeftRotateString(chark s, int n, int m) m %=n //若要左移动大于n位,那么和%n是等价的 Reversestring(s,0,m-1);/反转[0..m-1],套用到上面举的例子 中,就是X->X^T,即abc->cba Reversestring(s,m,n-1);/反转Lm.n-1」,例如Y-YT,即 def->fed Reversestring(s,0,n-1);/转[0..n-1],即如整个反转 (X TY T)T=YX, Ep cbafed->defabc 这就是把字符串分为两个部分,先各白反转再整体反转的方法,时间复杂度为 空间复杂 度为 达到了题目的要求 举一反 链表翻转。给出一个链表和一个数,比如,链表为1→2→3→4→5→6, 则翻转后 2→1→6→54→3,若 翻转后3→2→1→6-5-4,若,翻转后 4→3→2→1→6→5,用程序实现、 、编写程序,在原字符串中把字符串尾部的个字符移动到字符串的头部,要求:长度为 的字符串换作时间复杂度为,空间复杂度为例如,原字符串为 lovebaofeng”, ,输出结果为:" baofengllove”。 单词翻转。输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变,句子 中单词以空格符隔开。为简单起见,标点符号和普通字母一样处理。例如,输入“lama student”,则输出" student.aam|", 字符串包含 题目描述 给定两个分别由字母组成的字符串和字符串,字符串的长度比字符串短。请问,如何 最快地判断字符串中所有字母是否都在字符串里? 为了简单起见,我们规定输入的字符串只包含大写英文宇母,请实现函薮 比如,如果是下面两个字符串 答案是 里的字母在 里也都有,或者说 是 的真子集。 如果是下面两个字符串: 答案是,因为字符串 里的字母不在字符串 里 同时,如果 :,同样返回 分析与解法 题目描述虽长,但题意很明了,就是给定一长一短的两个字符串,,假设长短,要求 判断是否包含在字符串中。 初看似乎简单,但实现起来并不轻松,且如果面试官步步紧逼,一个一个否决你能想到的方 法,要你给出更好、最好的方案时,恐怕就要伤不少脑筋了 解法一 判断 中的字符是否在 中最直观也是最简单的思路是,针对 中每一个字 符,逐个与 中每个字符比较,看它是否在 代码可如下编写 bool String Contain (string &a, string &b) for (int i-0: i< b length(; ++i) I In t for (j=0;(j< a length o)&&(alj =bli]):++j) f (j >= alength O) return false return true 假设是字符串 的长度,是字符串 的长度,那么此算法,需要 次操 作。显然,时问开销太大,应该找到一种更好的办法。 解法二 如果允许排序的话,我们可以考虑下排序。比如可先对这两个字符串的字母进行排序,然后再 同时对两个字串依次轮询。两个字串的排序需要常规情況 次操作,之 后的线性扫描需要 次操作。 关于排序方法,可采用最常用的快速排序,参考代码如下 //注意AB中可能包含重复字符,所以注意A下标不要轻易移动。这种方法改 变了字符串。如不想改变请自己复制 bool StringContain(string &a, string &b) sort(a begin O, a end O) sort(b begin, b end o) for(int pa=0, pb=0; pb< b length; while((pa< a length)&&(alpa< blpb]) ++pa if((pa >=a length)(a[pa]>b[pb]) return false a lpa return true 解法三 有没有比快速排序更好的方法呢? 我们换一种角度思考本问题: 假设有一个仅由字母组成字串,让每个字母与一个素数对应,从开始,往后类推,对应 对应,对应 遍历第一个字串,把每个字母对应素数相乘。最终会得到一个 整数。 利用上面字母和素数的对应关系,对应第二个字符串中的字母,然后轮询,用每个字母对应的 素数除前面得到的整数。如果结果有余数,说明结果为 如果整个过程中没有余数,则说 明第二个字符串是第一个的子集了(判断是不是真子集,可以比较两个字符串对应的素数乘 积,若相等则不是真子集)。 思路总结如下 按照从小到大的顺序,用个素数分别与字符到一对应。 遍历长字符串,求得每个字符对应素数的乘积 遍历短字符串,判断乘积能否被短字符丰中的字符对应的素数整除。 输出结果 如前所述,算法的时间复杂度为 的最好的情况为(遍历短的字符串的第一个数 与长字符串素数的乘积相除,即出现余数,便可退出程序,返回 ,为长字串的长度, 空间复杂度为 //此方法只有理论意义,因为整数乘积很大,有溢出风险 bool StringContain(string &a, string &b) const int pl26」={2,3,5,7,11,13,17,19,23,29,31,37, 41,43,47,53,59,61,67,71,73,79,83,89,97,101} int f=1 for(int i =0; i< a length(;++i) intx=plai」-'A’」; if (f x) f米三X for (int i=0; i<b length(; ++1) intx= pbli」-'A’」; if (f x) return false; return true, 此种素数相乘的方法看似完美,但缺点是素数相乘的结果容易导致整数溢出。 解法四 如果面试官继续追问,还有没有更好的办法昵?计数排序?除了计数排序呢? 事实上,可以先把长字符串中的所有字符都放入一个 里,然后轮询短字符串 看短字符串的每个字符是否都在 里,如果都存在,说明长字符串包含短字符串 ,否则,说明不包含 再进一步,我们可以对字符串,用位运算(整数表小计算出一个“签名",再用中的字 符到里面进行查找 /“最好的方法”,时间复杂度0(n+m),空间复杂度0(1) bool StringContain(string &a, string &b) int hash =0 for (int i-0; i< a length(;++i) hash|=(1<(a[i]-'A') for (int i=0: i< b length(; ++i) if ((hash &(1<<(bli-7A)))==0) return false return true 这个方法的实质是用一个整数代替了 ,空间复杂度为,时间复杂度还是 举一反三 变位词 如果两个字符串的字符一样,但是顺序不一样,被认为是兄弟字符串,比如和 即为兄弟字符串,现提供一个字符串,如何在字典中迅速找到它的兄弟字符串,请 描述数据结构和查询过程 字符串转换成整数 题目描述 输入一个由数字组成的字符串,把它转换成整数并输出。例如:输入字符串,输出整数 给定函数原型 int strtolnt( const char*str),实现字符审转换成整数的功能,不能使用库 函数 分析与解法 本题考査的实际上就是字符串转换成整数的问题,或者说是要你自行实现函数。那如何实 现把表示整数的字符串正确地转换成整数呢?以作为例子: ·当我们扫描到字符串的第一个字符时,由于我们知道这是第一位,所以得到数字。 当扫描到第一个数字时,而之前我们知道前面有一个,所以便在后面加上一个数字 那前面的相当于,因此得到数字

...展开详情
试读 127P 程序员编程艺术:面试和算法心得
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    程序员编程艺术:面试和算法心得 25积分/C币 立即下载
    1/127
    程序员编程艺术:面试和算法心得第1页
    程序员编程艺术:面试和算法心得第2页
    程序员编程艺术:面试和算法心得第3页
    程序员编程艺术:面试和算法心得第4页
    程序员编程艺术:面试和算法心得第5页
    程序员编程艺术:面试和算法心得第6页
    程序员编程艺术:面试和算法心得第7页
    程序员编程艺术:面试和算法心得第8页
    程序员编程艺术:面试和算法心得第9页
    程序员编程艺术:面试和算法心得第10页
    程序员编程艺术:面试和算法心得第11页
    程序员编程艺术:面试和算法心得第12页
    程序员编程艺术:面试和算法心得第13页
    程序员编程艺术:面试和算法心得第14页
    程序员编程艺术:面试和算法心得第15页
    程序员编程艺术:面试和算法心得第16页
    程序员编程艺术:面试和算法心得第17页
    程序员编程艺术:面试和算法心得第18页
    程序员编程艺术:面试和算法心得第19页
    程序员编程艺术:面试和算法心得第20页

    试读已结束,剩余107页未读...

    25积分/C币 立即下载 >