算法速成（九）队列

2016年07月27日 38 阅读

算法速成（九）队列2014-04-28 csdn 特种兵—AK47可能大家都知道，线性表的变种非常非常多，比如今天讲的“队列”，灰常有意思啊。一：概念队列是一个”先进先出“的线性表，牛X的名字就是“First in First Out（FIFO）”，生活中有很多这样的场景，比如读书的时候去食堂打饭时的”排队“。当然我们拒绝插队。二：存储结构 前几天也说过，线性表...

算法速成（十）栈

2016年07月27日 39 阅读

算法速成（十）栈2014-04-28 csdn博客 特种兵—AK47今天跟大家聊聊栈，在程序设计中，栈的使用还是非常广泛的，比如有“括号匹配问题“，”html 结构匹配问题“。所以说掌握了”栈“的使用，对我们学习算法还是很有帮助的。一 ： 概念栈，同样是一种特殊的线性表，是一种Last In First Out（LIFO）的形式，现实中有 很多这样的例子，比如：食堂中的一叠盘子，我们只...

算法速成（十一）树操作之基本操作

2016年07月27日 40 阅读

算法速成（十一）树操作之基本操作2014-04-28 csdn 特种兵—AK47先前我们讲的都是“线性结构”，他的特征就是“一个节点最多有一个”前驱“和一个”后继“ 。那么我们今天讲的树会是怎样的呢？我们可以对”线性结构“改造一下，变为”一个节点最 多有一个"前驱“和”多个后继“。哈哈，这就是...

算法速成（十二）树操作之线索二叉树

2016年07月27日 38 阅读

算法速成（十二）树操作之线索二叉树2014-04-28 csdn博客 特种兵—AK47先前说了树的基本操作，我们采用的是二叉链表来保存树形结构，当然二叉有二叉的困扰之处，比 如我想找到当前结点的“前驱”和“后继”，那么我们就必须要遍历一下树，然后才能定位到 该“节点”的“前驱”和“后继”，每次定位都是O（n），这不是我们想看到的，那么有什...

算法速成（十三）树操作之赫夫曼树

2016年07月27日 37 阅读

算法速成（十三）树操作之赫夫曼树2014-04-28 csdn博客 特种兵—AK47今天说下最后一种树，大家可否知道，文件压缩程序里面的核心结构，核心算法是什么？或许你知 道，他就运用了赫夫曼树。听说赫夫曼胜过了他的导师，被认为”青出于蓝而胜于蓝“，这句 话也是我比较欣赏的，嘻嘻。一 概念了解”赫夫曼树“之前，几个必须要知道 的专业名词可要熟练记住啊。1： 结点的权 “权”就相当于&l...

算法速成（十四）图之非线性数据结构

2016年07月27日 39 阅读

算法速成（十四）图之非线性数据结构2014-04-28 csdn博客 特种兵—AK47今天来分享一下图，这是一种比较复杂的非线性数据结构，之所以复杂是因为他们的数据元素之间 的关系是任意的，而不像树那样被几个性质定理框住了，元素之间的关系还是比较明显的，图 的使用范围很广的，比如网络爬虫，求最短路径等等，不过大家也不要胆怯，越是复杂的东西 越能体现我们码农的核心竞争力。既然要学习图，得要遵守一下图的游戏规则。一： 概念图是由“顶点”...

算法速成（十五）图之“最小生成树”和“最短路径”

2016年07月27日 37 阅读

算法速成（十五）图之“最小生成树”和“最短路径”2014-04-28 csdn博客 特种兵—AK47今天是大结局，说下“图”的最后一点东西，“最小生成树“和”最短路径“。一： 最小 生成树1. 概念首先看如下图，不知道大家能总结点什么。对于一个连通图G， 如果其全部顶点和一部分边构成一个子图G1，当G1满足：① 刚好将图中所有顶点连通。② 顶点不存在回路。则称G1就是G的“...

算法系列（一） Google方程式

2016年07月27日 34 阅读

