基本概念: 对于某一组数据的搜索,除非这个数据结构支持特定的查找操作(例如unordered_map的查找根据哈希公式找到对应位置,时间复杂度是O(1)),否则就要采用遍历的方式进行搜索(例如链表的搜索就是遍历的方式)。 对一组数据的搜索需要: (1)每个结点都要访问一次; (2)每个结点仅仅访问一次; (3)对于结点访问顺序的不同,分为: 深度优先遍历(DFS = Depth First Search); 广度优先遍历(BFS = Breadth First Search); 除二者之外当然还有其他的搜索优先顺序…

2020年10月31日 0条评论 1点热度 阅读全文

贪心算法中“贪心”二字形象的说明了该算法的基本思想:贪心(每一步选择都是眼下的局部最优选择)。 比如每次给你1张面额不定的纸币,共10次,你这么选?肯定是每次都要一张100元的。当你要拿第一张时,此时眼下最优的选择就是拿一张100的,不会管拿了之后会不会对后面的9张产生影响。这就是一种贪心,当然这种情况下的贪心选择也是最优的选择,因为局部最优导致了整体的最优。 贪心算法常用于求解最优解问题,比动态规划思路简单,前提是要求问题满足贪心选择性质。 形象的讲: 贪心算法的每次选择就是只看当前的利益,不管当前的选择对后面选…

2018年2月23日 0条评论 16点热度 阅读全文

贪心算法中“贪心”二字形象的说明了该算法的基本思想:贪心(每一步选择都是眼下的局部最优选择)。 比如每次给你1张面额不定的纸币,共10次,你这么选?肯定是每次都要一张100元的。当你要拿第一张时,此时眼下最优的选择就是拿一张100的,不会管拿了之后会不会对后面的9张产生影响。这就是一种贪心,当然这种情况下的贪心选择也是最优的选择,因为局部最优导致了整体的最优。 贪心算法常用于求解最优解问题,比动态规划思路简单,前提是要求问题满足贪心选择性质。 形象的讲: 贪心算法的每次选择就是只看当前的利益,不管当前的选择对后面选…

2018年2月23日 0条评论 17点热度 阅读全文

1. 什么是trie树   1.Trie树 (特例结构树)         Trie树 ,又称 单词查找树、字典树 ,是一种 树形结构 ,是一种哈希树的变种,是一种用于快速检索的多叉树结构。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比 哈希表高。      Trie的核心思想是空间换时间。利用字符串的公共前缀来…

2016年8月11日 0条评论 17点热度 阅读全文

题目描述:给定一个m行n列的整数矩阵A,试求A的一个子矩阵,使其各元素之和为最大。 方法:借助一维数组连续子序列最大和的方法,将二维数组求最大子矩阵和的问题转化为求一维数组连续子序列最大和。 矩阵形式如下:  int [][]data = { {4,-2,9},                       {-1,3,8},           &…

2016年5月20日 0条评论 16点热度 阅读全文

树的结构包括: 二叉查找树 平衡二叉树(AVL) 红黑树 B-树 B+树 字典树 后缀树 广义后缀树 二叉查找树: 如果树不是一颗空树的话,那么二叉查找树具有以下特征: 1. 若左子树不为空,那么左子树所有节点的值小于均小于他的根节点的值。 2. 若右子树不为空,那么右子树的所有节点的值大于根节点的值。 3. 左右子树也分别为二叉排序树。 4. 没有键值相等的节点。 平衡二叉树 AVL树具有性质: 它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。的性质: 红黑树 1. …

2016年4月26日 0条评论 17点热度 阅读全文

图有多种表示方法,在 《无向邻接矩阵表示法的图的遍历》这篇文章中,讲了邻接矩阵表示法的遍历,这篇文章中将讨论邻接表表示法的图的遍历。邻接矩阵表示法在稀疏图(边少的图中)中比邻接矩阵表示法节省内存空间。不管以何种方式来表示,他们的遍历顺序是没有改变的。继续贴上图,方便我们理解。 上面的图可以用下面的邻接表表示。 左边的灰色区域表示各个顶点,我们可以用数组来表示,右边的黄色区域代表着各个顶点与其他顶点的关系。 邻接表表示法深度优先遍历和广度优先遍历代码如下: package 邻接表图的遍历; import j…

2016年2月2日 0条评论 14点热度 阅读全文

假设有以下结构的图: 用邻接矩阵表示如下: 因为他是无向图,我们可以发现他的矩阵是对角对称的。矩阵中每一行每一列都可以看成是一个顶点,矩阵中的元素表示着该顶点与其他顶点的关系,当元素的值为1说明它与对应列的顶点有边相连,如果他们的值为0,表示他们没有边相连。下面我们来看看我们怎么遍历这个图。 1.深度优先遍历: 假设我们从A这个顶点开始遍历,当访问到A点的时候它会找与A相连的第一个顶点B(为什么B是第一个与A相连的顶点?请看矩阵),并且访问B,访问到B点,它会碰到到与B第一个相连的顶点A,但是A顶点已经访问过,他就…

2016年2月2日 0条评论 14点热度 阅读全文

拓扑排序是对有向无圈图的顶点的一种排序,它使得如果存在一条从vi到vj的路径,那么在排序中Vj出现在Vi后面。一个简单的求拓扑排序的算法是先找出任意一个没有入边的顶点,然后我们显示该顶点,并将它和它的边一起从图中删除。然后为们对图的其余部分应用同样的方法处理。但是这个方法有一点不好,就是每次都要找入度为0的顶点,这种顶点一般很少,如果图很大的话,每次都遍历一遍就浪费很多时间。升级版是先计算每一个顶点的入度,然后将入度为0的顶点存入队列,操作完之后再更新入度。这样就不用遍历整个图而只需要从出队列操作就可以了。下面是代…

2015年8月11日 0条评论 14点热度 阅读全文

转载自http://blog.csdn.net/xywlpo/article/details/6439048 贪心算法的设计思想          贪心算法在解决问题的策略上目光短浅,只根据当前已有的信息就做出选择,而且一旦做出了选择,不管将来有什么结果,这个选择都不会改变。换言之,贪心法并不是从整体最优考虑,它所做出的选择只是在某种意义上的局部最优。贪心算法对于大部分的优化问题都能产生最优解,但不能总获得整体最优解,通常可以获得近似最优解。 引例 [找零钱] 一个…

2014年8月28日 0条评论 12点热度 阅读全文