- 博客(113)
- 收藏
- 关注
RSS订阅原创 POJ3259----Wormholes
DescriptionWhile exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a ...
2018-05-14 17:02:07
162
原创 bellman-ford算法
bellman-ford算法是用于解决单源最短路径的算法，与Dijkstra不同的是，它可解决存在负权边的的情况。同时，它也可以检测是否存在存在负权值环。其基本思路如下：建立一个距离数组dis[]，将源点设为0，其余点的距离初始化为无穷大。将下列操作循环最多n-1次：对于每条边,start->end,if(dis[end] > dis[start] + weight) ...
2018-05-14 15:22:00
172
原创 Floyd算法
Floyd算法用于求图中任意两点的最短距离。Floyd算法的内涵是遍历N个结点，对于第k个结点，将k结点作为中间结点，更新其余结点的信息：即其余结点（i）能否通过结点k来缩短与其他结点(j)的距离。Floyd的代码写起来非常简洁，但一直有一个小问题会困惑，假设i-j的最短距离中，以k结点更新最短距离时，如果此时i-k和k-j不是最短距离，如何保证i-j是最短距离呢？假设i-j最短距离中，编号最大的...
2018-05-12 10:23:34
282
原创 图的遍历
这里写的是无向图的遍历方法，BFS与DFS。BFS主要是借助了一个队列q，开始时将根结点压入队列，并标记为已访问，当队列不为空时做以下循环：1.输出队首结点2.取队列队首元素，遍历n个结点，如果队首结点与该结点有边且该结点为被访问，将该结点压入队列中，并标记该结点。DFS则是利用递归思想，需要在函数体外建立一个visit[n+1]数字。对于结点i，访问结点i，并标记结点i已访问遍历n个结点，如果结...
2018-05-07 22:38:01
452
原创 二叉树遍历
#include <iostream>#include <queue>using namespace std;class Node{public: int data; Node *left; Node *right; Node(int aData) { this->data = aData; ...
2018-05-06 14:52:53
134
原创 1004. Counting Leaves (30)
A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.InputEach input file contains one test case. Each case starts with a line contai...
2018-05-06 13:34:44
117
原创 Dijkstra 算法的几种变形
Dijkstra用来就最短路径，在保证最短路径的条件下，可新增一些其他标尺。1.每个结点拥有点权，在最短路劲的条件下求点权和最大的路劲。2.每条边新增边权cost，在最短路径的条件下求cost和最小的路径。3.求最短路径的条数。问题1，3可参考我的另一篇文章：https://blog.csdn.net/qq_39304201/article/details/80176476关键是建立num数组与m...
2018-05-04 20:48:07
1007
1
原创 1003. Emergency (25)
As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the l...
2018-05-03 11:01:14
199
原创 最简分数
题目描述给出n个正整数，任取两个数分别作为分子和分母组成最简真分数，编程求共有几个这样的组合。输入描述:每组包含n（n<=600）和n个不同的整数，整数大于1且小于等于1000。输出描述:每行输出最简真分数组合的个数。示例1输入73 5 7 9 11 13 15输出17 此题在理解题目时就走了很多弯路，一开始我以为是要求一组数中，任取两个组成分数，不同的分数值的个数时多少。后来看了别人的...
2018-04-28 16:39:27
2378
原创 Prim算法 与 dijkstra算法
有时总将两者搞混，两者都是基于贪心策略，且都是将图中顶点划分为两部分，每次取最小值。在这里对两者的算法做一个区分。Prim算法是解决图的 最小生成树 问题，在每次循环中，选取一个点在s中，另一个点在V-s中，且两点权值最小，直到V-s为空。Dijkstra算法是解决图的 最短路径 问题，即从某一点到其余各点的最短路径。在每次循环中选取V-s中的点，且其到起点的距离最短，然后用此更新其余结点的距离，...
2018-04-26 14:39:12
448
原创 I wanna go home
题目描述 The country is facing a terrible civil war----cities in the country are divided into two parts supporting different leaders. As a merchant, Mr. M does not pay attention to politics but he actu...
2018-04-26 14:04:15
237
原创 C语言里遇到的一点问题
用纯c写一个字符串反转时发现了一个bug，用下面的程序测试下：#include <stdio.h>#include <stdlib.h>#include <string.h>int main(){ int i; char s[100]={0}; scanf("%s",s); printf("strlen(s)/2-1 等于...
2018-04-23 21:11:00
288
原创 单链表实现多项式相加
首先用两个单链表储存两个多项式，要求输入的时候按指数降序输入。新建一个单链表res；接着从两个单链表的头部开始比较；如果指数不相同，将指数较大者接在res后面，同时res链表与较大者链表的游标向后移动，并且令res游标（此时指向刚刚接上的结点）的next域为空。这个过成相当于从原单链表中直接夺取了一个结点。如果指数相同，分两种情况。1.相加后系数为0.直接令两个原多项式的游标向后移动一格，其余什么...
2018-04-21 17:51:50
1106
原创 1002. A+B for Polynomials (25)
This time, you are supposed to find A+B where A and B are two polynomials.InputEach input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomia...
2018-04-21 16:54:36
91
原创 整数拆分
题目描述一个整数总可以拆分为2的幂的和，例如： 7=1+2+4 7=1+2+2+2 7=1+1+1+4 7=1+1+1+2+2 7=1+1+1+1+1+2 7=1+1+1+1+1+1+1 总共有六种不同的拆分方式。 再比如：4可以拆分成：4 = 4，4 = 1 + 1 + 1 + 1，4 = 2 + 2，4=1+1+2。 用f(n)表示n的不同拆分的种数，例如f(7)=6. 要求编写程序，读入n(...
2018-04-21 15:02:59
192
原创 质因数个数
题目描述求正整数N(N>1)的质因数的个数。 相同的质因数需要重复计算。如120=2*2*2*3*5，共有5个质因数。输入描述:可能有多组测试数据，每组测试数据的输入是一个正整数N，(1<N<10^9)。输出描述:对于每组数据，输出N的质因数的个数。示例1输入120输出5首先对于一个数n，可能因数只有可能是2~sqrt(n),所以考虑的数只在这个范围里。其次，在如果i是n的质因...
2018-04-20 22:24:57
723
原创 一些小积累
一些不利用STL库的方法：（持续更新）1.字符串反转#include <iostream>#include <string>using namespace std;int main(){ string a; int i; int low,high; cin>>a>>low>>high; f...
2018-04-19 21:11:52
79
原创 快速排序
快速排序思想如下：将一串序列中某一项作为基础pivot，将小于pivot的元素移到pivot的左侧，将大于pivot的元素移到右则，这样就得到了以pivot的基准的两串子序列，对子序列也做如此排序。这里也是用到了分治的策略，先分解再合并。快速排序分解是难点。以位置low的元素为基准，设置两个游标i=low,j=high。先从右往左扫描，遇到小于pivot的元素，则p[i],p[j]交换.i++。此...
2018-04-19 17:08:27
121
原创 大数乘法
解决长位数相乘的问题。解决方法是模拟手工计算乘法，即数列式相乘。在计算时，先不处理进位，将结果储存在一个数组中，待全部计算完成后，做一次进位处理。基本思想如下： 1 2 3 * 4 5 6 ------------- ...
2018-04-19 15:22:05
137
原创 进制转换
题目描述将一个长度最多为30位数字的十进制非负整数转换为二进制数输出。输入描述:多组数据，每行为一个长度不超过30位的十进制非负整数。（注意是10进制数字的个数可能有30个，而非30bits的整数）输出描述:每行输出对应的二进制数。示例1输入0138输出01111000此题考的就是一个大数除法。思路是用一个字符串来储存大数，从第一位开始除以2.得到的结果为加进一个新的字符串，余数乘...
2018-04-19 10:37:59
160
原创 归并排序
归并排序是一种分治策略。将一串序列从中间分开，分为low-mid,mid+1-high两部分子序列。这是分解。将子序列排序，并把排序后子序列重新复制给原数组。这是合并。对子序列不断递归调用，直到子序列个数为1。数量为1不再排序，直接将该数赋值给原数组。例如一个序列 n=101 3 9 0 5 8 4 2 7 6分解过程：1. 1-3-9-0-5 , 8-4-2-7-6 ...
2018-04-18 22:57:58
89
原创 阶乘
输入n， 求y1=1!+3!+...m!(m是小于等于n的最大奇数） y2=2!+4!+...p!(p是小于等于n的最大偶数)。输入描述:每组输入包括1个整数：n输出描述:可能有多组测试数据，对于每组数据，输出题目要求的y1和y2示例1输入4输出7 26求阶乘相加的过程用到了dp的思想，n!的阶乘等于(n-1)! *n，每个子问题记录结果即可求后面的阶乘。该问题中，y1是奇数阶乘的和，y2是偶...
2018-04-18 15:33:35
467
原创 找位置
题目描述对给定的一个字符串，找出有重复的字符，并给出其位置，如：abcaaAB12ab12 输出：a，1；a，4；a，5；a，10，b，2；b，11，1，8；1，12， 2，9；2，13。输入描述:输入包括一个由字母和数字组成的字符串，其长度不超过100。输出描述:可能有多组测试数据，对于每组数据，按照样例输出的格式将字符出现的位置标出。1、下标从0开始。2、相同的字母在一行表示出其出现过...
2018-04-18 15:26:34
141
原创 N阶楼梯上楼问题
题目描述N阶楼梯上楼问题：一次可以走两阶或一阶，问有多少种上楼方式。（要求采用非递归）输入描述:输入包括一个整数N,(1<=N<90)。输出描述:可能有多组测试数据，对于每组数据，输出当楼梯阶数是N时的上楼方式个数。示例1输入4输出5此题考查的是斐波那契数列。对于n阶的楼梯，设其上楼方法有f(n)种方法。上到n阶，只能从n-1阶上一阶，或从n-2阶上两阶，除此之外再无其他方法。所以...
2018-04-17 15:37:23
594
原创 A+B
此题难度在于两数的正负未知，如果符号相同，利用栈就可以实现相加。关键在于两长短，符号都未知，如果一正一负，利用栈做减法时先要判断两者绝对值大小，再判断最后结果的正负，略微有些复杂。对于类似与A+B的题，如果数相加后的的范围未超过了long long（1开头的19位数），直接将改数转换为long long 后相加减。如果超过了long long ，就需要按位自己设计加减。在将字符串转为整型的时候，用...
2018-04-16 19:26:04
154
原创 遍历链表
题目描述建立一个升序链表并遍历输出。输入描述:输入的每个案例中第一行包括1个整数：n(1<=n<=1000)，接下来的一行包括n个整数。输出描述:可能有多组测试数据，对于每组数据，将n个整数建立升序链表，之后遍历链表并输出。示例1输入43 5 7 9输出3 5 7 9这题可以简单的记录n个数，sort一下输出即可。这里写了一个按升序建立链表的过程，主要思想是通过两个指针p，q，p...
2018-04-15 18:27:02
2098
原创 奇偶校验
题目描述输入一个字符串，然后对每个字符进行奇校验，最后输出校验后的二进制数(如'3’，输出：10110011)。输入描述:输入包括一个字符串，字符串长度不超过100。输出描述:可能有多组测试数据，对于每组数据，对于字符串中的每一个字符，输出按题目进行奇偶校验后的数，每个字符校验的结果占一行。示例1输入33a输出101100111011001101100001这个题主要是学习了bitset...
2018-04-15 14:10:52
675
原创 二叉树遍历
题目描述二叉树的前序、中序、后序遍历的定义： 前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树； 中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树； 后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。 给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。输入描述:两个字符串，其长度n均小于等于2...
2018-04-15 13:21:39
95
原创 Prim算法
Prim算法是用来求带权无向图中的最小生成树。我对其解释如下：1.对于带权无向图G=（V，E）。有一集合s，开始时从图中任选一点origin并入s中，origin即为起点。2.选取一条弧<j,k>,顶点j属于s中，顶点k属于V-s中，并且<j,k>的权值为可选的边中的最小的。3.将顶点k并入s中。4.重复2-3，直到s包含了所有顶点（或已经执行了n-1次）在算法中，主要是使...
2018-04-14 16:54:08
185
原创 哈夫曼树的构造
哈夫曼树是叶子节点带权路径最小的二叉树。其构造方法我个人理解如下：对于给定的n个结点，其权值为Ni，将n个结点并入集合S中，对于n个结点按权值大小从小到大排列，每次从集合中取出权值最小的两个结点，将他们作为一个新结点的左右子树，新结点的权值为两结点之和，将新结点并入S中，重复操作，直至S中只有一棵树。利用C++，优先队列实现哈夫曼树的构造，在这里用优先队列储存结构体指针，在实现从小到大排序时略麻烦...
2018-04-14 15:37:43
787
1
原创 贪心策略之Dijkstra算法
Dijkstra算法是解决有向带权图中最短路径的算法。我用自己的语言解释Dijkstra算法的过程：1.首先有一个有向带权图G=（V,E），V为顶点集合，E为边集合,用邻接矩阵map[n][n]来储存。 确定一个起始点origin，有一个辅助集合s，一开始将origin并入s中。 有一个辅助数组dist[n],dist[i]表示i距离origin的最短距离，初始化dist[i]=map...
2018-04-13 23:19:49
2726
原创 二叉排序树
题目描述输入一系列整数，建立二叉排序数，并进行前序，中序，后序遍历。输入描述:输入第一行包括一个整数n(1<=n<=100)。接下来的一行包括n个整数。输出描述:可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。每种遍历结果输出一行。每行最后一个数据之后有一个空格。输入中可能有重复元素，但是输出的二叉树遍历序列中重复元素...
2018-04-13 19:32:43
109
原创 对 复数集合 一题代码的讲解
#include <iostream>#include <string>#include <cmath>#include <algorithm>#include <queue>#include <stdio.h>using namespace std;class Complex{public: do...
2018-04-12 21:26:32
94
原创 复数集合
题目描述 一个复数（x+iy）集合，两种操作作用在该集合上： 1、Pop 表示读出集合中复数模值最大的那个复数，如集合为空 输出 empty ，不为空就输出最大的那个复数并且从集合中删除那个复数，再输出集合的大小SIZE； 2 Insert a+ib 指令（a，b表示实部和虚部），将a+ib加入到集合中 ，输出集合的大小SIZE； 最开始要读入一个int n，表...
2018-04-12 21:09:13
1530
原创 查找
题目描述 读入一组字符串（待操作的），再读入一个int n记录记下来有几条命令，总共有2中命令：1、翻转 从下标为i的字符开始到i+len-1之间的字符串倒序；2、替换 命中如果第一位为1，用命令的第四位开始到最后的字符串替换原读入的字符串下标 i 到 i+len-1的字符串。每次执行一条命令后新的字符串代替旧的字符串（即下一条命令在作用在得到的新字符串上）。 命令格式：第一位0...
2018-04-12 18:54:41
115
原创 整数，字符，字符串间的转换
#include <iostream>#include <string>#include <sstream>#include <cmath>using namespace std;int main(){ int i; int num1=123456; int num2=1; string str="12...
2018-04-11 21:19:02
380
原创 矩阵的幂
题目描述给定一个n*n的矩阵，求该矩阵的k次幂，即P^k。输入描述: 第一行：两个整数n（2<=n<=10）、k（1<=k<=5），两个数字之间用一个空格隔开，含义如上所示。接下来有n行，每行n个正整数，其中，第i行第j个整数表示矩阵中第i行第j列的矩阵元素Pij且（0<=Pij<=10）。另外，数据保证最后结果不会超过10^8。输出描述:对于每组测试数据，...
2018-04-11 20:44:11
3732
原创 哈夫曼树
题目描述哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。输入描述:输入有多组数据。每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。输出描述:输出权值。示例1输入5 1 2 2 5 9输出37分析：1.此题主要有两...
2018-04-11 17:23:57
1674
原创 管理系统的源码
基本思路如下：1.成员基类Person，学生类Students与教师类Teacher继承Person；2.操作基类OperationPage，添加、删除、修改、查询类 继承自OperationPage；3.主函数里初始化数据库信息，实例化LoginPage类，loginPage选择登录教师还是学生，相应进入到studentPage与teacherPage进行操作。main.cpp#include ...
2018-03-30 23:57:52
945
原创 连接数据库的程序：一个小型的管理系统
一、涉及到的知识点如下：1.连接数据库，利用SqlQuery与SqlTableModel对数据库进行操作。2.设置窗口背景图片，窗口标题，窗口Icon等。二、功能：1.连接SQL server 数据库，初始化Teacher表与Student表，并插入一位默认的Teacher；2.teacher与student在登录界面选择登录3.teacher管理界面可以 添加、修改、删除、查询 teacher与...
2018-03-30 23:47:38
585
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人