文章 61
评论 136
浏览 295664
ACM刷题之-POJ-2192(Zipper)

ACM刷题之-POJ-2192(Zipper)

Description Given three strings, you are to determine whether the third string can be formed by combining the characters in the first two strings. The first two strings can be mixed arbitrarily, but each must stay in its original order. For example, consider forming “tcraete” from “cat” and “tree”: String A: cat String B: tree String C: tcraete As you can see, we can form the third string by alternating characters from the two strings. As a second example, consider forming "catrtee

Kmeans算法解析及基于MapReduce的并行化实现

Kmeans算法解析及基于MapReduce的并行化实现

Kmeans算法,最为经典的基于划分的聚类方法 Kmeans算法: k-means 算法接受参数 k ;然后将事先输入的n个数据对象划分为 k个聚类以便使得所获得的聚类满足:同一聚类中的对象相似度较高;而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”(引力中心)来进行计算的。 K-means算法是最为经典的基于划分的聚类方法,是十大经典数据挖掘算法之一。K-means算法的基本思想是:以空间中k个点为中心进行聚类,对最靠近他们的对象归类。通过迭代的方法,逐次更新各聚类中心的值,直至得到最好的聚类结果。 假设要把样本集分为c个类别,算法描述如下: (1)适当选择c个类的初始中心; (2)在第k次迭代中,对任意一个样本,求其到c个中心的距离,将该样本归到距离最短的中心所在的类; (3)利用均值等方法更新该类的中心值; (4)对于所有的c个聚类中心,如果利用(2)(3)的迭代法更新后,值保持不变,则迭代结束,否则继续迭代。 该算法的最大优势在于简洁和快速。算法的关键在于初始中心的选择和距离公式。

ACM刷题之-2015微软编程之美资格赛

ACM刷题之-2015微软编程之美资格赛

题目一:2月29 时间限制:2000ms 单点时限:1000ms 内存限制:256MB 描述 给定两个日期,计算这两个日期之间有多少个2月29日(包括起始日期)。 只有闰年有2月29日,满足以下一个条件的年份为闰年: 1. 年份能被4整除但不能被100整除 2. 年份能被400整除 输入 第一行为一个整数T,表示数据组数。 之后每组数据包含两行。每一行格式为"month day, year",表示一个日期。month为{“January”, “February”, “March”, “April”, “May”, “June”, “July”, “August”, “September”, “October”, “November” , “December”}中的一个字符串。day与year为两个数字。 数据保证给定的日期合法且第一个日期早于或等于第二个日期。 输出 对于每组数据输出一行,形如"Case #X: Y"。X为数据组数,从1开始,Y为答案。 数据范围

ACM刷题之-POJ-3749(破译密码)

ACM刷题之-POJ-3749(破译密码)

Description 据说最早的密码来自于罗马的凯撒大帝。消息加密的办法是:对消息原文中的每个字母,分别用该字母之后的第5个字母替换(例如:消息原文中的每个字母A都分别替换成字母F)。而你要获得消息原文,也就是要将这个过程反过来。 密码字母:A B C D E F G H I J K L M N O P Q R S T U V W X Y Z M 原文字母:V W X Y Z A B C D E F G H I J K L M N O P Q R S T U 注意:只有字母会发生替换,其他非字母的字符不变,并且消息原文的所有字母都是大写的。 Input 最多不超过100个数据集组成,每个数据集之间不会有空行,每个数据集由3部分组成: 起始行:START 密码消息:由1到200个字符组成一行,表示凯撒发出的一条消息. 结束行:END 在最后一个数据集之后,是另一行:ENDOFINPUT Output 每个数据集对应一行,是凯撒的原始消息。 Sample Input START NS BFW, JA

ACM刷题之-POJ-1191(棋盘分割)

ACM刷题之-POJ-1191(棋盘分割)

