首页 > 代码库 > 九章算法培训,第一天

九章算法培训,第一天

第一节课主要讲了SubSet,因为每次开课例子差不多,所以老师对这些题的理解与把握是比较熟悉的,

上课直接手写代码 然后直接进行点评,这点是比较赞的

 

关于一些针对面试的东西,就不多说了,

我个人是比较赞同讲师的观点的,30-45分钟的时间,

如果是让面试者写比较难的算法是不现实的,除非是事先经过精心的背诵

否则很难有人能写对KMP 红黑树之类的

 

关于SubSet的递归 讲的挺好,

递归无非三点

 

对递归进行定义

然后对递归进行拆解

递归结束的一般条件

 

因为人脑的堆栈不够用,要证明递归的正确性,我个人还是建议手动绘图的方式来说

 

对于 1,2,3 这种集合,求其全部子集,如下图

像1 2 3 6 9 10 13 这种箭头的指向就是每次的递归调用, 其余的都是递归调用返回的箭头

返回有一个明显的特点就是,返回后的 集合 比 返回前的集合少一个数,所以视频里面,在每次递归调用之后都有一句subset.remove(size-1)

 

以后想到递归的题目就先画个图,毕竟老子的堆栈还是太小了,

做这种搜索题,其实之前 我就做过很多17年的 校招算法面试题中 就有这种类型

技术分享

 

对于第二种情况,对于原集合中出现了重复元素,其实这就是在前一个问题上 剪枝 的问题,

先放图 然后注重理解图的意义,而不是 针对代码进行死磕,代码死磕是很难发现解决方案的

 

[1,2,2‘]

很明显要剪掉的在哪一块,一眼就可以 看出来

技术分享

 类似这种搜索题的 还有跳楼板 买东西 找零钱之类的,考察的并不是算法本身,更多的是考察面试者是否掌握了 将业务描述成代码实现的能力 与 思考这种问题的方法

在面试中,如果面试者能用图的方式展示出来,离代码AC其实已经不远了

 

http://www.cnblogs.com/winters1992/p/6053374.html 追加一个链接,之前做跳石板 AC的题 思路跟这题差不多

 

九章算法培训,第一天