存档

文章标签 ‘面试’

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

2012年7月8日 没有评论

---

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

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

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

==最长重复子串==

==最长不重复子串==

==最长回文子串==

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

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

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

==最长公共子串==

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

阅读全文...

面试题:从给定的N个正数中选取若干个数之和最接近M

2012年6月11日 5 条评论

---

这道题跟捞鱼问题一样,都是刚进实验室新生培训那会儿做过的题目,不过这个是一师姐当时找工作的面试题。

如题,并输出该子序列

测试用例:2,9,5,7,4,11,10

分别输出最接近33、40、47、60的子序列

分析:N个数之和接近M,将M看做一个容量的背包,这个题目就变成了典型的01背包,M容量下求最优解并输出最优方案,这在01背包中都整理过,上代码:

阅读全文...