算法系列（一） Google方程式2014-04-30 csdn博客 吹泡泡的小猫有一个字符组成的等式：WWWDOT - GOOGLE = DOTCOM，每个字符代表一个0－9之间的数字，WWWDOT 、GOOGLE和DOTCOM都是合法的数字，不能以0开头。请找出一组字符和数字的对应关系，使它们互相替 换，并且替换后的数字能够满足等式。这个字符等式是Google公司能力倾向测试实验室的一道题目， 这种题目主要考察人的逻辑推导能力和短期记忆能力，通常棋下的...

算法系列（二） 三只水桶等分水问题

2016年07月27日 36 阅读

算法系列（二） 三只水桶等分水问题2014-04-30 吹泡泡的小猫 有一个容积为8升的水桶里装满了水，另外还有一个容积为3升的空桶和一个容积为5升的空桶，如 何利用这两个空桶等分8升水？附加条件是三个水桶都没有体积刻度，也不能使用其它辅助容器。这是一道经典题目，一般人都可以在一分钟内给出答案，不过，很多人可能没有注意到这道题 的答案不是唯一的。先来看看最常见的一个答案，也是目前已知最快的操作步骤，共需要7次倒水动作 ：从容积是8升的桶中倒5升水到容积是5...

算法系列（三） 妖怪与和尚过河问题

2016年07月27日 39 阅读

算法系列（三） 妖怪与和尚过河问题2014-04-30 csdn博客 吹泡泡的小猫有三个和尚（或传教士）和三个妖怪（或食人怪）过河，只有一条能装下两个人（和尚或妖怪）的 船，在河的任何一方或者船上，如果妖怪的人数大于和尚的人数，那么和尚就会有被吃掉的危险。你 能不能找出一种安全的渡河方法呢？这是一个很有意思的智力题，但是并不难，每次可以选择 一个人或者两个人过河，只要保证在河的任何一边的和尚数量总是大于或等于妖怪的数量即可。这里 先给出一种过河方法：两个妖...

算法系列（四） 字符串的相似度

2016年07月27日 35 阅读

算法系列（四） 字符串的相似度2014-04-30 csdn博客 吹泡泡的小猫我们把两个字符串的相似度定义为：将一个字符串转换成另外一个字符串的代价（转换的方法可 能不唯一），转换的代价越高则说明两个字符串的相似度越低。比如两个字符串：“SNOWY”和 “SUNNY”，下面给出两种将“SNOWY”转换成“SUNNY”的方法：变换1： S - N O W Y S ...

算法系列（五）最长公共子序列（LCS）问题（非连续子序列）的两种解法

2016年07月27日 36 阅读

算法系列（五）最长公共子序列（LCS）问题（非连续子序列）的两种解法2014-04-30 csdn博客 吹泡泡的小猫最长公共子序列也称作最长公共子串，英文缩写是LCS（Longest Common Subsequence）。其定义 是：一个序列S，如果分别是两个或多个已知序列的子序列，且是符合此条件的子序列中最长的，则称 S为已知序列的最长公共子序列。关于子序列的定义通常有两种方式，一种是对子序列没有连 续的要求，其子序列的定义就是原序列中删除若干元素后得...

算法系列（六）最长公共子序列（LCS）问题（连续子序列）的三种解法

2016年07月27日 37 阅读

算法系列（六）最长公共子序列（LCS）问题（连续子序列）的三种解法2014-04-30最长公共子序列（LCS）问题有两种方式定义子序列，一种是子序列不要求不连续，一种是子序列 必须连续。上一章介绍了用两种算法解决子序列不要求连续的最终公共子序列问题，本章将介绍要求 子序列必须是连续的情况下如何用算法解决最长公共子序列问题。仍以上一章的两个字符串 “abcdea”和“aebcda”为例，如果子序列不要求连续，其...

算法系列（七） 爱因斯坦的思考题（上）

2016年07月27日 36 阅读

算法系列（七） 爱因斯坦的思考题（上）2014-04-30 csdn博客 吹泡泡的小猫这是一个很有趣的逻辑推理题，传说是爱因斯坦提出来的，他宣称世界上只有2％的人能解出这个 题目，传说不一定属实，但是这个推理题还是很有意思的。题目是这样的，据说有五个不同颜色的房 间排成一排，每个房间里分别住着一个不同国籍的人，每个人都喝一种特定品牌的饮料，抽一种特定 品牌的烟，养一种宠物，没有任意两个人抽相同品牌的香烟，或喝相同品牌的饮料，或养相同的宠物 ，问题是谁在养鱼...

