- 博客(43)
- 收藏
- 关注
RSS订阅
原创 哈夫曼树的创建
哈夫曼树每次选取两个最小值，然后将两个最小值之和再存入到权值中，如果用数组每次都排序插入在排序，效率不高，本文采用最小堆的形式，堆中的元素为带权值的哈夫曼结点。代码如下：/************************************************************************** 文件名：5.2.1.cpp** 文件描述：哈夫曼树** ...
2018-08-14 10:26:24
3017
转载 14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串""。示例1:输入: ["flower","flow","flight"]输出: "fl"示例2:输入: ["dog","racecar","car"]输出: ""解释: 输入不存在公共前缀。说明:所有输入只包含小写字母a-z。思路：这题思路不难，但在具体的实现中有...
2019-03-19 09:48:18
192
原创 13. 罗马数字转整数
罗马数字包含以下七种字符:I，V，X，L，C，D和M。字符 数值I 1V 5X 10L 50C 100D 500M 1000例如， 罗马数字 2 写做II，即为两个并列的 1...
2019-03-04 15:46:16
180
原创 9. 回文数
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。示例 1:输入: 121输出: true示例 2:输入: -121输出: false解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。示例 3:输入: 10输出: false解释: 从右向左读, 为 01 。因此它不是一个回文...
2019-01-14 10:54:16
230
原创 7. 整数反转
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。示例 1:输入: 123输出: 321 示例 2:输入: -123输出: -321示例 3:输入: 120输出: 21注意:假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。...
2019-01-09 14:47:56
150
原创 1. 两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。示例:给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]三种解法：...
2019-01-04 17:19:10
163
原创 部分背包问题（贪心算法）
部分背包问题是基于贪心法的基本思想。何谓贪心法，只要你够贪心，就能领略贪心算法之精髓。部分背包问题和0/1背包问题的区别就是：部分背包问题中的单个物品，可以取一部分装入背包。而0/1背包问题则是要么全部拿走，要么一无所有（这里引用了LOL卡牌大师的台词）。 那么作为一个so greed的你，肯定应该知道按照什么顺序拿物品的把。没错，看着值钱的先抢！ 这里所说的值钱，指的是单位重量所产生的价...
2018-11-09 20:59:23
5262
原创 7-11 关键活动
7-11 关键活动 （30 分）假定一个工程项目由一组子任务构成，子任务之间有的可以并行执行，有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程，各门课程可以看成是子任务。有些课程可以同时开设，比如英语和C程序设计，它们没有必须先修哪门的约束；有些课程则不可...
2018-10-09 19:10:18
294
原创 7-10 公路村村通
7-10 公路村村通 （30 分）现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。输入格式:输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。输出格式:...
2018-10-05 15:47:46
902
1
原创 7-9 旅游规划
7-9 旅游规划 （25 分）有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。输入格式:输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是...
2018-10-04 09:40:26
497
原创 7-8 哈利·波特的考试
7-8 哈利·波特的考试 （25 分）哈利·波特要考试了，他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是haha，将老鼠变成鱼的魔咒是hehe等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念，例如ahah可以将老鼠变成猫。另外，如果想把猫变成鱼，可以通过念一个直接魔咒lalala，也可以将猫变老鼠、老鼠变鱼的魔咒连起来念：hahahehe。现...
2018-09-30 15:48:24
360
原创 7-7 六度空间
7-7 六度空间 （30 分）“六度空间”理论又称作“六度分隔（Six Degrees of Separation）”理论。这个理论可以通俗地阐述为：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过五个人你就能够认识任何一个陌生人。”如图1所示。图1 六度空间示意图“六度空间”理论虽然得到广泛的认同，并且正在得到越来越多的应用。但是数十年来，试图验证这个理论始终是许...
2018-09-30 09:16:33
482
原创 7-6 列出连通集
7-6 列出连通集 （25 分）给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。输入格式:输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。输出格式:按照"{...
2018-09-29 10:49:47
471
原创 排序算法之基数排序
基数排序(Radix Sort)是桶排序的扩展，它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。具体做法是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。对于一般的基数排序有通常有两种排序算法：主位优先算法（Most Significant Digit...
2018-09-26 15:42:47
140
原创 排序之桶排序
如果已知N个关键字的取值范围在0到M-1之间，而M比N小的多，则桶排序则为关键字的每个可能取值建立一个桶，即建立M个桶；在扫描N个关键字时，将每个关键字放入到相应的桶中，然后按照桶的顺序收集一遍就自然有序了。所以桶排序的效率比一般的排序算法效率高-------当然需要的额外条件是已知关键字的范围，并且关键字在此范围内是可列的，个数还不能超过内存空间所能承受的程度。代码如下：/******...
2018-09-26 15:32:36
127
原创 拓扑排序
概述：在现实生活中，某些事物可以用有向无环图（Directed Acyclic Graph，DAG）表述。这种有向无环图通常也称作“流程图”，比如，施工流程图、生产流程图、图中每个顶点可以代表一个具体的工序，每条有向边则反映了两个工序的前后次序。拓扑序：如果图中从V到W有一条有向路径，则V一定排在W之前。满足此条件的顶点序列称为一个拓扑序。获得一个拓扑序的过程就是拓扑排序AOV如果...
2018-09-17 08:35:35
412
4
原创 最小生成树之克鲁斯卡尔算法（Kruskal）
prim算法中的最小生成树是，采用的是从一个顶点开始，让一棵小树逐渐长成最小生成树，而kruskal算法，采用的是每次选择权值最小的一条边作为生成树，采用将每一棵生成树合并一棵最小生成树方法。也就是将树合成为森林。有一点需要注意：就是将新边加入到最小生成树中时，要判断是否构成回路，如果构成回路的话，则不能加入。那么问题来了，如何判断构成回路呢？一种是采用深度优先搜索来判断两个顶点是否连通，另一种是...
2018-09-14 17:32:49
416
原创 最小生成树之Prim算法-使用邻接矩阵实现
最小生成树的算法，网上有详细的介绍，这里简单谈一下关键的几个步骤：1：prim算法和单源最短路径中的迪杰斯特拉算法很相识，也在其中借鉴了部分算法。总的来说将图上的顶点分成两部分。一部分 为树顶点（已被选入生成树的顶点）和非树顶点（还未被选入生成树的顶点）。首先选择任意一个顶点加入生成树，然后从剩 下的非树顶点中选择一个距离生成树最近的顶点加入到生成树中，并且更新其它非...
2018-09-13 15:28:20
1992
原创 弗洛伊德（Floyd）算法（多源最短路径）
弗洛伊德算法比较适合稠密图，形式上比较优雅，核心代码只有五行。for (k = 1; k <= g.v; k++) for (i = 1; i <= g.v; i++) for(j = 1; j <= g.v; j++) if (g.matrix[i][j] > g.matrix[i][k] + ...
2018-09-08 16:06:09
456
原创 单源最短路径-迪杰斯塔拉（Dijkstra）算法的实现
/************************************************************************** 文件名：7.1.1.cpp** 文件描述：Dijkstra算法的实现（好久没写代码了，看来我还是适合codeing不适合paper）** 创建人： fdk* 时 间： 2018-09-03** 版本号：1.0** 修...
2018-09-04 19:57:45
242
原创 图的存储结构—-邻接矩阵和邻接表的代码实现
图的存储结构一般有两种：一、邻接矩阵：用矩阵表示图中各顶点之间的邻接关系和权值。（一般把带权值的图叫做网）邻接矩阵适合稠密图的存储。二、邻接表：是图的一种顺序存储于链式存储结合的存储方法。领接表表示法类似于树的孩子链表表示法。就是对于图G中的每个顶点Vi，将所有的邻接于Vi的顶点Vj链接成一个单链表，这个单链表就称做顶点Vi的邻接表，再将所有点的邻接表表头放到一个数组中，就构成了图的邻接表...
2018-08-20 10:25:02
1894
原创 7-5 堆中的路径
7-5 堆中的路径（25 分）将一系列给定数字插入一个初始为空的小顶堆H[]。随后对任意给定的下标i，打印从H[i]到根结点的路径。输入格式:每组测试第1行包含2个正整数N和M(≤1000)，分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间[-10000, 10000]内的N个要被插入一个初始为空的小顶堆的整数。最后一行给出M个下标。输出格式:对输入中给出的每个下标...
2018-08-17 15:08:45
2465
1
原创 7-4 是否同一棵二叉搜索树
7-4 是否同一棵二叉搜索树（25 分）给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。输入格式:输入包含若干组测试数据。每组数据的第1行给出两个正整数N (≤10...
2018-08-16 16:52:57
847
原创 7-1 Maximum Subsequence Sum
7-1 Maximum Subsequence Sum（25 分）Given a sequence of K integers { N1, N2, ..., NK }. A continuous subsequence is defined to be { Ni, Ni+1, ..., Nj } where 1≤i≤j≤K. The Maximum Subs...
2018-08-15 16:18:27
207
原创 7-3 树的同构
7-3 树的同构（25 分）给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互换后，就得到另外一棵树。而图2就不是同构的。 图1图2现给定两棵树，请你判断它们是否是同构的。 输入格式:输入给出2棵二叉树树的信息。对于每棵树，首先...
2018-08-15 16:15:36
801
原创 7-4 List Leaves
7-4 List Leaves（25 分）Given a tree, you are supposed to list all the leaves in the order of top down, and left to right.Input Specification:Each input file contains one test case. For each case, ...
2018-08-15 16:12:52
236
原创 堆的建立、插入、删除以及堆排序
堆的结构为完全二叉树，因此适合用数组来存储，本文建立的是最小堆代码如下：/************************************************************************** 文件名：5.1.1.cpp** 文件描述：堆的建立、插入、删除以及堆排序** 创建人： fdk* 时 间： 2018-08-11** 版本号...
2018-08-14 10:22:16
523
原创 平衡二叉树（AVL树）的插入、删除
AVL树主要难点在于，插入和删除，因为插入和删除后需要对树进行调整使其仍满足AVL树的要求，具体的调整过程网上都有就不细讲了，主要是删除部分很少有书进行讲解，可以参考一下：http://www.cppblog.com/cxiaojia/archive/2012/08/20/187776.html我的删除部分代码：可以看看为什么在删除一个结点后采用这种调整方式，博主也是看了好久才明白，一定要...
2018-08-11 10:33:27
205
原创 二叉排序树（搜索树）的建立、插入、查找、删除
本程序的主要难点在于，二叉排序树的删除。删除的结点有三种情况：1.要删除的是叶结点。这种情况最简单，可以直接删除，然后再修改其父结点的指针置空即可。2.如果要删除的结点只有一个孩子结点（该结点不一定是叶结点，可以是子树的根），删除之前需要改变父结点的指针，指向要删除结点的孩子结点。3.如果要删除的结点有左右两棵子树，有两种选择：一、取其右子树中的最小元素。 二、取其左子树中的最大元素。...
2018-08-08 21:04:11
432
原创 二叉树的建立、插入、删除、遍历（前中后的递归及非递归遍历和层次遍历）、求树高及叶子结点等
主要难点为树的建立和，非递归遍历，尤其是后序的非递归遍历。1.非递归遍历的主要思路：从根结点开始，沿左子树深入下去，当深入到最左端时，无法深入下去，则返回刚才深入的时遇到的结点，并遍历该结点的右子树，进行如此的深入和返回，直到最后根结点的右子树返回到跟结点为止。2.这一过程中，返回结点的顺序和进入结点的顺序相反，即先进入后返回，正好符合堆栈因此采用堆栈这一数据结构。在沿左子树进行深入时...
2018-08-07 21:00:55
441
原创 二分查找算法
这个在之前的九大算法中已经写过了，这次重新又写了一遍是为了进一步加深理解并学习--树这一存储结构/************************************************************************** 文件名：3.1.1.cpp** 文件描述：二分查找算法** 创建人： fdk* 时 间： 2018-08-02** 版本...
2018-08-02 20:06:53
224
原创 7-2 一元多项式的乘法与加法运算
设计函数分别求两个一元多项式的乘积与和。输入格式:输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。输出格式:输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。输入样例:4 3 4 -5 2...
2018-08-02 16:05:56
206
原创 7-1 最大子列和问题
7-1 最大子列和问题（20 分）给定K个整数组成的序列{ N1, N2, ..., NK }，“连续子列”被定义为{ Ni, Ni+1, ..., Nj }，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要...
2018-08-02 16:04:14
155
原创 单链表来实现多项式的加法和乘法运算
/************************************************************************** 文件名：2.2.6.cpp** 文件描述：实现多项式的加法及乘法运算** 创建人： fdk* 时 间： 2018-08-01** 版本号：1.0** 修改记录：链表的使用还不够熟练，不能自己独立完成需要多加练习*...
2018-08-01 20:15:38
940
原创 队列的链式存储实现（简单的入队和出队操作）
/************************************************************************** 文件名：2.2.5.cpp** 文件描述：队列的链式存储实现** 创建人： fdk* 时 间： 2018-07-31** 版本号：1.0** 修改记录：队列和堆栈一样也能采取链式存储，但队列的头fronts必须...
2018-08-01 13:55:18
2659
原创 循环队列的顺序存储实现（创建、插入、删除）
/************************************************************************** 文件名：2.2.4.cpp** 文件描述：循环队列的顺序存储实现（创建、插入、删除）** 创建人： fdk* 时 间： 2018-07-31** 版本号：1.0** 修改记录：******************...
2018-07-31 20:55:54
2430
原创 堆栈的链式存储实现（简单的入栈和出栈）
/************************************************************************** 文件名：2.2.3.cpp** 文件描述：堆栈的链式存储实现** 创建人： fdk* 时 间： 2018-07-31** 版本号：1.0** 修改记录：******************************...
2018-07-31 16:04:00
1709
原创 请用一个数组实现两个堆栈，要求最大地利用数组空间，使数组只要有空间入栈操作就可以成功
/************************************************************************** 文件名：2.2.2.cpp** 文件描述：请用一个数组实现两个堆栈，要求最大地利用数组空间，使数组只要有空间入栈操作就可以成功** 创建人： fdk* 时 间： 2018-07-30** 版本号：1.0** 修改记录...
2018-07-31 10:37:43
544
原创 栈的顺序存储实现-简单的进栈及出栈
/************************************************************************** 文件名：2.2.1.cpp** 文件描述：栈的顺序存储实现** 创建人： fdk* 时 间： 2018-07-30** 版本号：1.0** 修改记录：*******************************...
2018-07-30 20:37:10
903
原创 线性表（链表）的创建、查找、插入、删除
/************************************************************************** 文件名：2.1.2.cpp** 文件描述：线性表（链表）的查找、插入、删除** 创建人： fdk* 时 间： 2018-07-28** 版本号：1.0** 修改记录：头结点的作用：1、防止单链表是空的而设的.当链表...
2018-07-30 15:12:03
776
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人