如何求两个链表的第一个公共结点

2016年07月27日 37 阅读

如何求两个链表的第一个公共结点2015-10-12题目: 输入两个链表, 找出它们的第一个公共结点.计算链表的长度, 然后移动较长链表的指针, 使其到相同结点的距离的相同, 再同时移动两个链表的指针, 找到相同元素.时间复杂度: O（n）代码:/** main.cpp**Created on: 2014.6.12*Author: Spike*//*eclipse cdt, gcc 4.8.1*/#include <stdio.h>#includ...

Geeks面试题：Box Stacking Problem

2016年07月27日 35 阅读

Geeks面试题：Box Stacking Problem2015-10-14Dynamic Programming | Set 22 （Box Stacking Problem）You are given a set of n types of rectangular 3-D boxes, where the i^th box has height h（i）, width w（i） and depth d（i） （all real numbers）. Y...

Geeks面试题：Closest Pair of Points

2016年07月27日 35 阅读

Geeks面试题：Closest Pair of Points2015-10-14Divide and Conquer | Set 2 （Closest Pair of Points）We are given an array of n points in the plane, and the problem is to find out the closest pair of points in the array. This problem arise...

二叉搜索树与双向链表的C++实现

2016年07月27日 34 阅读

二叉搜索树与双向链表的C++实现2015-10-14题目：输入一颗二叉搜索树, 将该二叉搜索树转换成一个排序的双向链表.要求不能创建任何新的结点, 只能调整数中结点的指针的指向.方法: 使用中序遍历每一个结点, 并进行连接, 即左子树指前, 右子树指后, 并保存前一个节点.本程序包含算法原理, 测试程序, 及 输出.代码:/** main.cpp**Created on: 2014.6.12*Author: Spike*//*eclipse cdt, gc...

输入一个字符串并打印出该字符串中字符的所有排列

2016年07月27日 36 阅读

输入一个字符串并打印出该字符串中字符的所有排列2015-10-14题目: 输入一个字符串, 打印出该字符串中字符的所有排列.方法: 使用递归依次交换位置, 打印输出.代码:/* * main.cpp * *Created on: 2014.6.12 *Author: Spike *//*eclipse cdt, gcc 4.8.1*/#include <stdio.h>void Permutation（char* str, char* begi...

线性表的链式表示

2016年07月27日 33 阅读

线性表的链式表示2015-10-16以下为操作链表的算法，该链表为动态单链表。链表以头指针为索引，头指针指向头节点，头节点指向首节点，以此类推，直到尾节点。头节点中不存放数据，只存放指向首节点的指针，设置头节点的目的是为了方便对链表的操作，如果不设置头节点，而是直接由头指针指向首节点，这样在对头指针后的节点进行插入删除操作时就会与其他节点进行该操作时有所不同，便要作为一种特殊情况来分析操作系统：ubuntu编译软件：gcc结果截图：源代码：#include...

搜索引擎中倒排表数据结构、通配符查询、拼写纠正详解

2016年07月27日 34 阅读

搜索引擎中倒排表数据结构、通配符查询、拼写纠正详解2015-10-16搜索引擎里的dictionary data通常存储着这些信息：索引词（term vocabulary）。文档频率（document frequency，即这个词在多少个文档里出现）。指向倒排表的指针（pointers to each postings list ）。那么，他是怎样的一个数据结构呢？一种非常naive的词典结构就是：其中，term的类型是char[20]，占20bytes，...

如何在遍历中使用iterator及reverse_iterator删除元素

2016年07月27日 35 阅读

如何在遍历中使用iterator及reverse_iterator删除元素2015-10-16众所周知，在使用迭代器遍历 STL 容器时，需要特别留意是否在循环中修改了迭代器而导致迭代器失效的情形。下面我来总结一下在对各种容器进行正向和反向遍历过程中删除元素时，正确更新迭代器的用法。本文完整源码：https://code.csdn.net/snippets/173595首先，要明白使用正向迭代器（iterator）进行反向遍历是错误的用法，要不干嘛要有反向...

解密QQ号的队列算法

2016年07月27日 35 阅读

解密QQ号的队列算法2015-10-18新学期开始了，小哈是小哼的新同桌（小哈是个小美女哦~），小哼向小哈询问QQ号，小哈当然不会直接告诉小哼啦，原因嘛你懂的。所以小哈给了小哼一串加密过的数字，同时小哈也告诉了小哼解密规则。规则是这样的：首先将第1个数删除，紧接着将第2个数放到这串数的末尾，再将第3个数删除并将第4个数再放到这串数的末尾，再将第5个数删除……直到剩下最后一个数，将最后一个数也删除。按照刚才删除的顺序，把这些删除的...

快速排序算法

2016年07月27日 31 阅读

快速排序算法2015-10-18上一节的冒泡排序可以说是我们学习第一个真正的排序算法，并且解决了桶排序浪费空间的问题，但在算法的执行效率上却牺牲了很多，它的时间复杂度达到了O（N2）。假如我们的计算机每秒钟可以运行10亿次，那么对1亿个数进行排序，桶排序则只需要0.1秒，而冒泡排序则需要1千万秒，达到115天之久，是不是很吓人。那有没有既不浪费空间又可以快一点的排序算法呢？那就是“快速排序”啦！光听这个名字是不是就觉得很高端呢。假设...

冒泡排序算法

2016年07月27日 34 阅读

