面试算法题的快速思考方法

面对一个问题,改如何下手思考将其解决
服务器君一共花费了210.706 ms进行了5次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

面试中纯粹考算法的问题一般是让很多程序员朋友痛恨的,这里分享下我对于解答算法题的一些思路和技巧。

一般关于算法的文章,都是从经典算法讲起,一种一种算法介绍,见得算法多了,自然就有了感悟,但如此学习花费的时间和精力却是过于巨大,也不适合在博客里面交流。这一篇文,却是专门讲快捷思路的,很多人面对算法题的时候几乎是脑子里一片空白,这一篇文章讲的就是从题目下手,把毫无思路的题目打开一个缺口的几种常见技巧。

由简至繁

事实上,很多问题确实是很难在第一时间内得到正确的思路的,这时候可以尝试一种由简至繁的思路。首先把问题规模缩小到非常容易解答的地步。

[题目]有足够量的2分、5分、1分硬币,请问凑齐1元钱有多少种方法?

此题乍看上去,只会觉得完全无法入手,但是按照由简至繁的思路,我们可以先考虑极端简单的情况,假如把问题规模缩小成:有足够量的1分硬币,请问凑齐1分钱有多少种方法?毫无疑问,答案是1。

得到这一答案之后,我们可以略微扩大问题的规模: 有足够量的1分硬币,凑齐2分钱有多少种方法?凑齐n分钱有多少种方法?答案仍然是1。

接下来,我们可以从另一个角度来扩大问题,有足够量的1分硬币和2分硬币,凑齐n分钱有多少种方法?这时我们手里已经有了有足够量的1分硬币,凑齐任意多钱都只有1种方法,那么只用1分钱凑齐n-2分钱,有1种方法,只用1分钱凑齐n-4分钱,有1种方法,只用1分钱凑齐n-6分钱,有1种方法......

而凑齐这些n-2、n-4、n-6这些钱数,各自补上2分钱,会产生一种新的凑齐n分钱的方法,这些方法的总数+1,就是用1分硬币和2分硬币,凑齐n分钱的方法数了。

在面试时,立刻采用这种思路是一种非常有益的尝试,解决小规模问题可以让你更加熟悉问题,并且慢慢发现问题的特性,最重要的是给你的面试官正面的信号——立即动手分析问题比皱眉冥思苦想看起来好得多。

对于此题而言,我们可以很快发现问题的规模有两个维度:用a1-ak种硬币和凑齐n分钱,所以我们可以记做P(k,n)。当我们发现递归公式 P(k,n) = P(k-1,n - ak) + P(k-1,n - 2*ak) + P(k-1,n - 3*ak) ... ... 时,这个问题已经是迎刃而解了。

通常由简至繁的思路,用来解决动态规划问题是非常有效的,当积累了一定量简单问题的解的时候,往往通向更高一层问题的答案已经摆在眼前了。

一分为二

另一种思路,就是把问题一刀斩下,把问题分为两半,变成两个与原来问题同构的问题,能把问题一分为2,就能再一分为4,就能再一分为8,直到分成我们容易解决的问题。当尝试这种思路时,其实只需要考虑两个问题:1.一分为二以后,问题是否被简化了? 2.根据一分为二的两个问题的解,能否方便地得出整个问题的解?

[题目]将一个数组排序。

这个经典算法肯定所有人都熟悉的不能再熟悉了,不过若是从头开始思考这个问题,倒也不是所有人都能想出几种经典的排序算法之一的,这里仅仅是用来做例子说明一分为二的思路的应用。

最简单的一分为二,就是将数组分成两半,分别排序。对于两个有序数组,我们有办法将它合并成一个有序数组,所以这个一分为二的思路是可行的,同样对于已经分成两半的数组,我们还可以将这个数组分作两半,直到我们分好的数组仅有1个元素,1个元素的数组天然就是有序的。不难看出,按这种思路我们得出的是经典数组排序算法中的"归并排序"。

还有另一种一分为二的思路,考虑到自然将数组分成两半合并起来比较复杂,我们可以考虑将数组按照大于和小于某个元素分成两半,这样只要分别解决就可以直接连接成一个有序数组了,同样这个问题也是能够再次一分为二。按照这个思路,则可以得出经典数组排序算法中的"快速排序"。

化虚为实

这种思路针对的是浮点数有关的特殊问题,因为无论是穷举还是二分,对于浮点数相关的计算问题(尤其是计算几何)都难以启效,所以化虚为实,指的是把有点"虚"的浮点数,用整数来替代。具体做法是,把题目中给出的一些浮点数(不限于浮点数,我们不关心其具体大小的整数也可以)排序,然后用浮点数的序号代替本身来思考问题,等到具体计算时再替换回来。

[题目]已知n个边水平竖直的矩形(用四元组[x1,y1,x2,y2]表示),求它们的总共覆盖面积。

因为坐标可能出现浮点数,所以此题看起来十分繁复(可以实践上面由简至繁和一分为二的思路都基本无效),略一思考,矩形的覆盖关系其实只跟矩形坐标的大小有关,所以我们尝试思考将矩形的所有x值排序,然后用序号代替具体竖直,y值亦然,于是我们得到所有矩形其实处于一个2nx2n的区块当中,这样我们用最简单的穷举办法,可以计算出每一个1x1的格子是否被覆盖住了。至此,只要我们计算面积的时候,把格子的真实长宽换算回来,就已经得到题目的答案了。

以上三种思路,是我平时遇到算法问题的快速思考方向,并非万灵药方,若是不能生效,就要静下心来慢慢思考观察了,考虑到面试的时候基本不会遇到高难度算法题,这几种技巧的命中率应该不会太低,共享给大家,希望有所帮助。

本文地址:http://www.nowamagic.net/librarys/veda/detail/1018,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/1018

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《重来:更为简单有效的商业思维》 贾森•弗里德(Jason Fried) (作者), 大卫•汉森(David Heinemeier Hansson) (作者), Mike Rohde (插图作者), 李瑜偲 (译者)

这本书呈现的是一种更好、更简单的经商成功之道。读完这本书,你就会明白为什么计划实际上百害而无一益,为什么你不需要外界投资人,为什么将竞争视而不见反倒会发展得更好。事实是你所需要的比你想象的少得多。你不必成为工作狂,你不必大量招兵买马,你不必把时间浪费在案头工作和会议上,你甚至不必拥有一间办公室。所有这些都仅仅是借口!

更多计算机宝库...