Python语言目前是最火的语言之一，语法简单，功能强大，最新的TIOBE已公布2020年6月的编程语言排行榜，Python已经连续多个月都在前三甲了，非常火爆！
现在学习Python的同学越来越多，面试的环节，很多面试官让你任选语言进行编程。Python因为简单，很多小伙伴愿意用Python进行答题。最近我们的一个粉丝交流群，有一位同学跟我分享了他面试的经历。小李学了Python大概有2年多了，他跟我讲了前段时间面试某杭州大厂的一道面试题，注意是面试题，不是笔试卷。
现场让你手写代码，压力山大啊～～也许是因为紧张的原因，也许是因为自己算法基础底子不深的原因，反正现场憋了很久，没有憋出来。到底是什么样的一个算法题呢，一起来看一下。
题目：
假设你手上有面值1块，2块，5块各若干张纸币，你现在需要支付给商家6元钱，请问你有多少种组合，列出每一种组合？
要求：
1).在白板上手写代码或者直接在电脑上写
2).分析你的算法，如何优化
3).对搜索的结果进行分析
看起来这个问题似乎很简单，就是一个空间组合搜索，然后加起来的面值为6即可，但是现场面试给你思考的时间，不会超过1分钟。小李当时就心里咯噔一下，leetcode的题目少刷了，其实面试之前也准备了，刷了一些算法题，但是还是手生了一些。
大家可以思考一下，如果是你的话，你先不看下面的答案，现场手写能写出来吗？
思路：
这个题目其实网上也很多类似的，就是钞票的选取方案而已，一般的解法都是递归。递归只要设计出口即可。如果我们的方案等于6元即退出，如果超过了6元就放弃，如果不足6元就继续添加更多的钞票即可。
bills是钞票面额的列表(假如为[1,2,5]),然后target是目标值(假如为6),然后填入一个空列表的方案 solution
- 如果总金额等于target就打印solution;
- 如果大于总金额就放弃；
- 上面两种都不满足的时候，就是金额不够的情况，进行一个递归搜索，这里等于设计一个容器ways(用来存放方案，直接复制solution 列表)，然后不断的加入一张钞票进行递归；
如果能现场写出来这个代码，并且运行成功，其实还是蛮厉害的，走到这一步，相信至少能拿到及格的分数了。但是面试官会进行第二次的提问，你觉得这个算法哪里有问题，怎么解决？
确实这个里面有很多重复的方案，比如[1,1,1,1,2]和[1,1,1,2,1]就是完全重复的，我们需要取重复。
很明显上面的搜索是大而全的，就是有很多浪费的空间，如果我们的搜索的样本很大的话，就会有很多浪费的空间，这样的效率肯定是低的，如何优化呢？
有的同学说可以保存结果然后进行取重复，但是这样要等整个的结果出来才行；有没有办法在搜索空间算法上动手脚呢？
我们来看一些优化后的代码：
是不是过滤了很多重复的方案，我们在搜索的方案里面加一个新参数bigger，就是当前的已经生成的最高的面额，在搜索的过程中，我们只能append那些大于等于已经加入的最高的面额钞票，低的我们就不卖了。
当然还有其他的解决办法，其实如果回答出这个参数，相信会给面试官加分不少，说明在工作的时候，并不是一个只知道完成任务的，还是一个喜欢勤思考会优化代码的人。其实面试的时候回答出这一步，已经是可以拿到良好分了。
上面的结果都是在通过print打印在内存里面，如果我们需要对整个的搜索的空间进行进一步的处理，比如我们有100种方案，我们需要保存到文件中或者数据库里面进一步的分析，如果把递归的结果提取出来呢？
第一种，简单粗暴：
我们直接用全局变量，在整个函数的外部加一个out=[]，来存储所有的组合：
第二种,优雅的方式
全局变量固然简单，但是在生产的环境的项目里面，这肯定不是最佳的解法。最好的方法还是在函数内自己存储，然后我们只要在调用的时候获取即可。这里我们用Python里面的生成器yield来搞定。
通过yield来缓存递归过程的结果，是不是非常优雅。这个时候我们对所有的组合可以进行分析，比如我想找到用钞票最少的组合，就可以这样：
小编说两句：
其实整个这道面试题，如果是放在笔试题里面，相信大部分的同学都可以答出来，难度其实并不大。但是在面试的环节，就会难很多，一个紧张，二个思考的时间非常短，需要平时有深厚的积累！
建议参加大厂的面试，多多少少都要准备一下尤其是算法。一定要多刷一些leetcode的题目，不要照搬照套，一定要理解并且把代码学到肚子里去，实在不行，先把代码思路背下来，这样有备无患，毕竟临阵磨枪，不快也光！好了，希望今天的文章对大家有帮助。
目前wx搜索Python 【菜鸟学Python】排第二，汇聚了30万Python爱好者，累计原创近400篇趣味干货(爬虫，数据分析，算法，面试指南，原创趣味实战，Python游戏，机器学习），欢迎一起学Python，交流指正。
网友评论