算法系列（七） 爱因斯坦的思考题（下）

2016年07月27日 37 阅读

算法系列（七） 爱因斯坦的思考题（下）2014-04-30 csdn博客 吹泡泡的小猫CheckGroupRelation（）函数需要根据当前组group的位置进行适当的处理，如果当前组是第一个 组或最后一个组，则group的相邻组只有一个，就是最靠近group的组，其它情况下group的相邻组都是 两个。CheckGroupRelation（）函数的实现如下：162 bool CheckGroupRelation（GROUP *groups, int g...

算法系列（八） RLE行程长度压缩算法

2016年07月27日 40 阅读

算法系列（八） RLE行程长度压缩算法2014-04-30 csdn博客 吹泡泡的小猫RLE（Run Length Encoding）行程长度压缩算法（也称游程长度压缩算法），是最早出现、也是 最简单的无损数据压缩算法。RLE算法的基本思路是把数据按照线性序列分成两种情况：一种是连续的 重复数据块，另一种是连续的不重复数据块。对于第一种情况，对连续的重复数据块进行压缩，压缩 方法就是用一个表示块数的属性加上一个数据块代表原来连续的若干块数据。对于第二种情况...

算法系列（九） 计算几何与图形学有关的几种常用算法（一）

2016年07月27日 32 阅读

算法系列（九） 计算几何与图形学有关的几种常用算法（一）2014-04-30 csdn博客 吹泡泡的小猫我的专业是计算机辅助设计（CAD），算是一半机械一半软件，《计算机图形学》是必修课，也是 我最喜欢的课程。热衷于用代码摆平一切的我几乎将这本教科书上的每种算法都实现了一遍，这种重 复劳动虽然意义不大，但是收获很多，特别是丢弃了多年的数学又重新回到了脑袋中，算是最大的收 获吧。尽管已经毕业多年了，但是每次回顾这些算法的代码，都觉得内心十分澎湃，如果换成现在...

算法系列（九） 计算几何与图形学有关的几种常用算法（二）

2016年07月27日 39 阅读

算法系列（九） 计算几何与图形学有关的几种常用算法（二）2014-04-30 csdn博客 吹泡泡的小猫3.6 用矢量的叉积判断直线段是否有交矢量叉积计算的另一个常用用途是直线段求交。求交算 法是计算机图形学的核心算法，也是体现速度和稳定性的重要标志，高效并且稳定的求交算法是任何 一个CAD软件都必需要重点关注的。求交包含两层概念，一个是判断是否相交，另一个是求出交点。直 线（段）的求交算法相对来说是比较简单的，首先来看看如何判断两直线段是否相交。常规的 ...

算法系列（十） 直线生成算法

2016年07月27日 40 阅读

算法系列（十） 直线生成算法2014-04-30 csdn博客 吹泡泡的小猫在欧氏几何空间中，平面方程就是一个三元一次方程，直线就是两个非平行平面的交线，所以直线 方程就是两个三元一次方程组联立。但是在平面解析几何中，直线的方程就简单的多了。平面几何中 直线方程有多种形式，一般式直线方程可用于描述所有直线：Ax+By+C = 0 （A、B不同 时为0）当知道直线上一点坐标（X0，Y0）和直线的斜率K存在时，可以用点斜式方程：Y-Y0 = K（X &ndas...

算法系列（十一） 圆生成算法

2016年07月27日 39 阅读

算法系列（十一） 圆生成算法2014-04-30 csdn博客 吹泡泡的小猫在平面解析几何中，圆的方程可以描述为（x – x0）2 + （y – y0）2 = R2，其中（x0, y0）是圆心坐 标，R是圆的半径，特别的，当（x0, y0）就是坐标中心点时，圆方程可以简化为x2 + y2 = R2。在计算 机图形学中，圆和直线一样，也存在在点阵输出设备上显示或输出的问题，因此也需要一套光栅扫描 转换算法。为了简化，我们先考虑圆心在原...