[toc]
这次笔试惨败,一道也没a,基本都考到了不熟练的部分。
总结一下考到的算法知识点。
第一题
第一题
一个字符串,在头尾最少添加多少字母使得字符串是回文字符串?
思路:
暴力法
针对题目分析,我们要找的是填充字符之后长度最短的回文字串。如何使填充后的字符串最短呢?
我们倒过来想,我们得到的一定是一个回文字符串,由于题目要求我们只能在字符串尾部添加字符,因此去掉我们添加的字符,最后的字符一定是原字符串的子回文字串的一端,我们尽量复用原字符串的回文子串就可以使得添加的字符最少。
因此,我们要做的就是在原字符串中寻找最长的后缀回文字串,并把剩下部分反转拼接到最后。
这里贴上 LC214 的暴力解法
1 | class Solution { |
时间复杂度$O(N^2)$,测试用例超时。
利用 KMP 算法优化字符串匹配
这里需要先熟悉一下 KMP 算法。
KMP 算法的基本思想:当出现不匹配时,就能知道一部分文本的内容。
使用一个数组来记录匹配失败时,模式指针应该回退多远。
数组内记录的元素表示:与文本指针下一个位置比较的模式指针的位置。
KMP 计算 next 数组,实际上就是在找 pattern 字串有没有相同的前后缀,而我们寻找回文子串的时候,将正序字符串与逆序字符串相匹配,中间有很多重复比较,利用 KMP 算法的中间步骤可以优化匹配时间复杂度,找到原字符串最长回文前缀。
第二题
第二题
一个数组,如何使得两个不相交子集之和相等且最大?
思路
brute-force
直接 DFS,每一个数字都有三种选择:分到 A 子集,分到 B 子集,丢弃,DFS 搜索直到找到匹配结果。
第三题
第三题
售票处8点开门,有 n 个人排队,每个人可以自己买,也可以和后面的人一起买,最后一个人只能自己买或者和前面的人买,给出两个数组表示两种方案所需的时间,问最短时间。
思路
最基础的动态规划,将状态取为前 i
个人需要的最短排队时间,由于第 i + 1
个人是否能与前一个人一起买票取决于第 i
个人是否与第 i - 1
个人买,又知道两人合买的时间,所以得出状态转移表达式$dp[i] = min(dp[i-1]+single[i],\ dp[i-2]+double[i-1])$。
第四题
第四题
有 n 个教授,每个教授都可以认可其他教授,且认可具有传递性,问有多少对教授相互认可,给出 edge 的数目以及每个 edge。
思路
tarjin 算法?