Description 将一个 8* 8的棋盘进行如下分割:将原棋盘割下一块矩形棋盘并使剩下部分也是矩形,再将剩下的部分继续如此分割,这样割了(n-1)次后,连同最后剩下的矩形棋盘共有 n 块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行) 原棋盘上每一格有一个分值,一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成 n 块矩形棋盘,并使各矩形棋盘总分的均方差最小。 均方差,其中平均值,xi 为第 i 块矩形棋盘的总分。 请编程对给出的棋盘及 n,求出 O'的最小值。 Input 第 1 行为一个整数 n(1 < n < 15)。 第 2 行至第 9 行每行为 8 个小于 100 的非负整数,表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。 Output 仅一个数,为 O'(四舍五入精确到小数点后三位)。 Sample Input 3 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

ACM刷题之-POJ-3662(Telephone Lines)

ACM刷题之-POJ-3662(Telephone Lines)

Description Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of the cables required to connect his farm to the phone system. There are N (1 ≤ N ≤ 1,000) forlorn telephone poles conveniently numbered 1..N that are scattered around Farmer John’s property; no cables connect any them. A total of P (1 ≤ P ≤ 10,000) pairs of poles can be connected by a cable; the rest are too far apart. The i-th cable

ACM刷题之-POJ-3333(Co-workers from Hell)

ACM刷题之-POJ-3333(Co-workers from Hell)

Description A watchman has to check a number of chambers in the factory each night according to a schedule which specifies the order in which the chambers must be visited and the time it takes to check each chamber. The watchman starts his job each night starting from the first chamber and leaves the factory and goes home when he checks the final chamber. He normally checks all other chambers, but in our story he may not actually do so. Having access to this schedule, a co-worker wants to

