- 博客(190)
- 资源 (6)
- 收藏
- 关注
RSS订阅原创 window下xshell 开启密钥认证 禁用服务器密码登录
由于大家比较朴实，将实验室服务器密码设置成了程序员都知道的。但最近有些实验室连续最近出现了非法入侵现象（由于服务器不能同校外，估计是校内小朋友干的,太伤心了)。只能采用开启密钥认证，禁用密码登录。相信大家RSA非对称加密的原理大家都了解，这里就不赘述了。这里主要是window下xshell设置方法：首先填入你需要连接服务器的基本信息。下一步：之后的对话框，点击下
2013-12-11 17:01:38
4083
1
原创 合并K个有序链表-堆的使用
有k个有序的链表（按照结点的val值升序），请将它们全部合并为一个新的有序的链表。返回合并后链表的头结点。题目来源：http://www.itint5.com/oj/#21推荐指数：※※K个链表本来都是有序的，现在要将K个链表合并成一个。关键在于k个链表元素之间的比较。例如：k个链表的第一个元素比较之后，将最小的那个节点X放入新的链表当中。X=X->next; 现在就是要高效的
2013-11-05 20:25:38
1679
原创 最小生成树 prim算法
Prim算法的特点是集合A中的边总是形成单课树。prim算法的执行过程非常类似于寻找最短路径的Dijkstra算法。树从图中的任意一个顶点r开始，使用贪心策略，每次选择添加到树中的边（一个顶点在树的结合V中，一个顶点在A-V中）都到尽量小。算法：1.初始化各个顶点到树的距离。（一开始树只有根节点） for(i=0;i<n;i++){ closest[i]=m[root][i
2013-10-09 22:56:38
955
原创 RMQ (Range Minimum/Maximum Query)问题的ST（Sparse Table）解法
RMQ (Range Minimum/Maximum Query)问题，就是要求：数字序列区间最值。如果直接遍历查询，复杂度为O(n).对于比较大的数据和需要多次查询的场景，都是很不理想的。常见的方法有线段树和Sparse Tabel两种方法。复杂度：两种算法都需要预处理，预处理的复杂度为：线段树(segment tree) O(n)ST（实质是动态规划） O(nlog
2013-10-08 00:05:24
1067
原创 题目1509：树中两个结点的最低公共祖先-九度
题目描述：给定一棵树，同时给出树中的两个结点，求它们的最低公共祖先。输入：输入可能包含多个测试样例。对于每个测试案例，输入的第一行为一个数n(0其中每个测试样例包括两行，第一行为一个二叉树的先序遍历序列，其中左右子树若为空则用0代替，其中二叉树的结点个数node_num第二行为树中的两个结点的值m1与m2(0输出：对应每个测试案例，输出给定的树中两个结点的最低公
2013-10-07 21:06:35
1065
原创 题目1355：扑克牌顺子-九度
题目描述：LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,
2013-10-04 20:46:38
1209
原创 题目1360：乐透之猜数游戏-九度
题目描述：六一儿童节到了,YZ买了很多丰厚的礼品,准备奖励给JOBDU里辛劳的员工。为了增添一点趣味性,他还准备了一些不同类型的骰子,打算以掷骰子猜数字的方式发放奖品。例如,有的骰子有6个点数(点数分别为1~6),有的骰子有7个(点数分别为1~7),还有一些是8个点数(点数分别为1~8) 。他每次从中拿出n个同一类型的骰子(假设它们都是拥有m个点数并且出现概率相同)投掷,然后让员工在纸上按优先
2013-10-04 00:11:40
1643
原创 Problem B. Rational Number Tree -Calkin–Wilf tree 数节点编号 基本数据类型范围
ProblemConsider an infinite complete binary tree where the root node is 1/1 and left and right childs of node p/q are p/(p+q) and (p+q)/q, respectively. This tree looks like: 1/1 _____
2013-09-23 21:06:07
1712
原创 Problem A. Read Phone Number -模拟读电话号码
ProblemDo you know how to read the phone numbers in English? Now let me tell you.For example, In China, the phone numbers are 11 digits, like: 15012233444. Someone divides the numbers into 3-4-4 f
2013-09-23 13:45:26
1600
原创 Problem C. Sorting- 分组后 快速排序
ProblemAlex and Bob are brothers and they both enjoy reading very much. They have widely different tastes on books so they keep their own books separately. However, their father thinks it is good to
2013-09-23 13:41:03
995
原创 字符串匹配 KMP算法 模板
/*kmp相关ojhttp://www.cnblogs.com/wuyiqi/archive/2012/01/06/2315188.html*/#include#include#include#includeusing namespace std;const int T=1000009;const int W=10009;/*在jump数组中，发现str[k+1]!=str[i]时
2013-09-22 22:03:25
2001
原创 题目1534：数组中第K小的数字 数值逼近的方法
题目描述：给定两个整型数组A和B。我们将A和B中的元素两两相加可以得到数组C。譬如A为[1,2]，B为[3,4].那么由A和B中的元素两两相加得到的数组C为[4,5,5,6]。现在给你数组A和B，求由A和B两两相加得到的数组C中，第K小的数字。输入：输入可能包含多个测试案例。对于每个测试案例，输入的第一行为三个整数m，n， k(1紧接着两行， 分
2013-09-20 20:59:52
1258
原创 题目1533：最长上升子序列-九度
题目描述：给定一个整型数组， 求这个数组的最长严格递增子序列的长度。 譬如序列1 2 2 4 3 的最长严格递增子序列为1，2，4或1，2，3.他们的长度为3。输入：输入可能包含多个测试案例。对于每个测试案例，输入的第一行为一个整数n(1输入的第二行包括n个整数，代表这个数组中的数字。整数均在int范围内。输出：对于每个测试案
2013-09-19 11:15:08
1293
原创 题目1361：翻转单词顺序-九度
题目描述：JOBDU最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？输入：每
2013-09-19 09:31:40
871
原创 求最长公共子序列Longest Common Subsequence LCS
最长公共子序列：一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。最长公共子序列与最长公共子串(要求连续)是不同的。复杂度：对于一般性的LCS问题（即任意数量的序列）是属于NP-hard。但当序列的数量确定时，问题可以使用动态规划（Dynamic Programming）在多项式时间解决。最长公共子序列是一个十分实用
2013-09-18 10:27:14
1138
原创 最长公共子串 Longest common subString
最长公共子串（ Longest Common subString），简化成两个串的情况，就是要求两个找出两个字符串A、B相同的子串中最长的一个，要求连续。这和最长公共子序列不同同，最长公共子序列可以不连续。算法：找两个字符串的最长公共子串，这个子串要求在原字符串中是连续的。其实这又是一个序贯决策问题，可以用动态规划来求解。我们采用一个二维矩阵来记录中间的结果。这个二维矩阵怎么构造呢？直接举
2013-09-16 09:58:41
1286
原创 点评团促销 -动态规划 背包
点评团准备展开一次大促销，促销中的每件商品，都有市场价和促销价，市场价和促销价的差就是用户省下的钱。由于本次活动的目标人群是点评团忠实用户，所以购买每件商品还需要一定量的金币，而金币就是根据用户的历史购买计算出来的。给定一个用户的资金预算和金币预算，计算如何在不超过预算的情况下能省下最多的钱。输入：首先三个整数，n: 促销商品的数量，m: 资金预算，k: 金币预算其中0接下来有n行
2013-09-15 13:10:02
1360
原创 变成回文字符串所需要的次数-动态规划
描述所谓回文字符串，就是一个字符串，从左到右读和从右到左读是完全一样的，比如"aba"。当然，我们给你的问题不会再简单到判断一个字符串是不是回文字符串。现在要求你，给你一个字符串，可在任意位置添加字符，最少再添加几个字符，可以使这个字符串成为回文字符串。输入第一行给出整数N（0接下来的N行，每行一个字符串，每个字符串长度不超过1000.输出每行输出所需添加的最少字符
2013-09-15 11:20:42
3601
原创 Bad Horse -google-判断是否是二分图
ProblemAs the leader of the Evil League of Evil, Bad Horse has a lot of problems to deal with. Most recently, there have been far too many arguments and far too much backstabbing in the League, so
2013-09-14 18:48:52
2132
原创 Moist-google
ProblemMoist has a hobby -- collecting figure skating trading cards. His card collection has been growing, and it is now too large to keep in one disorganized pile. Moist needs to sort the cards in
2013-09-14 13:55:03
1362
原创 Captain Hammer-google
ProblemThe Hamjet is a true marvel of aircraft engineering. It is a jet airplane with a single engine so powerful that it burns all of its fuel instantly during takeoff. The Hamjet doesn't have any
2013-09-14 13:52:38
1418
原创 打印括号的所有组合
这是一道在线的趣味题：打印括号实现一个算法，打印所有可能的N对尖括号组合，用a代替“”。输入N，输出可能的括号组合：例如输入：2输出：aabbabab（最后一行行尾换行符）输入是从标准输入读取，输出打印到标准输出之中。推荐指数：※※来源：这一道题，可以抽象层一个排列组合的问题，在排列过程中注意使用剩余的右括号一定要多余左括号的条件进行剪枝。#
2013-09-13 22:02:55
1910
原创 题目1354：和为S的连续正数序列-九度
题目描述：小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!输入：输入有多
2013-09-13 11:28:47
807
原创 二分图的最大权匹配
二分图的带权匹配就是求出一个匹配集合，使得集合中边的权值之和最大（最小权匹配可以转化成最大权匹配，只要对权值取反）。注意：最大权匹配必须是在保证该匹配是完备匹配的基础上权值和最大。而完备匹配是指一个匹配它包含二分图两个点集中某一个的全集（当然也可以包括这两个全集，也就是完备匹配）。KM算法是通过给每个顶点一个标号（我们有时称之为顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。我们令二
2013-09-12 09:35:34
2179
原创 HDU1068-Girls and Boys
Problem Descriptionthe second year of the university somebody started a study on the romantic relations between the students. The relation “romantically involved” is defined between one girl and o
2013-09-11 15:13:10
1693
原创 poj3020-Antenna Placement
DescriptionThe Global Aerial Research Centre has been allotted the task of building the fifth generation of mobile phone nets in Sweden. The most striking reason why they got the job, is their dis
2013-09-11 11:06:13
1084
原创 poj 3041-Asteroids
DescriptionBessie wants to navigate her spaceship through a dangerous asteroid field in the shape of an N x N grid (1 Fortunately, Bessie has a powerful weapon that can vaporize all the astero
2013-09-10 19:15:05
1116
原创 HDU1150-Machine Schedule
Problem DescriptionAs we all know, machine scheduling is a very classical problem in computer science and has been studied for a very long history. Scheduling problems differ widely in the nature
2013-09-10 16:40:32
1045
原创 匈牙利算法-最大二分匹配
匈牙利算法，是求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。增广路也称增广轨或交错轨： 若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。（M为一个匹配）由增广路的定义可以推出下述三个结论：1.P的路
2013-09-10 14:57:37
1941
原创 数组A中，除了某一个数字x之外，其他数字都出现了三次，而x出现了一次。请给出最快的方法，找到x。
数组A中，除了某一个数字x之外，其他数字都出现了三次，而x出现了一次。请给出最快的方法，找到x。类似的：数组A中，除了某一个数字x之外，其他数字都出现了三次，而x出现了两次。请给出最快的方法，找到x。这道题是：数组A中，除了某一个数字x之外，其他数字都出现了两次，而x出现了一次。请给出最快的方法，找到x。的变种。思路：http://blog.csdn.net/zhu_liangwei/
2013-09-07 19:57:10
2637
3
原创 题目1351：数组中只出现一次的数字-九度
题目描述：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。输入：每个测试案例包括两行：第一行包含一个整数n，表示数组大小。2第二行包含n个整数，表示数组元素，元素均为int。输出：对应每个测试案例，输出数组中只出现一次的两个数。输出的数字从小到大的顺序。样例输入：82 4 3 6 3 2 5 5
2013-09-04 16:55:39
1402
原创 题目1350：二叉树的深度-九度
题目描述：输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。输入：第一行输入有n，n表示结点数，结点号从1到n。根结点为1。 n 接下来有n行，每行有两个个整型a和b，表示第i个节点的左右孩子孩子。a为左孩子，b为右孩子。当a为-1时，没有左孩子。当b为-1时，没有右孩子。输出：输出一个整型，表示
2013-09-04 15:25:09
1162
原创 题目1352：和为S的两个数字-九度
题目描述：输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。输入：每个测试案例包括两行：第一行包含一个整数n和k，n表示数组中的元素个数，k表示两数之和。其中1 第二行包含n个整数，每个数组均为int类型。输出：对应每个测试案例，输出两个数，小的先输出。如果找不到，则输出“-1 -1”样例
2013-09-04 11:08:05
1135
原创 题目1349：数字在排序数组中出现的次数-九度
题目描述：统计一个数字在排序数组中出现的次数。输入：每个测试案例包括两行：第一行有1个整数n，表示数组的大小。1第二行有n个整数，表示数组元素，每个元素均为int。第三行有1个整数m，表示接下来有m次查询。1下面有m行，每行有一个整数k，表示要查询的数。输出：对应每个测试案例，有m行输出，每行1整数，表示数组中该数字出现的次数。样例输入：
2013-09-03 23:06:54
753
原创 题目1348：数组中的逆序对-九度
题目描述：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。输入：每个测试案例包括两行：第一行包含一个整数n，表示数组中的元素个数。其中1 第二行包含n个整数，每个数组均为int类型。输出：对应每个测试案例，输出一个整数，表示数组中的逆序对的总数。样例输入：47 5 6 4
2013-09-03 20:16:22
776
原创 题目1214：丑数-九度
题目描述：把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。输入：输入包括一个整数N(1输出：可能有多组测试数据，对于每组数据，输出第N个丑数。样例输入：3样例输出：3推荐指数：※※来源：http://ac.jobdu.c
2013-09-02 20:14:45
733
原创 题目1504：把数组排成最小的数-PAT
题目描述：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。输入：输入可能包含多个测试样例。对于每个测试案例，输入的第一行为一个整数m (1输入的第二行包括m个正整数，其中每个正整数不超过10000000。输出：对应每个测试案例，输出m个数字
2013-09-01 21:45:00
1027
原创 1062. Talent and Virtue (25)-PAT
About 900 years ago, a Chinese philosopher Sima Guang wrote a history book in which he talked about people's talent and virtue. According to his theory, a man being outstanding in both talent and virt
2013-08-30 22:59:26
1194
原创 1061. Dating (20)-PAT
Sherlock Holmes received a note with some strange strings: "Let's date! 3485djDkxh4hhGE 2984akDfkkkkggEdsb s&hgsfdk d&Hyscvnm". It took him only a minute to figure out that those strange strings are a
2013-08-30 22:39:41
1210
1
openstack 报告
2013-09-05
cirros-0.3.0-x86_64-uec.tar.gz
2012-08-20
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人