存档

文章标签 ‘笔试’

关于字符串处理的一些问题 | 目录

2012年7月8日 没有评论

---

字符串处理问题很常见,一般来说,这样的问题分为单字符串问题和双字符串问题。本博对这些问题也陆续整理了一点,这里做个目录,方便查找,以后慢慢更新。

===单字符串问题===

==反转字符串的思考及三种解法==

==最长重复子串==

==最长不重复子串==

==最长回文子串==

===双字符串问题===

==字符串相似度(编辑距离)==

==最长公共子序列(LCS)==

==最长公共子串==

本节相关代码可以到这里下载。

阅读全文...

有趣的笔试题:捞鱼问题

2012年6月12日 2 条评论

---

话说这道题还是三年前径点公司来学院笔试中的一道题目,当时刚进入实验室,师兄在带着我们做新生培训的时候做过这道题,最近回顾DP的一些基础,翻找以前写的程序,发现了这道题,就贴一下,给出两种方法的代码,并对比了它们在不同规模问题下的效率。

题目:20个桶,每个桶中有10条鱼,用网从每个桶中抓鱼,每次可以抓住的条数随机,每个桶只能抓一次,问一共抓到180条的排列有多少种 (也可求概率)。

分析:我们要在20个桶中一共抓取180条鱼,每个桶能抓到鱼的条数为0-10,仔细想下,这个问题是可以分解成子问题的:假设我们在前i个桶中抓取了k(0<=k<=10*i)条鱼,那么抓取180条鱼的排列种数就等于在剩下的(20-i)个桶中抓取(180-k)条鱼的方法加上前i个桶中抓取k条鱼的方法。

例如,在第一个桶中抓取了2条鱼,那么总的排列数等于在剩下19个桶中抓取178条鱼的排列种数;如果在第一个桶中抓取了10条鱼,那么总的排列数等于在剩下19个桶中抓取170条鱼的排列数,,,依次分解该问题,总的排列数就等于所有这些排列数的总和。有点DP的感觉。

换个思维,在实现上这个题目可以有更为简洁的方法,我们看看这个问题的对偶问题,抓取了180条鱼之后,20个桶中剩下了20条鱼,不同的抓取的方法就对应着这些鱼在20个桶中不同的分布,于是问题转化为将20条鱼分到20个桶中有多少中不同的排列方法(这个问题当然也等价于180条鱼分到20个桶中有多少种不同的方法)?其中,每个桶最多放10条,最少放0条。这样一转化,无论是用搜索还是DP,问题规模都缩小了很大一块。

阅读全文...