部分面试题解题思路

《部分面试题解题思路》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、部分面试题解题思路这几天在网上看到一篇关于算法面试题的博客，归纳的很好，有不少经典的题目，大部分来自《编程珠玑》、《编程之美》、《代码之美》三本书。这里给出书上的解答以及一些思考。如有不对的地方，希望得到高手的指点。【一】时间受限大部分的面试题，都是对时间复杂度有所要求的，如果有涉及，“最快”一类的字样，毫无疑问，先上时空原理，用空间来换时间。Hash，大数组，一些辅助性的空间，都是首选。在我的面试经历中，有无数次用到过Hash和大数组的。不过，通常这不会是面试官想听的唯一解法，他们紧接着十有八九是会说“如果只有xxxx空间呢？”。说此类方法只是为自己争取更多的时间，并且体现思考的完整性，简

2、而言之，装B用。。。eg1.1：求一个char（8bit）中，二进制1的个数，越快越好。--《编程之美》编程之美上提供了五种方法，（1）使用除法操作（2）使用位操作（3）在位操作的基础上改进，算法的复杂度只于1的个数有关（4）使用分支操作（5）查表法。第2种方法用的是位运算，比第一种方法高效很多。第3种方法非常有技巧。第4，5两种方法其实是用空间换时间，但是如果是一个int（32bit），那么这两种方法就不适用了。方法3的代码intCount(BYTEv) {    intnum=0;    while(v) {      v&=(v-1);      num++;   }}eg1.2：有一

3、个整数数组A[N]，让你不用除法，求另一个数组B[N]，其中B[i]=A[0]*A[1]...*A[N-1]/A[i]，期望复杂度是O(N)。 --TopLanguage 利用两个辅助数组C[N],D[N]完成，其中C[i]=A[0]*A[1]*...A[i-1]*A[i],D[i]=A[i]*A[i+1]*...A[N-2]*A[N-1]，B[i]=C[i-1]*D[i+1] 【二】空间受限这里的空间受限，指的是在大数据分析的逻辑下，空间受限的问题。大部分情况下，就是压缩。位图是一个很好的方法，用一个bit（或几个）取代更大的int类型，最常见的位图是1bit取代1int，其实，很多时候，

4、1bit可以取代更大的空间，这完全取决于你需要保留的信息。。。 eg2.1：有一个很大的文件，存放一堆7位的电话号码，号码无重复，请用最小的内存消耗，将其排序。--《编程珠玑》利用位图技术实现。每一个号码如果用一个int存储，那么需要40MB( (10^7*4)/10^6MB)，如果用位图技术，则只需用1位来存放1个号码，需要1.25MB( (10^7/8)/10^6MB)每个号码对应位图的一位，位图初始全清零，读入一个号码就把相应的位置位，遍历后按位图顺序输出对应的数字。eg2.2：给10MB的内存，给一个4百万整数的文件，找一个不在文件中的整数。可以用10MB内存来存放0到（8*10^7

5、-1）范围数的出现情况。扫描文件一遍，将该范围中相应的位置位，超出范围的数简单丢弃。然后遍历位图，找到第一个为0的位即可，位图中肯定有未置位的位。扩展1：给10MB的内存，给一个40亿整数的文件，找一个不在文件中的整数。同样可以用上述的方法，不过可能需要多遍扫描。因为文件中的整数是多于 8*10^7，第一遍扫描后，位图的所有位都可能被置位。如果出现这种情况，那么用10MB内存存放 （8*10^7）到 （16*10^7-1）范围数的出现情况，再次尝试。平均性能几乎是扫描1次。扩展2：给10MB的内存，给一个40亿整数的文件，找一个不在文件中的整数。只能扫描文件1遍暂时未想到确定性的算法，这里给

6、出一种近似的方法。随机生成200万个数，然后排序。扫描文件1遍，把文件中出现的对应数删除，比如200万个随机数中有5，而文件中也有5，那么把随机数5从数组中删除（简单置为-1即可）。最终随机生成的200万个数中会剩余(2*10^6)*(1-(4*10^9)/2^32)，取其中的任意一个即可。几乎不会失败。【三】基于文件 越来越多的大公司，开始关系对文件的处理，上面所说的空间受限的问题，其实也基本都是和文件打交道。基于文件的处理，基本都是寻找，或者排序，最最核心的，就是减少文件读取的次数。除了位图法，还可以考虑哨兵，典型的案例就是外排中，增加单个文件大小的方法。eg3.1：给定一个包含4300

7、000000个32位整数的顺序文件，找到一个至少出现两次的整数。--《编程珠玑》思路1：如果内存不受限，用位图技术，必有2个数会落到同一位中，其实是运用了鸽巢原理。32位整数能表示的最大数为4294967295，小于43亿。思路2：如果内存受限，采用二分搜索法。由于4.3G>32位的整数空间，根据鸽笼原理，肯定会有重复的整数。搜索范围从所有的32位正整数开始（全部当成unsignedint，简化问题），即[0