双色球算法必中6红_经典算法专题

  本文关键词：算法，由笔耕文化传播整理发布。

随笔分类 - 经典算法专题

经典算法题每日演练——第二十五题 块状链表

摘要: 在数据结构的世界里，我们会认识各种各样的数据结构，每一种数据结构都能解决相应领域的问题，每一种数据结构都像是降龙十八掌中的某一掌，掌掌毙命。。。 当然每个数据结构，有他的优点，必然就有它的缺点，那么如何创造一种数据结构来将某两种数据结构进行扬长避短，那就非常完美了。这样的数据结构也有很多，比如：双端队列，还有就是今天讲的 块状链表， 我们都知道 数组 具有 O(1)的查询时间，O(N)的删除，O(N)的插入。。。 链表 具有 O(N)的查询时间，O(1)的删除，O(1)的插入。。。 那么现在我们就有想法了，何不让“链表”和“数组”结合起来，来一起均摊CURD的时间，做法将数...阅读全文

posted @ 2014-03-04 22:26 一线码农 阅读(4942) | 编辑

经典算法题每日演练——第二十四题 梳排序

摘要: 这篇再看看一个经典的排序，梳排序，为什么取名为梳，可能每个梳都有自己的gap吧，大梳子gap大一点，小梳子gap小一点。上一篇我们看到鸡尾酒排序是在冒泡排序上做了一些优化，将单向的比较变成了双向，同样这里的梳排序也是在冒泡排序上做了一些优化。冒泡排序上我们的选择是相邻的两个数做比较，就是他们的gap为1，其实梳排序提出了不同的观点，如果将这里的gap设置为一定的大小，效率反而必gap=1要高效的多。　下面我们看看具体思想，梳排序有这样一个1.3的比率值，每趟比较完后，都会用这个1.3去递减gap，直到gap=1时变成冒泡排序，这种算法比冒泡排序的效率要高效的多，时间复杂度为O(N2/2...阅读全文

posted @ 2014-03-02 23:59 一线码农 阅读(2587) | 编辑

经典算法题每日演练——第二十三题 鸡尾酒排序

摘要: 这篇我们继续扯淡一下鸡尾酒排序，为了知道为啥取名为鸡尾酒，特意看了下百科，见框框的话，也只能勉强这么说了。要是文艺点的话，可以说是搅拌排序，通俗易懂点的话，就叫“双向冒泡排序”，我想作为码农的话，不可能不知道冒泡排序，冒泡是一个单向的从小到大或者从大到小的交换排序，而鸡尾酒排序是双向的，从一端进行从小到大排序，从另一端进行从大到小排序。从图中可以看到，第一次正向比较，我们找到了最大值9. 第一次反向比较，我们找到了最小值1. 第二次正向比较，我们找到了次大值8. 第二次反向比较，我们找到了次小值2 。。。 ...阅读全文

posted @ 2014-03-02 11:54 一线码农 阅读(2905) | 编辑

经典算法题每日演练——第二十二题 奇偶排序

摘要: 这个专题因为各种原因好久没有继续下去了，MM吧。。。你懂的，嘿嘿，不过还得继续写下去，好长时间不写，有些东西有点生疏了，这篇就从简单一点的一个“奇偶排序”说起吧，不过这个排序还是蛮有意思的，严格来说复杂度是O(N2)，不过在多核的情况下，可以做到N2 /(m/2)的效率，这里的m就是待排序的个数，当m=100，复杂度为N2 /50，还行把，比冒泡要好点，因为重点是解决问题的奇思妙想。 下面我们看看这个算法是怎么描述的，既然是奇偶，肯定跟位数有关了1：先将待排序数组的所有奇数位与自己身后相邻的偶数位相比较，如果前者大于后者，则进行交换，直到这一趟结束。2：然后将偶数位与自己身后相邻的奇数位相..阅读全文

posted @ 2014-02-27 01:25 一线码农 阅读(2949) | 编辑

经典算法题每日演练——第二十一题 十字链表

摘要: 上一篇我们看了矩阵的顺序存储，这篇我们再看看一种链式存储方法“十字链表”，当然目的都是一样，压缩空间。一：概念 既然要用链表节点来模拟矩阵中的非零元素，肯定需要如下5个元素(row,col,val,down,right)，其中：row:矩阵中的行。col:矩阵中的列。val:矩阵中的值。right:指向右侧的一个非零元素。down：指向下侧的一个非零元素。现在我们知道单个节点该如何表示了，那么矩阵中同行的非零元素的表示不就是一个单链表吗？比如如下：那么进一步来说一个多行的非零元素的表示不就是多个单链表吗，是的，这里我把单链表做成循环链表，我们来看看如何用十字链表来表示稀疏矩阵。从上面的十...阅读全文

posted @ 2013-04-02 13:44 一线码农 阅读(11495) | 编辑

经典算法题每日演练——第二十题 三元组

摘要: 我们知道矩阵是一个非常强大的数据结构，在动态规划以及各种图论算法上都有广泛的应用，当然矩阵有着不足的地方就是空间和时间复杂度都维持在N2上，比如1w个数字建立一个矩阵，在内存中会占用1w*1w=1亿的类型空间，这时就会遇到outofmemory。。。那么面临的一个问题就是如何来压缩矩阵，当然压缩的方式有很多种，这里就介绍一个顺序表的压缩方式：三元组。一：三元组 有时候我们的矩阵中只有零星的一些非零元素，其余的都是零元素，那么我们称之为稀疏矩阵，当然没有绝对的说有多少个零元素才算稀疏。针对上面的这个无规律的存放非零元素，三元组提出了一种方法，就是仅仅记录矩阵中的非零元素以及它的行，列以及...阅读全文

posted @ 2013-03-28 19:02 一线码农 阅读(3228) | 编辑

经典算法题每日演练——第十九题 双端队列

摘要: 话说大学的时候老师说妹子比工作重要~，工作可以再换，妹子这个。。。所以。。。这两个月也就一直忙着Fall in love，嗨，慢慢调整心态吧，这篇就选一个简单的数据结构聊一聊，话说有很多数据结构都在玩组合拳，比如说：块状链表，块状数组，当然还有本篇的双端队列，是的，它就是栈和队列的组合体。一：概念我们知道普通队列是限制级的一端进，另一端出的FIFO形式，栈是一端进出的LIFO形式，而双端队列就没有这样的限制级，也就是我们可以在队列两端进行插入或者删除操作。二：编码1：定义结构体通常情况下，队列的内部都是采用数组来实现，而且带有两个指针head和tail来指向数组的区间段，为了充分利用数组空间.阅读全文

posted @ 2013-03-20 18:09 一线码农 阅读(3769) | 编辑

经典算法题每日演练——第十八题 外排序

摘要: 说到排序，大家第一反应基本上是内排序，是的，算法嘛，玩的就是内存，然而内存是有限制的，总有装不下的那一天，此时就可以来玩玩外排序，当然在我看来，外排序考验的是一个程序员的架构能力，而不仅仅局限于排序这个层次。一：N路归并排序1.概序 我们知道算法中有一种叫做分治思想，一个大问题我们可以采取分而治之，各个突破，当子问题解决了，大问题也就KO了，还有一点我们知道内排序的归并排序是采用二路归并的，因为分治后有LogN层，每层两路归并需要N的时候，最后复杂度为NlogN，那么外排序我们可以将这个“二”扩大到M，也就是将一个大文件分成M个小文件，每个小文件是有序的，然后对应在内存中我们开M个优先队...阅读全文

posted @ 2012-12-19 14:44 一线码农 阅读(10064) | 编辑

经典算法题每日演练——第十七题 Dijkstra算法

摘要: 或许在生活中，经常会碰到针对某一个问题，在众多的限制条件下，如何去寻找一个最优解？可能大家想到了很多诸如“线性规划”，“动态规划”这些经典策略，当然有的问题我们可以用贪心来寻求整体最优解，在图论中一个典型的贪心法求最优解的例子就莫过于“最短路径”的问题。一：概序 从下图中我要寻找V0到V3的最短路径，你会发现通往他们的两点路径有很多：V0->V4->V3，V0->V1->V3，当然你会认为前者是你要找的最短路径，那如果说图的顶点非常多，你还会这么轻易的找到吗？下面我们就要将刚才我们那点贪心的思维系统的整理下。二：构建 如果大家已经了解Prim算法，那么Dijkstra算阅读全文

posted @ 2012-12-18 12:14 一线码农 阅读(6736) | 编辑

经典算法题每日演练——第十六题 Kruskal算法

摘要: 这篇我们看看第二种生成树的Kruskal算法，这个算法的魅力在于我们可以打一下算法和数据结构的组合拳，很有意思的。一：思想 若存在M={0,1,2,3,4,5}这样6个节点，我们知道Prim算法构建生成树是从”顶点”这个角度来思考的，然后采用“贪心思想”来一步步扩大化，最后形成整体最优解，而Kruskal算法有点意思，它是站在”边“这个角度在思考的，首先我有两个集合。1. 顶点集合(vertexs)： 比如M集合中的每个元素都可以认为是一个独根树（是不是想到了并查集？）。2.边集合(edges)： 对图中的每条边按照权值大小进行排序。（是不是想到了优先队列？）好了，下面该如何操作呢？...阅读全文

posted @ 2012-12-17 00:28 一线码农 阅读(3865) | 编辑

经典算法题每日演练——第十五题 并查集

摘要: 这一篇我们看看经典又神奇的并查集，顾名思义就是并起来查，可用于处理一些不相交集合的秒杀。一：场景 有时候我们会遇到这样的场景，比如:M={1,4,6,8},N={2,4,5,7}，我的需求就是判断{1,2}是否属于同一个集合，当然实现方法有很多，一般情况下，普通青年会做出O(MN)的复杂度，那么有没有更轻量级的复杂度呢？嘿嘿，并查集就是用来解决这个问题的。二：操作 从名字可以出来，并查集其实只有两种操作，并(Union)和查(Find)，并查集是一种算法，所以我们要给它选择一个好的数据结构，通常我们用树来作为它的底层实现。1.节点定义 1 #region 树节点 2 ...阅读全文

posted @ 2012-12-16 15:00 一线码农 阅读(3753) | 编辑

经典算法题每日演练——第十四题 Prim算法

摘要: 图论在数据结构中是非常有趣而复杂的，作为web码农的我，在实际开发中一直没有找到它的使用场景，不像树那样的频繁使用，不过还是准备仔细的把图论全部过一遍。一：最小生成树 图中有一个好玩的东西叫做生成树，就是用边来把所有的顶点联通起来，前提条件是最后形成的联通图中不能存在回路，所以就形成这样一个推理：假设图中的顶点有n个，则生成树的边有n-1条，多一条会存在回路，少一路则不能把所有顶点联通起来，如果非要在图中加上权重，则生成树中权重最小的叫做最小生成树。对于上面这个带权无向图来说，它的生成树有多个，同样最小生成树也有多个，因为我们比的是权重的大小。二：Prim算法求最小生成树的算法有很多...阅读全文

posted @ 2012-12-12 19:12 一线码农 阅读(4358) | 编辑

经典算法题每日演练——第十三题 赫夫曼树

摘要: 赫夫曼树又称最优二叉树，也就是带权路径最短的树，，对于赫夫曼树，我想大家对它是非常的熟悉，也知道它的应用场景，但是有没有自己亲手写过，这个我就不清楚了，不管以前写没写，这一篇我们来玩一把。一：概念赫夫曼树里面有几个概念，也是非常简单的，先来看下面的图：1. 基础概念<1> 节点的权： 节点中红色部分就是权，在实际应用中，我们用“字符”出现的次数作为权。<2> 路径长度：可以理解成该节点到根节点的层数，比如：“A”到根节点的路径长度为3。<3> 树的路径长度：各个叶子节点到根节点的路径长度总和，用WPL标记。最后我们要讨论的的赫夫曼树也就是带权路径长度最小的一棵阅读全文

posted @ 2012-12-09 14:27 一线码农 阅读(4998) | 编辑

经典算法题每日演练——第十二题 线段树

摘要: 这一篇我们来看树状数组的加强版线段树，树状数组能玩的线段树一样可以玩，而且能玩的更好，他们在区间求和，最大，平均等经典的RMQ问题上有着对数时间的优越表现。一：线段树 线段树又称"区间树”，在每个节点上保存一个区间，当然区间的划分采用折半的思想，叶子节点只保存一个值，也叫单元节点，所以最终的构造就是一个平衡的二叉树，拥有CURD的O(lgN)的时间。从图中我们可以清楚的看到[0-10]被划分成线段的在树中的分布情况，针对区间[0-N]，最多有2N个节点，由于是平衡二叉树的形式也可以像堆那样用数组来玩，不过更加耗费空间，为最多4N个节点，在针对RMQ的问题上，我们常常在每个节点上增加一阅读全文

posted @ 2012-12-08 00:37 一线码农 阅读(3300) | 编辑

经典算法题每日演练——第十一题 Bitmap算法

摘要: 在所有具有性能优化的数据结构中，我想大家使用最多的就是hash表，是的，在具有定位查找上具有O(1)的常量时间，多么的简洁优美，但是在特定的场合下：①：对10亿个不重复的整数进行排序。②：找出10亿个数字中重复的数字。当然我只有普通的服务器，就算2G的内存吧，在这种场景下，我们该如何更好的挑选数据结构和算法呢？一：问题分析 这年头，大牛们写的排序算法也就那么几个，首先我们算下放在内存中要多少G: (10亿 * 32)/(1024*1024*1024*8)=3.6G，可怜的2G内存直接爆掉，所以各种神马的数据结构都玩不起来了，当然使用外排序还是可以解决问题的，由于要走IO所以暂时剔除，因为...阅读全文

posted @ 2012-12-06 12:59 一线码农 阅读(12354) | 编辑

经典算法题每日演练——第十题 树状数组

摘要: 有一种数据结构是神奇的，神秘的，它展现了位运算与数组结合的神奇魅力，太牛逼的，它就是树状数组，这种数据结构不是神人是发现不了的。一：概序 假如我现在有个需求，就是要频繁的求数组的前n项和，并且存在着数组中某些数字的频繁修改，那么我们该如何实现这样的需求？当然大家可以往真实项目上靠一靠。① 传统方法：根据索引修改为O(1)，但是求前n项和为O(n)。②空间换时间方法：我开一个数组sum[]，sum[i]=a[1]+....+a[i]，那么有点意思，求n项和为O(1)，但是修改却成了O(N)，这是因为我的Sum[i]中牵 涉的数据太多了，那么问题来了，我能不能在相应的...阅读全文

posted @ 2012-12-05 12:50 一线码农 阅读(5565) | 编辑

经典算法题每日演练——第九题 优先队列

摘要: 前端时间玩小爬虫的时候，我把url都是放在内存队列里面的，有时我们在抓取url的时候，通过LCS之类的相似度比较，发现某些url是很重要的，需要后端解析服务器优先处理，针对这种优先级比较大的url，普通的队列还是苦逼的在做FIFO操作，现在我们的需求就是优先级大的优先服务，要做优先队列，非堆莫属。一：堆结构 1:性质 堆是一种很松散的序结构树，只保存了父节点和孩子节点的大小关系，并不规定左右孩子的大小，不像排序树那样严格，又因为堆是一种完全二叉树，设节点为i,则i/2是i的父节点，2i是i的左孩子，2i+1是i的右孩子，所以在实现方式上可以采用轻量级的数组。2：用途 如果大家玩过微...阅读全文

posted @ 2012-12-03 16:33 一线码农 阅读(5944) | 编辑

经典算法题每日演练——第八题 AC自动机

摘要: 上一篇我们说了单模式匹配算法KMP，现在我们有需求了，我要检查一篇文章中是否有某些敏感词，这其实就是多模式匹配的问题。当然你也可以用KMP算法求出，那么它的时间复杂度为O(c*(m+n))，c：为模式串的个数。m：为模式串的长度,n:为正文的长度，那么这个复杂度就不再是线性了，我们学算法就是希望能把要解决的问题优化到极致，这不，AC自动机就派上用场了。 其实AC自动机就是Trie树的一个活用，活用点就是灌输了kmp的思想，从而再次把时间复杂度优化到线性的O(N)，刚好我前面的文章已经说过了Trie树和KMP，这里还是默认大家都懂。一：构建AC自动机同样我也用网上的经典例子，现有say sh..阅读全文

posted @ 2012-12-02 16:11 一线码农 阅读(6678) | 编辑

经典算法题每日演练——第七题 KMP算法

摘要: 在大学的时候，应该在数据结构里面都看过kmp算法吧，不知道有多少老师对该算法是一笔带过的，至少我们以前是的，确实kmp算法还是有点饶人的，如果说红黑树是变态级的，那么kmp算法比红黑树还要变态，很抱歉，每次打kmp的时候，输入法总是提示“看毛片”三个字,嘿嘿，就叫“看毛片算法”吧。一：BF算法 如果让你写字符串的模式匹配，你可能会很快的写出朴素的bf算法，至少问题是解决了，我想大家很清楚的知道它的时间复杂度为O（MN），原因很简单，主串和模式串失配的时候，我们总是将模式串的第一位与主串的下一个字符进行比较，所以复杂度高在主串每次失配的时候都要回溯，图我就省略了。二：KMP算法 刚才我们...阅读全文

posted @ 2012-12-01 01:57 一线码农 阅读(8293) | 编辑

经典算法题每日演练——第六题 协同推荐SlopeOne 算法

摘要: 相信大家对如下的Category都很熟悉，很多网站都有类似如下的功能，“商品推荐”,"猜你喜欢“，在实体店中我们有导购来为我们服务，在网络上我们需要同样的一种替代物，如果简简单单的在数据库里面去捞，去比较，几乎是完成不了的,这时我们就需要一种协同推荐算法，来高效的推荐浏览者喜欢的商品。一：概念 SlopeOne的思想很简单，就是用均值化的思想来掩盖个体的打分差异，举个例子说明一下：在这个图中，系统该如何计算“王五“对”电冰箱“的打分值呢？刚才我们也说了，slopeone是采用均值化的思想,也就是：R王五=4-{[(5-10)+(4-5)]/2}=7 。下面我们看看多于两项的商品，如.阅读全文

posted @ 2012-11-22 14:43 一线码农 阅读(6691) | 编辑

经典算法题每日演练——第五题 字符串相似度

摘要: 这篇我们看看最长公共子序列的另一个版本，求字符串相似度(编辑距离)，我也说过了，这是一个非常实用的算法，在DNA对比，网页聚类等方面都有用武之地。一：概念 对于两个字符串A和B，通过基本的增删改将字符串A改成B，或者将B改成A，在改变的过程中我们使用的最少步骤称之为“编辑距离”。比如如下的字符串：我们通过种种操作，痉挛之后编辑距离为3，不知道你看出来了没有？二：解析 可能大家觉得有点复杂，不好理解，我们试着把这个大问题拆分掉，将"字符串 vs 字符串“，分解成”字符 vs 字符串“，再分解成”字符 vs 字符“。<1> ”字符“vs”字符“ 这种情况是最简单的了，比如”A阅读全文

posted @ 2012-11-11 23:45 一线码农 阅读(7510) | 编辑

经典算法题每日演练——第四题 最长公共子序列

摘要: 一： 作用 最长公共子序列的问题常用于解决字符串的相似度，是一个非常实用的算法，作为码农，此算法是我们的必备基本功。二：概念 举个例子，cnblogs这个字符串中子序列有多少个呢？很显然有27个，比如其中的cb,cgs等等都是其子序列，我们可以看出子序列不见得一定是连续的，连续的那是子串。 我想大家已经了解了子序列的概念，那现在可以延伸到两个字符串了，那么大家能够看出：cnblogs和belong的公共子序列吗？在你找出的公共子序列中，你能找出最长的公共子序列吗？从图中我们看到了最长公共子序列为blog，仔细想想我们可以发现其实最长公共子序列的个数不是唯一的，可能会有两个以上，但是长度...阅读全文

posted @ 2012-11-11 00:55 一线码农 阅读(40037) | 编辑

经典算法题每日演练——第三题 猴子吃桃

摘要: 猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾就多吃了一个。第二天早上又将剩下的桃子吃了一半，还是不过瘾又多吃了一个。以后每天都吃前一天剩下的一半再加一个。到第10天刚好剩一个。问猴子第一天摘了多少个桃子？分析: 这是一套非常经典的算法题，这个题目体现了算法思想中的递推思想，递归有两种形式，顺推和逆推，针对递推，只要 我们找到递推公式，问题就迎刃而解了。 令S10=1，容易看出S9=2(S10+1)，简化一下 S9=2S10+2 S8=2S9+2 ..... Sn=2Sn+1+2遥想公瑾当年，老师说递归是最...阅读全文

posted @ 2012-08-08 12:40 一线码农 阅读(13464) | 编辑

经典算法题每日演练——第二题 五家共井

摘要: 古代数学巨著《九章算数》中有这么一道题叫“五家共井，甲二绠（汲水用的井绳）不足，如（接上）乙一绠；乙三绠不足，如丙一绠；丙四绠不足，如丁一绠；丁五绠不足，如戊一绠；戊六绠不足，如甲一绠，皆及。意思就是说五家人共用一口井，甲家的绳子用两条不够，还要再用乙家的绳子一条才能打到井水；乙家的绳子用三条不够，还要再用丙家的绳子一条才能打到井水；丙家的绳子用四条不够，还要再用丁家的绳子一条才能打到井水；丁家的绳子用五条不够，还要再用戊家的绳子一条才能打到井水；戊家的绳子用六条不够，还要再用甲家的绳子一条才能打到井水。最后问：井有多深？每家的绳子各有多长？分析：同样这套题也是属于不定方程，拿这个题...阅读全文

posted @ 2012-08-06 16:57 一线码农 阅读(10715) | 编辑

经典算法题每日演练——第一题 百钱买百鸡

摘要: 百钱买百鸡的问题算是一套非常经典的不定方程的问题，题目很简单：公鸡5文钱一只，母鸡3文钱一只，小鸡3只一文钱，用100文钱买一百只鸡,其中公鸡，母鸡，小鸡都必须要有，问公鸡，母鸡，小鸡要买多少只刚好凑足100文钱。分析：估计现在小学生都能手工推算这套题，只不过我们用计算机来推算，我们可以设公鸡为x，母鸡为y，小鸡为z，那么我们 可以得出如下的不定方程， x+y+z=100, 5x+3y+z/3=100， 下面再看看x，y，z的取值范围。 由于只有100文钱，则5x<100 => 0<x<20, 同理 0<y<33,那么z=100-x-y， 好，我们...阅读全文

posted @ 2012-08-05 20:22 一线码农 阅读(28091) | 编辑

  本文关键词：算法，由笔耕文化传播整理发布。