What are the 10 algorithms one must know in order to solve most algorithm challenges/puzzles?
QUESTION :
What are the 10 algorithms one must know in order to solve most algorithm challenges/puzzles?
ANSWER:
Dynamic Programming (DP) appears to account for a plurality (some estimate up to a third) of contest problems. Of course, DP is also not a single algorithm that you can just learn once and retain, so maybe this doesn't answer your question.
I suppose it also depends on whether you consider data structures in the same category as algorithms. There are certainly some data structures that you should be familiar with if you want to do well in programming competitions. The most important ones are range trees (variously known as interval trees or segment trees) and binary indexed trees (BITs), also known as Fenwick trees. Additionally, many DP algorithms make use of a prefix sum array.
The most essential of the single algorithms I can think of are the following, in no particular order. However, you may be disappointed by how rarely some of these actually appear in contests. Most non-DP problems appear to be of the "ad hoc with data structures" variety, and you simply have to practice in order to get good at them.
(To be clear, again, I list below only algorithms that take a single input set, compute some function of it, and carry no state between inputs. This distinguishes them from data structures, which by definition hold state, and categories of algorithms and algorithmic techniques like DP, which don't have some specific function they compute.)
- Sieve of Eratosthenes, or another prime number sieve
- Depth-first search
- Breadth-first search
- Dijkstra's algorithm
- Floyd--Warshall algorithm
- Either Kruskal's or Prim's algorithm
- Some implementation of topological sorting, such as by using DFS
- Convex hull (I recommend the Monotone Chains algorithm)
- Coordinate compression
- Edmonds--Karp, or another implementation of the Ford--Fulkerson method; or a preflow-push algorithm; or, if you are preparing an ACM codebook, Dinic's algorithm. (Note: Max flow is not allowed to appear on the IOI, but may nevertheless appear on national team-selection contests)
-- By Brian Bi
Excerpt from :https://www.quora.com/What-are-the-10-algorithms-one-must-know-in-order-to-solve-most-algorithm-challenges-puzzles
最新文章
- 通过InputStream访问文件中的数据的四种方法
- solr&lucene3.6.0源码解析（三）
- 编译php-5.6出错，xml2-config not found
- hasOwnProperty
- 使用sudo执行命令的时候提示找不到命令
- php redis扩展
- android Vibrator 使用
- 【Android - 框架】之ButterKnife的使用
- innodb关键特性之double write
- 201521123063 《java程序设计》第六周学习总结
- 读《图解HTTP》有感-（与HTTP协作的WEB服务器）
- mysql必须知道的
- sql语句格式化数字(前面补0)
- Android4.4中jni的native的方法无法找到的解决方案
- 您需要来自XXX的权限才能对此文件夹进行更改
- python ---Pandas时间序列：生成指定范围的日期
- Python 编码问题（十四）
- laravel5.5源码笔记（七、数据库初始化）
- JDK1.7的一些新特性
- Java 字符串拼接 StringBuilder() StringBuffer