1.13 爱奇艺2024校招笔试真题

1.13.1 分词结果修改

【题目描述】

一个已经用分词算法分好词的中文句子，由于分词算法有一定错误率使得某些词汇没有正确分词，所以希望用一个词典中的词去进行匹配并把句中所有能完全匹配上的字符串强行改成一个词，但其它不受影响的分词结果不改变，请实现满足这个要求这样的算法。（注：测试数据中不出现中文字符，均使用类似样例2的字符， 且不会出现多解、匹配词相互有冲突的情况）

输入描述：

第一行是分好词的一句话（字符串），词与词间由空格分开；第二行是若干个需要匹配的词，词与词间由空格分开

输出描述：

修改后的分词结果（一个字符串），词与词间由空格分开

输入样例1：

可 今日 小 主要 参加 殿 选 小主 殿选

输出样例1：

可 今日 小主 要 参加 殿选

输入样例2：

aa bcd edf deda ded

输出样例2：

aa bc ded f ded a

输入样例3：

娘娘 谬赞 ， 臣妾愧 不敢 当 愧不敢当

输出样例3：

娘娘 谬赞 ， 臣妾 愧不敢当

【解题思路】

使用基本数组结构记录每个字符后是否切割即可。

【参考代码】

import sys

def solution(seged_sent, dictionary):

seged_sent = seged_sent.split()

dictionary = dictionary.split()

sent = list('x'.join(['o'.join(list(word)) for word in seged_sent]) + 'x')

for k in dictionary:

for i in range(int(len(sent) / 2)):

match = ''

if len(k) <= int(len(sent[i * 2:]) / 2):

for j in range(len(k)):

match += sent[(i + j) * 2]

if match == k:

for l in range(j):

sent[(i + l) * 2 + 1] = 'o'

sent[(i + j) * 2 + 1] = 'x'

sent[i * 2 - 1] = 'x'

res_sent = []

word = ''

for i in range(int(len(sent) / 2)):

word += sent[i * 2]

if sent[i * 2 + 1] == 'x':

res_sent.append(word)

word = ''

return ' '.join(res_sent)

if __name__ == '__main__':

seged_sent, dictionary = sys.stdin.readlines()

print(solution(seged_sent, dictionary))

1.13.2 联谊会

【题目描述】

某IT公司举办部门间的相亲会，A部门出了n女生，B部门出了m个男生，要求被男女生配对年龄必须相同（如25岁的女生要求配对25岁的男生，21岁的女生要求配对21岁的男生）。联谊会举办前，举办人突然发现，两边人数不同，年龄也不都配对。现在要求B部门调整男生安排，可以做的操作包括添加新的男生，去除某男生，或者替换某个男生。怎么做操作步骤最少？

输入描述：

输入女生年龄数组，输入男生年龄数组

输出描述：

最小的操作数

输入样例：

21 23 24 29

20 23 25 28 30

输出样例：

4

【解题思路】

本题为动态规划算法中的最短编辑距离算法。

从两队人马中最后一个人开始考察即30和29。显然二者不配对，那么我们有以下三种处理办法：

(1) 新叫一个人：男生队伍中新叫来一个29岁男生，那么男生变成了20 23 25 28 30 29，女生仍然是21 23 24 29，由于此时末尾人员配对成功，那么就变成了比较20 23 25 28 30和21 23 24的操作数，即d(20 23 25 28 30, 21 23 24 29) = d(20 23 25 28 30, 21 23 24) + 1。可以写成d(I，j) = d(i，j - 1) +1。表示下次比较的女