cloudzhou
2014-10-29 16:29:55 +08:00
这是最基本的算法，最近刚好在给人面试，自己想出来的一些题目，供大家参考：
1 走台阶问题：
很长的台阶，共有 X 级，一个大人每次可以走 m级 或者 n级，如果最后剩下不足 m级 或者 n级，那就算一步走完，问有几种不同的走法。
比如 7 级的台阶，每次可以走 2级 和 3级，有 5 种走法：
2->2->2->1
3->2->2
2->3->2
2->2->3
3->3->1
有两种解法： 1 动态规划 2 排列组合
2 能否求零问题：
给出一组正数，随意排列组合，每个正数使用且只使用一次，使用 +, - ，判断能否得到 0。
比如 {1,3,7,8,11} 那么 11 - 8 - 7 + 3 + 1 = 0。
而 {1,3,7} 那么无论怎么排列和+-都没办法得到 0。
解法：贪心求最优解
3 给出一组正数和目标值，判断能否在这组正数里每个数乘以一个非负数求和得到目标值。
比如 {3, 4} 目标值是 17，那么可以通过 3*3 + 2*4 = 17。
{3, 4} 目标值是 18，那么可以通过 6*3 + 0*4 = 18、 2*3 + 3*4 = 18 等等。
而如果 {9, 7} 目标值是 19，没办法找到合适的 非负数相乘求和 得到 19。
解法：这是一个 DFS 遍历的问题。
4 另外就是一些现实的问题，比如怎么简单实现一个 LRU cache。
解法：hash + 双向链表，能考一些编码细节。
这些题目虽然有些理论化，但是还是能看出编码能力的。