下载  >  开发技术  >  C  > 程序员编程艺术:面试和算法心得.pdf

程序员编程艺术:面试和算法心得.pdf 评分:

第一部分 数据结构 • • • 第一章 字符串 o 1.0 本章导读 o 1.1 旋转字符串 o 1.2 字符串包含 o 1.3 字符串转换成整数 o 1.4 回文判断 o 1.5 最长回文子串 o 1.6 字符串的全排列 o 1.10 本章习题 第二章 数组 o 2.0 本章导读 o 2.1 寻找最小的 k 个数 o 2.2 寻找和为定值的两个数 o 2.3 寻找和为定值的多个数 o 2.4 最大连续子数组和 o 2.5 跳台阶 o 2.6 奇偶排序 o 2.7 荷兰国旗 o 2.8 矩阵相乘 o 2.9 完美洗牌 o 2.15 本章习题 第三章 树 o 3.0 本章导读 o 3.
第一章字符串 本章导读 宇符串相关的问题在各大互联网公司笔试面试中出现的频率极高,比如微软经典的单词翻转题 输入“ am a student.”,则输出“ student.aamP。 本章重点介绍6个经典的字符串问题,分别是旋转字符串、字符串包含、字符串转换成整数、 回文判断、最长回文子串、字符串的全排列,这6个问题要么从暴力解法入手,然后逐步优化 要么多种思路多种解法 读完本章后会发现,好的思路都是在充分考虑到问题本身的特征的前提下,或巧用合适的数据结 构,或选择合适的算法降低时间复杂度(避免不必要的操作),或选用效率更髙的算法。 11旋转字符串 题目描述 给定一个字符串,要求把字符串前面的若干个字符移动到字符串的尾部,如把字符串“ abcdef"前 面的2个字符a和"移动到字符串的尾部,使得原字符串变成字符串“ defat”。请写一个函数完 成此功能,要求对长度为n的字符串操作的时间复杂度为O(n),空间复杂度为O(1)。 分析与解法 解法一:暴力移位法 初看此题,可能最先想到的方法是按照题目所要求的,把需要移动的字符一个一个地移动到字符 串的尾部,如此我们可以实现一个函数 Leftshiftone(char*s,intn),以完成移动一个字符 到字符串尾部的功能,代码如下所示 void LeftShiftOne(char* s, int n) char t=s[0];/保存第一个字符 Tor(int i=1: i< n: i++) sIn ]=t; 因此,若要把字符串开头的m个字符移动到字符串的尾部,则可以如下操作 void LeftRotateString(char*k s, int n, int m) while(m LeftShiftOne(s, n) 下面,我们来分析一下这种方法的时间复杂度和空间复杂度。 针对长度为n的字符串来说,假设需要移动m个字符到字符串的尾部,那么总共需要mn次 操作,同时设立一个变量保存第一个字符,如此,时问复杂度为O(mn),空间复杂度为O(1) 空间复杂度符合题日要求,但时间复杂度不符合,所以,我们得需要寻找其他更好的办法来降低 时间复杂度。 解法二:三步反转法 对」这个问题,换一个角度思考一下 将一个字符串分成X和Y两个部分,在每部分字符上定义反转操作,如ⅩAT,即把X的所有 字符反转(如,X="abc"”,那么Ⅹ^T="cba"),那么就得到下面的结论:( XATYAT)AT=YX,显然 就解决了字符串的反转问题。 例如,字符串 abcdef,若要让def翻转到abc的前头,只要按照下述3个步骤操作即可 1.首先将原字符串分为两个部分,即X:abC,Y:def 2.将Ⅹ反转,X->XAT,即得:abc->cba:将Y反转,Y>YAT,即得:def->fed 3.反转上述步骤得到的结果字符韦 XATYAT,即反转字符串 chafed的两部分(cba和fed) 给予反转, chafed得到 defabc,形式化表示为(XTY^T)AT=YX,这就实现了整个反转 如下图所示: 可操作的证明方法-手摇法 如果要将一个具有0个元幸(我们只有10个手指啊)的数组向上旋转5个位置,先让两只手 你自己,左右放在右手上面(其实两只手是同意平面上的),看下图 结能米 5 翻转左手 特右手 两手整体翻转 代码则可以这么写: oid ReverseString(char s, int from, int to) while (from< to) char t= sfrom sLfrom++]=stol s[to-=t void LeftRotateString(char* s, int n, int m) m %n //若要左移动大于n位,那么和‰是等价的 Reversestring(s,0,m-1);//反转[0..m-1],套用到上面举的例子中, 就是X->XT,即abe->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, EJ cbafed->defabc 这就是把字符串分为两个部分,先各自反转再整体反转的方法,时间复杂庋为O(n),空间复杂 度为O(1),达到了题日的要求 举一反三 1、链表翻转。给出一个链表和一个数k,比如,链表为1郑斗爷,k=2,则翻转后 216为斗,若k=3,翻转后3斗为斗,若k=4,翻转后4郑为,用程序实现。 2、编写程序,在原宇符串中把字符串尾部的m个宇符移动到字符串的头部,要求:长度为n 的字符串操作时间复杂度为O(n),空间复杂度为O(1)。例如,原字符串为 ovebaofeng”,m=7, 输出结果为:" baofeng llove”。 3、单词翻转。输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变,句子中 单词以空格符隔开。为简单起见,标点符号和普通字母一样处理。例如,输入" am a student.”, 则输出“ student.aam|”。 1.2字符串包含 题目描述 给定两个分别由字母组成的字符串A和字符串B,宇符串B的长度比字符串A短。请问,如何 最快地判断字符串B屮所有字母是否都在字符串A里? 为了简单起见,我们规定输入的字符串只包含大写英文字母,请实现函数bool String Contains(string &A, string &B) 比如,如果是下面两个字符串: String 1: ABCD String 2: BAD 答案是true,即 String2里的字母在 String1里也都有,或者说 String2是 String1的真子集。 如果是下面两个字符串 String 1: ABCD String 2: BCE 答案是 false,因为字符串Stng2里的E字母不在字符串 String1里。 同时,如果 string1:ABCD, string2:AA,同样返回true 分析与解法 题目描述虽长,但题意很明了,就是给定一长一短的两个字符串A,B,假设A长B短,要求判 断B是否包含在字符串A中 初看似乎简单,但实现起来并不轻松,且如果面试官步步紧逼,一个一个否决你能想到的方法, 要你给出更好、最好的方案时,恐怕就要伤不少脑筋了。 解法一 判断stng2中的字符是否在sng1中?最直观也是最简单的思路是,针对 string2中每一个字 符,逐个与 string1中每个字符比较,看它是否在 String1中 代码可如下编写: bool StringContain(string &a, string &b) for (int i=0;i< b length(;++1)( int J: for (j=0;(j< a length o)&&(alj] =bli]);++i) if (j >=a length O) return false return true 假设n是字符串 String1的长度,m是字符串 String2的长度,那么此算法,需要O(nm)次操作 显然,时间开销太大,应该找到一种更好的办法。 解法二 如果允许排序的话,我们可以考虑下排序。比如可先对这两个字符串的字母进行排序,然后再同 时对两个字串依次轮询。两个字串的排序需要(常规情况) o(m log m)+O( n log n)次操作,之后 的线性扫描需要Om+n)次操作 关于排序方法,可采用最常用的快速排序,参考代码如下: //注意AB中可能包含重复字符,所以注意A下标不要轻易移动。这种方法改变 了字符串。如不想改变请自己复制 bool StringContain(string &a, string &b) sort(a begin(, a end O) sort(b begin(, b end o) or (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 解法三 有没有比快速排序更好的方法呢? 我们换一种角度思考本问题: 假设有一个仅由字母组成字串,让每个字母与一个素数对应,从2开始,往后类推,A对应2, B对应3,C对应5,…。遍历第一个字串,把每个字母对应素数相乘。最终会得到一个整数 利用上面字母和素数的对应关系,对应第二个字符串中的字母,然后轮询,用每个字母对应的素 数除前面得到的整数。如果结果有余数,说明结果为 false。如果整个过程中没有余数,则说明 第二个字符串是第一个的子集了(判断是不是真子集,可以比较两个字符串对应的素数乘积,若 相等则不是真子集)。 思路总结如下 1.按照从小到大的顺序,用26个素数分别与宁符A到z一一对应。 2.遍历长宇符串,求得每个字符对应素数的乘积。 3.遍历短字符串,判断乘积能否被短字符串中的字符对应的素数整除。 4.输出结果。 如前所述,算法的时间复杂庋为O(m+n)的最好的情况为on)(遍历短的字符串的第一个数,与 长字符串素数的乘积相除,即出现余数,便可退出程序,返回 false),n为长字串的长度,空 间复杂度为O(1) //此方法只有理论意义,因为整数乘积很大,有溢出风险 bool StringContain (string &a, string &b) const int p26」={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 r=l for (int i=0; i< a length(; ++i) int x-plali-A] if (f x) f米三X for(int i=0; i< b length(; ++i) intx= pIbi」-'A」 if (f x) return false return true, 此种素数相乘的方法看似完美,但缺点是素数相乘的结果容易导致整数溢出。 解法四 如果面试官继续追问,还有没有更好的办法呢?计数排序?除了计数排序呢? 事实上,可以先把长字符串a中的所有字符都放入一个 Hashtable旦,然后轮洵短字符串b,看 短字符串b的每个字符是否都在 Hashtable里,如果都存在,说明长字符串a包含短字符串b, 否则,说明不包含 雨进一步,我们可以对字符串A,用位运算(26bt整数表示)计算出一个“签名”,再用B中的 符到A里面进行查找。 //“最好的方法”,时间复杂度0(n+m),空间复杂度0(1) bool StringContain (string &a, string &b) int hash =0 for (int i-0; i a length(; ++i) hash|=(1<<(ai]-'A') }f or (int i=0; i b length( if ((hash &(1 <<(bliJ-A)))== 0) return alse return true 这个方法的实质是用一个整数代替了 hashtable,空间复杂度为o(1),时间复杂度还是o(n+m) 举一反三 1、变位词 如果两个字符串的字符一样,但是顺序不一样,被认为是兄弟字符串,比如bad和adb 即为兄弟字符串,现提供一个字符串,如何在字典屮迅速找到它的兄弟字符串,请描述 数据结构和查询过程。 1.3字符串转换成整数 题目描述 输入一个由数字组成的字符串,把它转换成整数并输出。例如:输入字符串"123",输出整数123 给定函数原型 int str tolnt( const char*str),实现字符串转换成整数的功能,不能使用库 函数ato 分析与解法 木题考査的实际上就是字符串转换成整数的问题,或者说是要你自行实现ato函数。那如何实 现把表示整数的字符串正确地转换成整数呢?以"123"作为例子: ·当我们扫描到字符串的第一个字符1时,由于我们知道这是第一位,所以得到数字1 当扫描到第二个数字2时,而之前我们知道前面有一个1,所以便在后面加上一个数字 2,那前面的1相当于10,因此得到数字:1*10+2=12。 ·继续扣描到字符3,3的前面已经有了12,由于前面的12相当于120,加上后面扫描 到的3,最终得到的数是:12*10+3=123。

...展开详情
2017-11-16 上传 大小:4.91MB
举报 收藏
分享
程序员编程艺术:面试和算法心得

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

立即下载
程序员编程艺术:面试和算法心得》

July在西电的讲座,包括面试中经常考的算法、海量数据处理和机器学习。还有常见的问题解析。

立即下载
程序员编程艺术第一 ~二十七章(教你如何编程)高清完整PDF版by_July

本文档为程序员编程艺术系列:http://blog.csdn.net/v_july_v/article/category/784066,的PDF电子版,它最初由朋友吴超和花明月暗于04.03制作,而在此之前,你在任何一个地方都找不到它。 特此分享,完全免费0积分下载,以为感谢和回馈一年半以来一直支持本人blog:http://blog.csdn.net/v_JULY_v,的所有读者们,感谢各位,敬请享用。

立即下载
程序员编程艺术

本文档为程序员编程艺术系列PDF电子版,它最初由朋友吴超和花明月暗于04.03制作,而在此之前,你在任何一个地方都找不到它。

立即下载
程序员编程艺术第一~三十七章集锦 高清完整PDF版

  从2011年4月写下第一篇至今,编程艺术系列已经写了37章,也就是说详细阐述了37个编程问题,在创作的过程当中,得到了很多朋友的支持,特别是博客上随时都会有朋友不断留言,或提出改进建议,或show出自己的思路、代码,或指正bug,非常感激。      本系列越写到最后,越会发觉无论是面试,还是编程当中遇到的绝大部分问题,都是有规律可循的,而且可以不断优化,这也是自己愿一直写下去的原因。再者,能给每一年找工作的毕业生带去或多或少的参考,给早已参加工作的人提供思维锻炼的机会,何尝不是一种思考与编程的双重乐趣!      编程艺术的继续创作仍需要得到广大读者的更多支持,最近,正在review和优

立即下载
程序员编程艺术系列之经典算法研究

程序员编程艺术系列之经典算法研究 电子书【高清中文带书签】

立即下载
《编程之法—面试和算法心得》PDF

该pdf文件内容涉及面试、算法、机器学习三个主题。书中的每道编程题目都给出了多种思路、多种解法,不断优化、逐层递进。

立即下载
《程序员编程艺术:面试和算法心得》

July在西电的讲座,包括面试中经常考的算法、海量数据处理和机器学习

立即下载
编程艺术:面试和算法心得

《编程之法:面试和算法心得》[1] 涉及面试、算法、机器学习三个主题。书中的每道编程题目都给出了多种思路、多种解法,不断优化、逐层递进。本书第1章至第6章分别阐述字符串、数组、树、查找、动态规划、海量数据处理等相关的编程面试题和算法,第7章介绍机器学习的两个算法—K近邻和SVM。   此外,《编程之法:面试和算法心得》每一章都有“举一反三”和“习题”,以便读者及时运用所学的方法解决相似的问题,且在附录中收录了语言、链表、概率等其他题型。书中的每一道题都是面试的高频题目,反复出现在近5年各大公司的笔试和面试中,对面试备考有着极强的参考价值。

立即下载
编程之法:面试和算法心得 清晰完整版

应该是这个论坛比较清晰和清楚的pdf文件了

立即下载
《编程之法:面试和算法心得》文字版 pdf

《编程之法:面试和算法心得》文字版 pdf

立即下载
编程之法_面试和算法心得_完整扫描pdf

本书涉及面试、算法、机器学习三个主题。书中的每道编程题目都给出了多种思路、多种解法,不断优化、逐层递进。本书第1章至第6章分别阐述字符串、数组、树、查找、动态规划、海量数据处理等相关的编程面试题和算法,第7章介绍机器学习的两个算法—K近邻和SVM。此外,每一章都有“举一反三”和“习题”,以便读者及时运用所学的方法解决相似的问题,且在附录中收录了语言、链表、概率等其他题型。书中的每一道题都是面试的高频题目,反复出现在近5年各大公司的笔试和面试中,对面试备考有着极强的参考价值。

立即下载
html+css+js制作的一个动态的新年贺卡

该代码是http://blog.csdn.net/qq_29656961/article/details/78155792博客里面的代码,代码里面有要用到的图片资源和音乐资源。

立即下载
qBittorrent插件集合(22个)

btetree.py cpasbien.py divxtotal.py ilcorsaronero.py kickass.py leetx.py limetorrents.py linuxtracker.py nyaa.py nyaapantsu.py nyaasi.py pantsu.py psychocydd.py rarbg.py rutor.py skytorrents.py sukebei.py sumotorrent.py tntvillage.py torrent9.py torrentfunk.py zooqle.py

立即下载
万能BIOS刷新工具Universal Flash Utility V8.95

近期在网搜刷新工具时,寻得这组万能刷新工具类型的希缺资源[正宗正版工具软件],特上传bios之家论坛,对号最需要它的爱好者群!软件版权归属原作品发布方,提供与本网站各界爱好者试用,以便交流刷新比较困难的 bios 实际使用经验![[ 其中的895工具是在本论坛首次亮像,=本论坛335469299用户曾在2011年6月29日发表过848的使用资料=各位可划文搜链接[ ==http://bbs.bios.net.cn/?8024== ]看 用户 awb 空间 所存载主题=求万能bios刷写工具flash849.exe-=之=-335469299 -=所回帖发布软件介绍使用参数 参考试用万能 bio

立即下载