ACM刷题之-POJ-3006(Dirichlet's Theorem on Arithmetic Progre)

ACM刷题之-POJ-3006(Dirichlet's Theorem on Arithmetic Progre)

Description If a and d are relatively prime positive integers, the arithmetic sequence beginning with a and increasing by d, i.e., a, a + d, a + 2d, a + 3d, a + 4d, …, contains infinitely many prime numbers. This fact is known as Dirichlet’s Theorem on Arithmetic Progressions, which had been conjectured by Johann Carl Friedrich Gauss (1777 - 1855) and was proved by Johann Peter Gustav Lejeune Dirichlet (1805 - 1859) in 1837. For example, the arithmetic sequence beginning with 2 and i

ACM刷题之-POJ-1405(Heritage)

ACM刷题之-POJ-1405(Heritage)

Description Your rich uncle died recently, and the heritage needs to be divided among your relatives and the church (your uncle insisted in his will that the church must get something). There are N relatives (N <= 18) that were mentioned in the will. They are sorted in descending order according to their importance (the first one is the most important). Since you are the computer scientist in the family, your relatives asked you to help them. They need help, because there are some blanks i

ACM刷题之-POJ-1192(最优连通子集)

ACM刷题之-POJ-1192(最优连通子集)

Description 众所周知,我们可以通过直角坐标系把平面上的任何一个点P用一个有序数对(x, y)来唯一表示,如果x, y都是整数,我们就把点P称为整点,否则点P称为非整点。我们把平面上所有整点构成的集合记为W。 定义1 两个整点P1(x1, y1), P2(x2, y2),若|x1-x2| + |y1-y2| = 1,则称P1, P2相邻,记作P1P2,否则称P1, P2不相邻。 定义 2 设点集S是W的一个有限子集,即S = {P1, P2,…, Pn}(n >= 1),其中Pi(1 <= i <= n)属于W,我们把S称为整点集。 定义 3 设S是一个整点集,若点R, T属于S,且存在一个有限的点序列Q1, Q2, ?, Qk满足: 1. Qi属于S(1 <= i <= k); 2. Q1 = R, Qk = T; 3. QiQi + 1(1 <= i <= k-1),即Qi与Qi + 1相邻; 4. 对于任何1 <= i < j <= k有Qi ≠ Qj; 我们则称点R与点T在整点集S上连通,把点序列Q1, Q....

ACM刷题之-POJ-1185(炮兵阵地)

ACM刷题之-POJ-1185(炮兵阵地)

Description 司令部的将军们打算在 NM 的网格地图上部署他们的炮兵部队。一个 NM 的地图由 N 行 M 列组成,地图的每一格可能是山地(用"H" 表示),也可能是平原(用"P"表示),如下图。在每一格平原地形上最多可以布置一支炮兵部队(山地上不能够部署炮兵部队);一支炮兵部队在地图上的攻击范围如图中黑色区域所示: 如果在地图中的灰色所标识的平原上部署一支炮兵部队,则图中的黑色的网格表示它能够攻击到的区域:沿横向左右各两格,沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在,将军们规划如何部署炮兵部队,在防止误伤的前提下(保证任何两支炮兵部队之间不能互相攻击,即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内),在整个地图区域内最多能够摆放多少我军的炮兵部队。 Input 第一行包含两个由空格分割开的正整数,分别表示 N 和 M; 接下来的 N 行,每一行含有连续的 M 个字符('P'或者'H'),中间没有空格。按顺序表示地图中每

ACM刷题之-POJ-1021(2D-Nim)

ACM刷题之-POJ-1021(2D-Nim)

Description The 2D-Nim board game is played on a grid, with pieces on the grid points. On each move, a player may remove any positive number of contiguous pieces in any row or column. The player who removes the last piece wins. For example, consider the left grid in the following figure. The player on move may remove (A), (B), (A, B), (A, B, C), or (B,F), etc., but may not remove (A, C), (D, E), (H, I) or (B, G). For purposes of writing 2D-

hadoop下基于mapreduce实现pagerank算法

hadoop下基于mapreduce实现pagerank算法

摘要: PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由[1] 根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。Google用它来体现网页的相关性和重要性,在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。Google的创始人拉里·佩奇和谢尔盖·布林于1998年在斯坦福大学发明了这项技术。 PageRank通过网络浩瀚的超链接关系来确定一个页面的等级。Google把从A页面到B页面的链接解释为A页面给B页面投票,Google根据投票来源(甚至来源的来源,即链接到A页面的页面)和投票目标的等级来决定新的等级。简单的说,一个高等级的页面可以使其他低等级页面的等级提升。 PageRank的核心公式是: PR(A)=(1-d)+d(PR(B)/C+PR(C)/C……PR(Z)/C) - PR(A)是指网页A的PR数值 - PR(i)是链接向A页面的i页面的PR值 - C是网页i往其他页面输出的链接的数量 - d是一个常数,谷歌设置为0.

关于

关于

大名潘建锋,小名嘛,好像也没有。生在潮汕,长在潮汕,平平静静生活,普普通通生长,偶有微澜,不提也罢; 糊里糊涂去了武汉上大学,似懂非懂选了计算机专业。 混迹过潮汕、武汉、深圳,如今来到了北京做一只呆萌的后台程序猿,变成了北漂。每天工作的时候就写写业务代码,业余的时候呢就写写自己喜欢的代码,然后读读书、跑跑步、看看动漫、拍拍照、听听歌,致力于让自己的生活变得精致且快乐,脚踏实地的同时,偶尔也仰望一下星空。

python深坑之迭代器和生成器

python深坑之迭代器和生成器

本文以实例详解了python的迭代器与生成器,具体如下所示: 迭代器概述: 迭代器是访问集合元素的一种方式。迭代器对象从集合的第一个元素开始访问,直到所有的元素被访问完结束。迭代器只能往前不会后退,不过这也没什么,因为人们很少在迭代途中往后退。 迭代器的优点 对于原生支持随机访问的数据结构(如tuple、list),迭代器和经典for循环的索引访问相比并无优势,反而丢失了索引值(可以使用内建函数enumerate()找回这个索引值)。但对于无法随机访问的数据结构(比如set)而言,迭代器是唯一的访问元素的方式。 另外,迭代器的一大优点是不要求事先准备好整个迭代过程中所有的元素。迭代器仅仅在迭代到某个元素时才计算该元素,而在这之前或之后,元素可以不存在或者被销毁。这个特点使得它特别适合用于遍历一些巨大的或是无限的集合,比如几个G的文件,或是斐波那契数列等等。 迭代器更大的功劳是提供了一个统一的访问集合的接口,只要定义了__iter__()方法对象,就可以使用迭代器访问。 迭代器有两个基本的方法 next方法:返回迭代器的下一

星光未满,月色失约。