字符串纠错

故这样的,之前在 Leetcode 遇到一道题:『Edit Distance』, 当时做的时候并没有太多的思考,原因也很简单,不知道这道题的算法什么时候可以用得到。 直到,最近在看搜索引擎部分的算法,在处理用户的拼写异常的时候,比如,当用户搜索 『苏州大雪』的时候,怎么能进行纠错为『苏州大学』。 亦或者,在进行爬虫数据筛选的时候,比如在 B 站进行动漫数据抓取的时候,有很多的 UP 主会对动漫的名字做一定的修改,比如『(xx 字幕组)小林... [阅读全文]

Regular Expression Matching的NFA解法

事情的缘由是,在LeetCode上遇到了这么一题:Regular Expression Matching,大体的意思是用要求我们构建能实现一个简单的带规则的字符串匹配。 其实题目的意思已经比较明白,就是希望我们能实现正则的简单功能。比如"."代表所有的字符,"*"表示重复0到正无穷次。这道题可以用DP或者Trie树解决,并且效率也比较高,但是,因为最近正好写了脚本解释器,所以正好尝试用下有穷自动机来解题。 有穷自动机分为两种,一种是NFA,一种是DFA。两者之间的区别就... [阅读全文]

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", "Nov... [阅读全文]

Oracle面试之行

    之前也是和同学做了一下Oracle的PAC测试,也没有怎么去想结果,但是在周六的晚上九点半接到电话,说今天要去面试- -,然后就翘了计算机组成去面试了,其实呢,面试官挺好的,主要我去的比较早,然后一个人挺无聊的,就看了一会kindle.     接下来说面试的内容了,总体来说,难度不是很难,但是很基础,有些内容以前是看到的,但是在这种情况下,一时间也没有想起来。。。不得不说是一个败笔。   &nbs... [阅读全文]

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

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