快速求出某数的所有约数

故事是这样的,有一场比赛题,本来应该是考察 DP 的,但是算法写出来之后,一值暴 TLE,我一开始以为是 C++ 的 map 是 log(n) 的复杂度,于是改成了 unorder_map 试了下,结果还是 TLE。最后花了很久定位到求约数的算法超时。 按照人惯性的思维,求一个数的约数,直接使用一个 for 就可以了。而且算法的复杂度是 O(n) 具体一点可以说是 O(sqrt(n)) 也是可以接受的。 但是,还是有另一个更加快速的方法。 using namespace std; int prime[100000]; bool isPrime[1000005]; void getPrime(int x){ for (int i = 1; i < x; i += 2) { isPrime[i] = 1; ... [阅读全文]

字符串纠错

故这样的,之前在 Leetcode 遇到一道题:『Edit Distance』, 当时做的时候并没有太多的思考,原因也很简单,不知道这道题的算法什么时候可以用得到。 直到,最近在看搜索引擎部分的算法,在处理用户的拼写异常的时候,比如,当用户搜索 『苏州大雪』的时候,怎么能进行纠错为『苏州大学』。 亦或者,在进行爬虫数据筛选的时候,比如在 B 站进行动漫数据抓取的时候,有很多的 UP 主会对动漫的名字做一定的修改,比如『(xx 字幕组)小林家的龙女仆』或者『小林家的龙女仆(高清)』。按照我之前的处理方式,还是很简单的 KV 存储,所以在计算弹幕和播放量的时候,并没有统计合并这样的数据。而从实际情况上来看的话,这两个的数据是应该统计在一起的。 所以,发现这个算法也是可以用的。而且,这个算法确实挺有意思。 using namespace std; ... [阅读全文]

Regular Expression Matching的NFA解法

事情的缘由是,在LeetCode上遇到了这么一题:Regular Expression Matching,大体的意思是用要求我们构建能实现一个简单的带规则的字符串匹配。 其实题目的意思已经比较明白,就是希望我们能实现正则的简单功能。比如"."代表所有的字符,"*"表示重复0到正无穷次。这道题可以用DP或者Trie树解决,并且效率也比较高,但是,因为最近正好写了脚本解释器,所以正好尝试用下有穷自动机来解题。 有穷自动机分为两种,一种是NFA,一种是DFA。两者之间的区别就在于构造的方式,对于NFA来说,输入一个字符,它对应的是一个状态集,而对于DFA,则是一个固定的状态。两者也可以互相转换。相比较而言,对于这种相对比较简单的规则索引,我比较倾向于使用NFA。 首先我们需要对其进行构建NFA结构。因为本题的规则相对比较简单。比如说"a*"这样的结构,我们可以构造出如下的N... [阅读全文]

2015编程之美资格赛记录

Problem 1: 2月29日 描述 给定两个日期,计算这两个日期之间有多少个2月29日(包括起始日期)。 只有闰年有2月29日,满足以下一个条件的年份为闰年: 年份能被4整除但不能被100整除 年份能被400整除 输入 第一行为一个整数T,表示数据组数。 之后每组数据包含两行。每一行格式为"month day, year",表示一个日期。month为 { "January", "February", "March", "April", "May", "June", "July", "August", "September","October", "November" , "December"} 中的一个字符串。day与y... [阅读全文]

Oracle面试之行

    之前也是和同学做了一下Oracle的PAC测试,也没有怎么去想结果,但是在周六的晚上九点半接到电话,说今天要去面试- -,然后就翘了计算机组成去面试了,其实呢,面试官挺好的,主要我去的比较早,然后一个人挺无聊的,就看了一会kindle.     接下来说面试的内容了,总体来说,难度不是很难,但是很基础,有些内容以前是看到的,但是在这种情况下,一时间也没有想起来。。。不得不说是一个败笔。     第一个是英文的自我介绍,这是被人坑的,我之前问了一下进甲骨文的学长,他说,不需要进行英文面试,于是我就没有准备,然后,就悲剧了,。还好我的英文还没有想像中的那么烂,不过有一个很有趣的小插曲,就是中途我有一个单词不会拼,就是红外传感器,传感器是sensor但是红外我就不知到了... [阅读全文]

算法-卡特兰数(组合数学)

常见的问题,HDOJ 1133 他的递推关系式为: 几种常见的题目类型: 括号化 矩阵链乘: P=a1×a2×a3×……×an,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案? 出栈顺序 一个栈(无穷大)的进栈序列为1,2,3,…,n,有多少个不同的出栈序列? 突多边形三角划分(握手问题) 在一个凸多边形中,通过若干条互不相交的对角线,把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n,求不同划分的方案数f(n)。... [阅读全文]