一：作用最长公共子序列的问题常用于解决字符串的相似度，是一个非常实用的算法，作为码农，此算法是我们的必备基本功。二：概念举个例子，cnblogs这个字符串中子序列有多少个呢？很显然有27个，比如其中的cb,cgs等等都是其子序列，我们可以看出子序列不见得一定是连续的，连续的那是子串。我想大家已经了解了子序列的概念，那现在可以延伸到两个字符串了，你可以看出 cnblogs 和 belong 的公共子序列吗？在你找出的公共子序列中，...
前段时间玩小爬虫的时候，我把url都是放在内存队列里面，有时我们在抓取url的时候，通过LCS之类的相似度比较，发现某些url是很重要的，需要后端解析服务器优先处理，针对这种优先级比较大的url，普通的队列还是苦逼的在做FIFO操作，现在我们的需求就是优先级大的优先服务，要做优先队列，非堆莫属。一：堆结构1:性质堆是一种很松散的序结构树，只保存了父节点和孩子节点的大小关系，并不规定左右孩子的大小，不像排序树那样严格，又...
在所有具有性能优化的数据结构中，我想大家使用最多的就是hash表，是的，在定位查找场景上具有O(1)的常量时间，多么的简洁优美，但是在特定的场合下：①：对10亿个不重复的整数进行排序。②：找出10亿个数字中重复的数字。当然我只有普通的服务器，就算2G的内存吧，在这种场景下，我们该如何更好的挑选数据结构和算法呢？一：问题分析这年头，大牛们写的排序算法也就那么几个，首先我们算下放在内存中要多少G: (10亿 32)/(10241024...
在所有具有性能优化的数据结构中，我想大家使用最多的就是hash表，是的，在定位查找场景上具有O(1)的常量时间，多么的简洁优美，但是在特定的场合下：①：对10亿个不重复的整数进行排序。②：找出10亿个数字中重复的数字。当然我只有普通的服务器，就算2G的内存吧，在这种场景下，我们该如何更好的挑选数据结构和算法呢？一：问题分析这年头，大牛们写的排序算法也就那么几个，首先我们算下放在内存中要多少G: (10亿 32)/(10241024...
数据结构和算法介绍 什么是数据结构和算法 广义上，数据结构就是一组数据的存储结构，算法就是操作数据结构的一种方法。程序 = 数据结构 + 算法结构是数据元素之间不是独立的，存在特定的关系，数据结构指的是数据对象中数据元素之间的关系。 算法的概念 算法是计算机处理信息的本质，用过算法来告诉计算机如何执行程序。算法是一种解决问题的方法和思想 算法的5大特性 输入输出有穷性确定性可行性 算法的效率的衡量 好的算法可以优...
title: Day36-数据结构与算法-算法策略 date: 2021-02-01 10:44:30 tags: Liu_zimo常用的经典数据结构递归（Recursion） 递归：函数(方法)直接或间接调用自身。是一种常用的编程技巧如果递归调用没有终止，将会一直消耗栈空间 最终导致栈内存溢出（Stack Overflow) 所以必需要有一个明确的结束递归的条件 也叫作边界条件、递归基 注意：使用递归不是为了求得最优解，是为了简化解决问题的思路，代码会更加简洁递归求出来的很有可能...
我们知道，二叉查找树相对来说比较容易形成最坏的链表情况，所以前辈们想尽了各种优化策略，包括AVL，红黑，以及今天要讲的Treap树。Treap树算是一种简单的优化策略，这名字大家也能猜到，树和堆的合体，其实原理比较简单，在树中维护一个"优先级“，”优先级“采用随机数的方法，但是”优先级“必须满足根堆的性质，当然是“大根堆”或者“小根堆”都无所谓，比如下面的一棵树：从树中我们可以看到：节点中的key满足“二叉查找树”...
我们知道AVL树为了保持严格的平衡，所以在数据插入上会呈现过多的旋转，影响了插入和删除的性能，此时AVL的一个变种伸展树（Splay）就应运而生了，我们知道万事万物都遵循一个“八二原则“，也就是说80%的人只会用到20%的数据，比如说我们的“QQ输入法”，平常打的字也就那么多，或许还没有20%呢。一：伸展树1：思想伸展树的原理就是这样的一个”八二原则”，比如我要查询树中的“节点7”，如果我们是AVL的思路，每次都查询“节点7...
说到排序，大家第一反应基本上是内排序，是的，算法嘛，玩的就是内存，然而内存是有限制的，总有装不下的那一天，此时就可以来玩玩外排序，当然在我看来，外排序考验的是一个程序员的架构能力，而不仅仅局限于排序这个层次。一：N路归并排序1.概序我们知道算法中有一种叫做分治思想，一个大问题我们可以采取分而治之，各个突破，当子问题解决了，大问题也就KO了，还有一点我们知道内排序的归并排序是采用二路归并的，因为分治后有L...
开头 这里是一些个人开发者接私活和自己做软件加广告的一些科普知识。可是做软件，需要服务器，需要后台，对于一些小的开发者，想赚点广告费而又不想做后台使用服务器的人来说，网上提供了一些免费的接口，可以供我们使用，提供了许多数据。在这里我分享两个不错的提供WEB服务的网站。 一丶岗位职责 首先我们先看一下岗位职责1、负责安卓移动平台开发工作 2.Android框架开发和维护，SDK开发技术架构升级优化，提升业务研发效率二丶...
第一，散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。 第二，散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)。 第三，笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，...
Java数据结构和算法（十）——二叉树 接下来我们将会介绍另外一种数据结构——树。二叉树是树这种数据结构的一员，后面我们还会介绍红黑树，2-3-4树等数据结构。那么为什么要使用树？它有什么优点？前面我们介绍数组的数据结构，我们知道对于有序数组，查找很快，并介绍可以通过二分法查找，但是想要在有序数组中插入一个数据项，就必须先找到插入数据项的位置，然后将所有插入位置后面的数据项全部向后移动一位，来给新数据腾出空...
目录10.1 贪婪算法10.1.1 调度问题10.1.1.1 单处理器10.1.1.2 多处理器10.1.2 Huffman编码哈夫曼算法10.1.3 近似装箱问题10.1.3.1 联机算法1. 下项适合算法2. 首次适合算法3. 最佳适合算法10.1.3.2 脱机算法10.2 分治算法10.2.1 分治算法的运行时间10.2.2 最近点问题10.2.3 选择问题10.2.4 一些运算问题的理论改进10.2.4.1 整数相乘10.2.4.2 矩阵乘法10.3 动态规划10.3.1 用一个表代替递归10.3.2 矩阵乘法的顺序安排10.3.3 最优二叉...
Java数据结构和算法（八）——递归 记得小时候经常讲的一个故事：从前有座山，山上有座庙，庙里有一个老和尚和一个小和尚，一天，老和尚给小和尚讲了一个故事，故事内容是“从前有座山，山上有座庙，庙里有一个老和尚和一个小和尚，一天，老和尚给小和尚讲了一个故事，故事内容......”什么是递归，上面的小故事就是一个明显的递归。以编程的角度来看，程序调用自身的编程技巧称为递归（ recursion）。百度百科中的解释是这样的：递...
数据结构与算法 关于数据结构组织-例_图书的摆放 一、定义：数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义的函数来给出。（定义并不唯一） 二、对定义的解释（举例） 1、如何在书架上摆放图书？ <1>新书怎么插入？ <2>怎么找到某本指定的书？ 方法1：随便放 方便新书插入，但极不方便找到某本指定的书。 方法2：按照书名的拼音字母顺序排放 用二分查找法查找指定的书，方便...