稀有猿诉

十年磨一剑,历炼出锋芒,说话千百句,不如码二行。

前缀和与差分数组简介

在数组相关的问题中前缀和与差分数组是使用使用比较多的辅助数组,能有效的提升效率。前缀和就是数组中到当前元素的和;差分数组是一个辅助数组,每个元素是原数组相邻元素之差,故命名为差分数组,它在原数组区间修改等操作上能辅助提升效率。

Understanding Dijkstra Algorithm

最短路径问题,是图论中经常遇到的问题,对于非加权图,用广度优先搜索(BFS)就可以找到两个顶点之间的最短路径(最少边数),但对于加权图,就需要用到著名的犾克斯特拉算法(Dijkstra Algorithm)。

图论基础知识

图(Graph))是一个由节点和边组成的略复杂的二维数据结构,通常用于表示物体之间的关系。

理解并运用并查集

并查集Disjoint-set Data Structure)是一种树形的结构,用于处理不相交的集合的高效的查询(find)和合并(union)问题。主要有两种操作一是查询(find),也就是查询某个元素是否属于某个集合;二是合并(union),也即把某个加入到某个集合中,这里的集合都是无交集的。通过路径压缩,并查集的查询和合并都可以达到常数级别O(1)。

理解拓扑排序

拓扑排序Topological Sorting)是指将一个有向无环图(Directed Acyclic Graph)的所有顶点排成一个线性序列,使得图中的起始节点总是排在终止节点的前面,这是有向图每一个边都有起始节点和终止节点。这个名字有点容易混淆,它跟排序算法没有任何关系,拓扑排序仅是针对有向无环图,找到所有节点的一个可达的线性顺序。

记忆化搜索简介

记忆化搜索(Memorization Search),是指在做搜索过程中(比如DFS或者动态规划中)把重叠的子问题的解或者状态存储下来,以防止重复计算。最为常见的就是图搜索方法BFS和DFS时都要对已搜索过的节点进行标记以防止重复遍历,这就是一种记忆化搜索方法。再如动态规划的重复子问题,用数组进行缓存以防止重复计算,这也是一种记忆化搜索方法。

动态规划从入门到放弃

动态规划(Dynamic Programming)动态规划是用来求解具有最优子结构性质问题的一种方法。通俗的来说如果一个问题可以分成多个子问题或者分成多个步骤,每个子问题有多个解或者每个步骤有多个选择,最终求整体问题的一个最优解(最大值,最小值,方法总数,是否可行等等),这样的问题就适合用动态规划来求解。

动态规划一般可分为自顶而下式和自下而上式,自顶而下是通过递归,但因为涉及大量重复计算而导致时间复杂度过高,所以一般都是采用自下而上式,借助额外的空间来缓存子问题的解,减少重复计算从而降低时间复杂度,与记忆化搜索有点类似。

彻底搞懂背包问题

背包问题Knapsack Problem)是指给定一个容量固定为W的背包和一组数量为n的物品,每个物品的重量为wi,价值为vi,要求从物品中选择若干放入背包,使总物品重量不超过背包容量,并且使价值最大。这是动态规划的一类非常典型的问题。

贪心算法简介

贪心算法(Greedy Algorithm),又可称作贪婪算法,简称贪心,它是一指一种决策策略,依据统一的规则,在局部选择最优解,继而成为全局最优解。最经典的问题就是一类最短路径问题,从当前节点选择离它最近的节点,然后继续,到达目标节点后这一路径就是全局最短路径(这是Dijkstra算法);再如可分割的背包问题,物品有不同的重量和价值,但物品可分割,这也是贪心算法的经典应用案例。