《部分面试题解题思路》由会员分享，可在线阅读，更多相关《部分面试题解题思路（7页珍藏版）》请在金锄头文库上搜索。
1、部分面试题解题思路这几天在网上看到一篇关于算法面试题的博客，归纳的很好，有不少经典的题目，大部分来自编程珠玑、编程之美、代码之美三本书。这里给出书上的解答以及一些思考。如有不对的地方，希望得到高手的指点。【一】 时间受限大部分的面试题，都是对时间复杂度有所要求的，如果有涉及，“最快” 一类的字样，毫无疑问，先上时空原理，用空间来换时间。Hash，大数组，一些辅助性的空间，都是首选。在我的面试经历中，有无数次用到过 Hash 和大数组的。不过，通常这不会是面试官想听的唯一解法，他们紧接着十有八九是会说“如果只有 xxxx 空间呢？” 。说此类方法只是为自己争取更多的时间，并且体现思考的完整性，简
2、而言之，装 B 用。eg1.1：求一个 char（8bit）中，二进制 1 的个数，越快越好。 - 编程之美编程之美上提供了五种方法，（1）使用除法操作 （2）使用位操作 （3）在位操作的基础上改进，算法的复杂度只于 1 的个数有关 （4）使用分支操作 （5）查表法。第 2 种方法用的是位运算，比第一种方法高效很多。第 3 种方法非常有技巧。第 4，5 两种方法其实是用空间换时间，但是如果是一个 int（32bit），那么这两种方法就不适用了。方法 3的代码int Count(BYTE v) int num = 0; while( v ) v num+;eg1.2：有一个整数数组 AN，让你不
3、用除法，求另一个数组 BN，其中 Bi = A0*A1 . * AN-1 / Ai，期望复杂度是 O(N)。 - TopLanguage 利用两个辅助数组 CN,DN完成，其中 Ci = A0*A1*.Ai-1*Ai, Di=Ai*Ai+1*.AN-2*AN-1，Bi =Ci-1 *Di+1 【二】 空间受限这里的空间受限，指的是在大数据分析的逻辑下，空间受限的问题。大部分情况下，就是压缩。位图是一个很好的方法，用一个 bit（或几个）取代更大的 int 类型，最常见的位图是 1bit 取代 1int，其实，很多时候，1bit 可以取代更大的空间，这完全取决于你需要保留的信息。eg2.1：有一
4、个很大的文件，存放一堆 7 位的电话号码，号码无重复，请用最小的内存消耗，将其排序。 - 编程珠玑利用位图技术实现。每一个号码如果用一个 int 存储，那么需要 40MB ( (107*4)/106 MB)，如果用位图技术，则只需用 1 位来存放 1 个号码，需要 1.25MB( ( 107/8)/106 MB)每个号码对应位图的一位，位图初始全清零，读入一个号码就把相应的位置位，遍历后按位图顺序输出对应的数字。eg2.2：给 10MB 的内存，给一个 4 百万整数的文件，找一个不在文件中的整数。可以用 10MB 内存来存放 0 到（8*107-1）范围数的出现情况。扫描文件一遍，将该范围中相
5、应的位置位，超出范围的数简单丢弃。然后遍历位图，找到第一个为 0 的位即可，位图中肯定有未置位的位。扩展 1 ：给 10MB 的内存，给一个 40 亿整数的文件，找一个不在文件中的整数。同样可以用上述的方法，不过可能需要多遍扫描。因为文件中的整数是多于 8*107，第一遍扫描后，位图的所有位都可能被置位。如果出现这种情况，那么用 10MB 内存存放 （8*107）到（16*107-1）范围数的出现情况，再次尝试。平均性能几乎是扫描 1 次。扩展 2 ：给 10MB 的内存，给一个 40 亿整数的文件，找一个不在文件中的整数。只能扫描文件 1 遍暂时未想到确定性的算法，这里给出一种近似的方法。随
6、机生成 200 万个数，然后排序。扫描文件 1 遍，把文件中出现的对应数删除，比如 200 万个随机数中有 5，而文件中也有 5，那么把随机数 5 从数组中删除（简单置为-1 即可）。最终随机生成的 200 万个数中会剩余 (2*106) * ( 1 - (4*109)/232) ，取其中的任意一个即可。几乎不会失败。【三】 基于文件 越来越多的大公司，开始关系对文件的处理，上面所说的空间受限的问题，其实也基本都是和文件打交道。基于文件的处理，基本都是寻找，或者排序，最最核心的，就是减少文件读取的次数。除了位图法，还可以考虑哨兵，典型的案例就是外排中，增加单个文件大小的方法。eg3.1：给定一
7、个包含 4300000000 个 32 位整数的顺序文件，找到一个至少出现两次的整数。 - 编程珠玑思路 1：如果内存不受限，用位图技术，必有 2 个数会落到同一位中，其实是运用了鸽巢原理。32 位整数能表示的最大数为 4294967295，小于 43 亿。思路 2：如果内存受限，采用二分搜索法。由于 4.3G32 位的整数空间，根据鸽笼原理，肯定会有重复的整数。搜索范围从所有的 32 位正整数开始（全部当成 unsigned int，简化问题），即0,232)，中间值即为 231。然后遍历文件，如果小于 231 的整数个数大于 231，则调整搜索范围为0,231，反之亦然；然后再对整个文件再
8、遍历一遍，直到得到最后的结果。这样一共会有 logn 次的搜索，每次过 n 个整数（每次都是完全遍历），总体的复杂度为 o(nlogn)eg3.2：有一个文件，有很多很多的整数（也许有 100 亿） ，寻找其中最大的 K 个。 - 编程之美 列举几种解法解法 1：如果元素不是很多，用快速排序，然后遍历找到最大的 K 个。总的时间复杂度为 O(N logN) + O(K)解法 2：找 K 个数中最小的那个，就是第 K 大的数。利用二分搜索找到第 K 大的数，然后在遍历。总的时间复杂度为 O(NlogN)解法 3：如果数据不能全部装入内存，上面两种方法不是很好。可以利用堆排序，即维护一个 K 个元
9、素的最小堆即可。每次新考虑的一个数，如果比堆的最小数还要小，丢弃；如果比堆的最小数要大，那么替换最小元素，然后调整堆。时间复杂度为 O(N logK)解法 4：如果数据的范围有限，可以利用计数法，即扫描文件一遍，记录每个整数出现的次数，然后再从大到小取最大的 K 个即可。时间复杂度为 O(N)【四】 常见方法 你需要相信，面试官也是人，他不会有心情花 30 分钟给你描述一个问题，或者让你做 50页纸的推导，考算法的目的只是为了你的思维能力，而不是真的想让你搞定一个复杂的问题。大部分问题，都是有比较快速清晰的解决方法的。 1. 分治法 这绝对是你必须考虑使用的一种方法，如果有可能的话。动态规划这
10、东西，在面试的时候比较沉重，不好描述，不好书写，而分治却刚刚好，美丽，快捷，易书写，是面试官杀人越货的首选武器。分治的用法实在是太多了，几乎是无所不在，二分，快排，种群计数，各个唯美无比。 eg4.1：给你一个长度为 N 的整数数组，请找出最大的子数组和。 - 编程之美这一题其实可以用动态规划解决。定义两个辅助数组 Start N 和 All N ，Start i 表示从元素 i 开始，包含元素 i 的最大的一段连续数组和。Alli 表示从元素 i 开始，最大的一段连续数组和。All0 = max A0, A0+Start1, All1 可以很方便的用动态规划解决。int MaxSum(int
11、 *A, int n) Alln-1=Start n-1=An-1;for(int i=n-2;i=0;i-)Starti= max( Ai, Ai+Starti+1 ); Alli=max( Starti, Alli+1 ); return All0;如果要求返回最大子数组的位置，可以在循环中记录一下。算法还是能保持 O(N)的时间复杂度的。eg4.2：求一个 int（32bit ）中，二进制 1 的个数。 - 代码之美可以参考 eg1.1 的方法 1、方法 2、方法 32. 排序和查找 排序出现的次数实在是太多了，很重要的一点，排序的东西才能用二分。二分是如此好用，以至于我们总是想着排序。
12、查找和排序总是紧密联系的，当然，仅仅是为了查找，做一次排序，你需要衡量一下代价。 eg4.3：有一个论坛，有 ID 发帖数目超过总数的一半，给你论坛所有帖子的 ID 列表，请你找到这个水王。 - 编程之美 解法 1：先将 ID 排个序，然后取中间位置的那个 ID 即可。解法 2：每次删除不同的 ID，最后剩下的 ID 即为所求。扩展 1：如果有 3 个发帖很多的 ID，并且发帖的数目都超过了总数 N 的 1/4，找到这 3 个ID。可以用类似的解法，维护 3 个候选者。对于新 ID，检查 3 个候选者的出现次数。如果次数有 0，那么将该候选者设置为新 ID，并且把次数加 1；如果次数都是大于
13、0，并且新 ID 等于其中的一个候选者，那么将该候选者的出现次数加 1；如果次数都是大于 0，并且新 ID不等于三个中的任意一个，那么将三个候选者的出现次数各减少 1 次。最后剩下的 3 个 ID即为所求。eg4.4：给一组一维的空间 1, 6 2, 4 . ，请求是否有区间重叠。 - 编程之美 解法：将目标区间按 X 坐标排序，然后合并相交区间，最后扫描一遍合并后的区间，检查源区间是否在其中一个目标区间中。最后一步也可以利用二分查找。3. 减小问题规模 很多时候，题目看上去很吓人，仔细分析一下，就可以刨去其中大部分的无关内容，获得真正的出题意图，这一点很重要。另外有些时候，题目会在空间上做出
14、一些限制，这个时候，你可以考虑动态的对数据规模进行缩减，比如用减法或除法抵消，用抑或抵消，等等。 eg4.5：给一个整数 N，求它的阶乘 N!，有几个 0 结尾。 - 编程之美解法：0 的出现是因为 2*5 带来的，因此只要计算 min( 2 的个数, 5 的个数)即可。又由于2 的出现频率大于 5，只要求 5 的个数即可eg4.6：盒子里有三种颜色的球，红黄蓝，可以用任意两个不同颜色的球，换两个另外颜色的球，比如 1 红 + 1 黄 = 2 蓝。现在盒子里面有 171 个红球，172 个黄球，173 个蓝球，问，能不能经过若干次交换，最终变成同一颜色的球。 - TopLanguage猜测：不
15、能，最多只能是某种颜色 0 个，另一种 1 个，其余是第三种颜色。eg4.7：有一组数，除了一个数只有 1 个，其他都是两两成对的，请找出那一个不成对的数。另，如果不成对的数有两个，该如何是好。 解法：如果只有 1 个，可以将所有数做异或运算，最后的结果就是要找的数。如果是 2 个，那么先将所有数做异或运算，得到一个数，然后找到这个数的其中一位非 0 bit，利用这一位将这组数分成两部分，不成对的两个数不会在同一部分，然后对这两个部分分别调用只有 1 个情况的算法即可。4. 常量法 典型的速餐方法，它的思想是，一组数，在某些情况下，和一定，通过这个常量，进行反推，可快速搞定一些问题。 eg4.9：有一副扑克牌（你可以用任意方式来表示），被抽去一张，请快速找出这抽去的一张是什么？ - 微软面试题解法：算一下目前牌的数值总和 x，原来完整的总和是 y，则丢掉的牌是 y-x。5. 编码 编码真是个好东西，它可以将复杂的问题抽象化。比如，对一个序列进行编码，可以直接映射到数组脚标上，大大提高访问速度。 eg4.10：最近一次百度笔试题 eg4.11：有 1000 瓶超级名贵的葡萄酒，其中有 1 瓶有毒。这种毒药很厉害，哪怕被稀释了 1000000 倍还是可以毒死人的。但这个毒药一定时间后才会毒发，时长是 1 个月。为了不浪费这些
