算法题分类及解题思路
source link: http://www.ideawu.net/blog/archives/1079.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
* 暴力破解(brute force)
暴力破解, 就是穷举. 穷举的方式一般用递归, O(n^2). 优化的思路是减少递归步骤:
1. 更加严格的静态递归条件
2. 增加 close_list, 动态地判断是否需要进行递归, close_list 根据执行情况动态变化
另外的一种优化方向是消除递归. 因为递归是可以通过递归栈 open_list 来消除的. 可以对栈进行动态排序, 优先进行最可能成功的下一个步骤(A*). 这种排序优化, 导致可以使用不同的数据结构来存储递归栈: stack, queue, priority_queue.
有序性, 有序子集: 有一种非常常用的优化思路是利用输入条件的局部有序性(存在有序的子集), 不再穷举这些有序的子集. 在处理这些有序子集时, 采用 O(n) 或者 O(K) 算法, 最差也能采用二分法 O(logN), 而且其它元素与这些有序子集结合时, 也不再需要穷举.
A* 算法: open_list 根据沉没成本G和未来成本(H)之和来决定下一个处理步骤, 达成即最优.
* 动态规划(dynamic programming)
动态规划与暴力破解类似, 都是分而治之的思路, 但又不相同. 动态规划的下一个处理步骤是唯一的, 而且 open_list 初始可以确定, 后续单调递减. 下一个步骤的处理除了依赖自身的静态条件, 还依赖之前的处理结果集, 并维护这个结果集. 有点像消除了递归之后的暴力破解, 但暴力破解的 open_list 不是初始固定的.
* 直观解法(coding)
这类问题的解法非常直观, 一般没有算法上的优化空间, 也不需要技巧, 纯粹是为了训练编程能力. 考察做题者对变量的状态判断是否完备充分, 判断路径是否最简, if 分支是否可以合并等等. 所以, 就是考察边界条件的判断, 还有逻辑条件精减, 要求有非常强的逻辑思维能力.
一般这类题就是链表翻转, 有序链表合并, 删除重复元素, 数组遍历(螺旋向内, 螺旋向外, 蛇形, 等等), partition 等.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK