【scarletthln 关于算法的一点总结】
1. 分解问题的角度: fix 某一维度,尝试另一维度上的所有可能
a. 可能是array的(i, j)pointers, b. 可能是矩形的长与宽, c. 可能是tree的每一个subtree, d. 可能是情景题的每一对pair...
2. 求所有解的, 暴力上backtracking吧
3. 如果问最短/最少的, 先想BFS、DP这对好基友:忘了bfs了
4. 如果环相关/重复访问, DFS + visited state雄起:忘了visited了
5. 如果问连通性, 静态靠DFS/BFS, 动态靠Union-Find:忘了动态了
6. 如果有依赖性, 想想Topologic order 和indegree
7. DAG的万能套路 DFS+memo, 再到DP
8. 建图的时候想想vertex, edges/neighbors, cost分别是什么。如果出现cycle, 别忘了给vertex增加状态
9. 树相关, 永远有backtracking 和 pure recursion两条路:啥是pure recursion啊?
10. 遇到字符串/字典/char board相关的, Trie tree总是可以试试的:用得少别怪我
11. Range里求最大/最小/sum等特征值, Segment tree会是不错的选择:用得少别怪我
12. Matrix和Array通常都是1. Two Pointers, 2. Sliding Window(fixed & not fixed), 3. DP
13. DP题型往往是: a. 问你可不可以啊, 数量有多少啊, b. 两个string上match来match去的, c. 1D/2D array 相关, d. 博弈游戏
14. 破解DAG cycle想想哪个维度是具有单调性的: 常见的steps, directions, paths
15. Reversed idea非常重要, 可能会帮助你破题: 最长可能是某种最短的反面, 最多可能是某种最少的反面, obstacle的反面是reachable, subarray的反面是array中的剩下元素, left的反面是right。:用得少别怪我
16. Look up别忘了HashMap/HashSet, HashMap + DLL是常见hybrid数据结构。:用得少别怪我
17. 找规律试试那些旁门左道: 单调Stack/双端Deque::用得少别怪我
18. 排序大法总是可以试试的::用得少别怪我
19. 时空复杂度: a. backtracking相关, 想想branching factor和height
b. DFS+memo/DP相关, 想想state数量, 以及每个state的cost
c. tree相关, 总是要考虑balanced 和 single linked list的
d. array/矩阵相关, 先数数你有多少个for loops
e. binary search application相关, 别忘了check function开销
f. stack/queue/deque相关, 常说的吃进去一次又吐出来一次
g. Java的string是朵奇葩, string concatenation不是免费的
h. 没人知道n是什么, 先告诉别人m,n,k,V,E是什么
20. 比较不同sol的trade offs: a. Time/Space complexity异同:头一次听说
b. online/offline算法
c. pre-computation cost
d. 不同APIs的call frequency差异会导致不同的时间要求
e. extension: 是否适用于generic parameters/stream input
f. 线程安全/large scale
最新文章
- ubuntu 14.04安装搜狗输入法
- Appium学习实践(二)Python简单脚本以及元素的属性设置
- 深入了解PooledConnectionFactory CachingConnectionFactory Sin
- 升级ssh编译错误
- hdu5391 Zball in Tina Town(威尔逊定理)
- C++_nullptr
- <;转>;SQL的执行顺序
- JavaScript入门(二)
- leetcode:程序员面试技巧
- Mybatis事务(二)事务隔离级别
- nginx 做数据仓库时,location 404 Not Found,发现找不到要用的数据报:Not Found
- 如何使用微信web开发者工具调试企业微信
- Java NIO4:缓冲区Buffer(续)
- 前缀和的应用 CodeForces - 932B Recursive Queries
- profile和bashrc四种的区别
- js 弹窗的实现
- TrinityCore 魔兽世界私服11159 完整配置
- 使用Jquery做分页效果
- Java中的网络编程-2
- python 推荐算法