冒泡排序算法2015-10-18简化版的桶排序不仅仅有上一节所遗留的问题，更要命的是：它非常浪费空间！例如需要排序数的范围是0~2100000000之间，那你则需要申请2100000001个变量，也就是说要写成int a[2100000001]。因为我们需要用2100000001个“桶”来存储0~2100000000之间每一个数出现的次数。即便只给你5个数进行排序（例如这5个数是1，1912345678，2100000000，180...

桶排序算法：最快最简单的排序算法

2016年07月27日 32 阅读

桶排序算法：最快最简单的排序算法2015-10-18在我们生活的这个世界中到处都是被排序过的。站队的时候会按照身高排序，考试的名次需要按照分数排序，网上购物的时候会按照价格排序，电子邮箱中的邮件按照时间排序……总之很多东西都需要排序，可以说排序是无处不在。现在我们举个具体的例子来介绍一下排序算法。首先出场的我们的主人公小哼，上面这个可爱的娃就是啦。期末考试完了老师要将同学们的分数按照从高到低排序。小哼的班上只有5个同学，这5个同...

编程算法：求1+2+...+n（构造函数） 代码（C++）

2016年07月27日 35 阅读

编程算法：求1+2+...+n（构造函数） 代码（C++）2015-10-20题目: 求1+2+...+n, 要求不能使用乘除法forwhileifelseswitchcase等关键字及条件判断语句（A？B:C）.可以使用构造函数, 循环求解, 使用数组构造多个类, 使用类的静态变量存储数据.代码:/** main.cpp**Created on: 2014.7.12* *Author: spike*/#include <stdio.h>#in...

编程算法：求1+2+...+n（函数继承） 代码（C++）

2016年07月27日 33 阅读

编程算法：求1+2+...+n（函数继承） 代码（C++）2015-10-20题目: 求1+2+...+n, 要求不能使用乘除法forwhileifelseswitchcase等关键字及条件判断语句（A？B:C）.可以使用函数继承, 通过递归调用, 每次递归值减1, 使用求反运算（！）, 即非0为0, 0为1.代码:/** main.cpp**Created on: 2014.7.12* *Author: spike*/#include <stdio...

编程算法：求1+2+...+n（函数指针） 代码（C++）

2016年07月27日 32 阅读

编程算法：求1+2+...+n（函数指针） 代码（C++）2015-10-20 未知 题目: 求1+2+...+n, 要求不能使用乘除法forwhileifelseswitchcase等关键字及条件判断语句（A？B:C）.可以使用函数指针求解, 通过递归调用, 每次递归值减1, 使用求反运算（！）, 即非0为0, 0为1.代码:/** main.cpp**Created on: 2014.7.12* *Author: spike*/#include <...

编程算法：求1+2+...+n（模板类） 代码（C++）

2016年07月27日 35 阅读

编程算法：求1+2+...+n（模板类） 代码（C++）2015-10-20题目: 求1+2+...+n, 要求不能使用乘除法forwhileifelseswitchcase等关键字及条件判断语句（A？B:C）.可以使用模板类求解, 输入模板参数, 进行递归调用, 每次递归值减1, 至模板参数为1时, 显示调用结束模板类.代码:/** main.cpp**Created on: 2014.7.12* *Author: spike*/#include <...

Dijkstra最短路算法

2016年07月27日 33 阅读

Dijkstra最短路算法2015-10-22上周我们介绍了神奇的只有五行的Floyd最短路算法，它可以方便的求得任意两点的最短路径，这称为“多源最短路”。本周来来介绍指定一个点（源点）到其余各个顶点的最短路径，也叫做“单源最短路径”。例如求下图中的1号顶点到2、3、4、5、6号顶点的最短路径。与Floyd-Warshall算法一样这里仍然使用二维数组e来存储顶点之间边的关系，初始值如下。我们还需要用一个一维...

解密回文——栈

2016年07月27日 35 阅读

解密回文——栈2015-10-22上一节中我们学习了队列，它是一种先进先出的数据结构。还有一种是后进先出的数据结构它叫做栈。栈限定只能在一端进行插入和删除操作。比如说有一个小桶，小桶的直径只能放一个小球，我们现在向小桶内依次放入2号、1号、3号小球。假如你现在需要拿出2号小球，那就必须先将3号小球拿出，再拿出1号小球，最后才能将2号小球拿出来。在刚才取小球的过程中，我们最先放进去的小球最后才能拿出来，而最后放进去的小球却可以最先拿出来。这就是后进先出，也可...

冒泡、二分法插入及快速排序算法

2016年07月27日 34 阅读

冒泡、二分法插入及快速排序算法2015-10-221.冒泡排序算法过程：1.遍历整个数组，每两两相邻的元素进行比较，如$a[$i]>$a[$i+1]则互换位置，每次比较消除一个逆序。2.每一次循环后，下次再需要循环的次数减少1。<？php// 冒泡排序$arr = createarr（20）;printarr（$arr）;popsort（$arr）;printarr（$arr）;function createarr（$num=10）{$arr ...

只有五行的Floyd最短路算法

2016年07月27日 35 阅读

只有五行的Floyd最短路算法2015-10-22暑假，小哼准备去一些城市旅游。有些城市之间有公路，有些城市之间则没有，如下图。为了节省经费以及方便计划旅程，小哼希望在出发之前知道任意两个城市之前的最短路程。上图中有4个城市8条公路，公路上的数字表示这条公路的长短。请注意这些公路是单向的。我们现在需要求任意两个城市之间的最短路程，也就是求任意两个点之间的最短路径。这个问题这也被称为“多源最短路径”问题。现在需要一个数据结构来存储图的...