|
程序 = 数据结构 + 算法 先有数据，再有算法，所以在设计时，都是以数据结构为出发点来进行设计的。另一方面，如果你有了具体的算法，也可以根据具体情况对数据结构进行改进。 如何保存一堆东西？ --》数据结构 set： 将一堆散乱的东西存放在一个容器里面 然而数据本身是没有顺序的，如何保存顺序关系？ 方法1: array：将数据连续有序的排成一排 方法2： linkedlist: 将各个数据之间用指针连接
如何处理这些数据？ --》算法 怎么计算这些数据就是算法部分所关注的内容。同样的一堆数据（相同的input），根据不同需求，要求得到不同的处理结果（output），那么我们就会使用不同的算法。个人理解，算法就是处理计算数据的具体方法，我们在课本中学到的各种排序算法，贪心，动态规划算法都是一些业界前辈多年研究的结果，可以供我们直接使用。最简单的例子，要排序一堆数据，那么常用的就是mergesort， quick sort等，当然具体情况具体分析，各种算法各有优劣。但大致都在这个框架里面，套用一句网络流行语就是：这，都是套路。话虽如此，但如果咱能把每个算法的深入的学习理解，还是可以从中学到很多思考以及解决问题的方法。 举个具体算法的例子： 如何判断某些数据是否存在？
那么又如何加速查找呢？ 继续上面找人的例子，如果你知道要找的目标的身高，那么让所有人按照从左到右从矮到高的身高顺序依次排列，你可以先寻问站在最中间的人的身高，如果他比你要找的人高，那么你的目标一定在此人的左边，此人右边的所有人都可以排除掉了。反之亦然。这样，每次的搜索规模就能减小一半，大大的节约了搜索时间。 对于数据是同样的道理，如果数据是已排序的，那么每次可以从有效区间的中间点开始查找，如果正好等于要找的元素，直接返回。若小于要查找的元素，则有效区间可以缩小为该中间点的左边，反之中间点右边。 这种方法是一种确定性贪心。 这种算法可以由两种不同的底层数据结构支持该算法：array和binarysearch tree 另外一个有趣的算法问题就是，如何遍历整个Tree？ 方法1：DFS 方法2: BFS 知识整合 算法题： input： 一个有向图 output： 从头部到叶子的最小路径 每个点，记录一个值distance代表从根节点到达改点的最段距离，从可达到它的所有路径中，选择最短的路径长度。以图中2点为例，分别可以从3和5达到它，distance(2)= min(distance(3), distance(5)) + 2 这就是我们常说的动态规划（DP）: 由上一层的答案推导出下一层的答案，即k + 1层答案是由k层答案得到的。 动态规划一共做了三件事： 1. 解空间转换 以上题为例，每个点除了它原本的数据值，还多存了一个额外的值distance，此时每个点的语义就和原来的语义有所不同 2.BFS 3.贪心：确定性贪心 本文整理作者：陈微，更多精彩内容，欢迎访问官网 BitTiger.io 或关注 “论码农的自我修养” 微信公众号：bit_tiger |
|
|
