科大讯飞笔试 8.13 AK
睡到14:37才醒,迟到了37min,还好题目不难。
编程题用时17min,
总用时40min。
题3:数量级10的5次方,枚举所有的子串复杂度n方,肯定不行。
A中子串数量为 n * (n + 1) / 2
B中新子串的数量计算如下:
用hash表h记录a数组各元素的坐标。
依次遍历b数组的每个元素,再根据h获取对应a中的坐标
然后两个坐标同时向后移动,直到不匹配的时候两者就出现了不同子串,统计b坐标剩余的长度,即为当前节点的新子串数量。
比如:
a: ...ABC..
b: ...ABDSD
从A开始匹配,b的D与a的C无法匹配,则ABD、ABDS、ABDSD都是在a中不曾出现的子串,数量为 (字符串长度-D的坐标+1)
优化一下:两个坐标移动过程中相同的公共节点数量也是b坐标剩余的长度,所以可以直接计算。
即由于A匹配过最长的子串了,B的数量也是(字符串长度-D的坐标+1),
则下一步可以直接开始从D开始匹配。
时间复杂度O(N)
不太擅长讲解,可能不太清楚
代码没保存,因为直接在线提交的,没用上本地ide
#科大讯飞信息集散地#
编程题用时17min,
总用时40min。
题3:数量级10的5次方,枚举所有的子串复杂度n方,肯定不行。
A中子串数量为 n * (n + 1) / 2
B中新子串的数量计算如下:
用hash表h记录a数组各元素的坐标。
依次遍历b数组的每个元素,再根据h获取对应a中的坐标
然后两个坐标同时向后移动,直到不匹配的时候两者就出现了不同子串,统计b坐标剩余的长度,即为当前节点的新子串数量。
比如:
a: ...ABC..
b: ...ABDSD
从A开始匹配,b的D与a的C无法匹配,则ABD、ABDS、ABDSD都是在a中不曾出现的子串,数量为 (字符串长度-D的坐标+1)
优化一下:两个坐标移动过程中相同的公共节点数量也是b坐标剩余的长度,所以可以直接计算。
即由于A匹配过最长的子串了,B的数量也是(字符串长度-D的坐标+1),
则下一步可以直接开始从D开始匹配。
时间复杂度O(N)
不太擅长讲解,可能不太清楚
代码没保存,因为直接在线提交的,没用上本地ide
#科大讯飞信息集散地#
全部评论
用set ac0
第三题为啥老超时😂
怎么回事呢?佬
大佬可以发一下第三题代码吗,私发也行,感谢!
ak了,简历挂了捏
老哥请问科大讯飞笔试的代码题 需要自己写输入输出吗
相关推荐
11-19 18:45
西安邮电大学 采编 点赞 评论 收藏
分享
点赞 评论 收藏
分享
10-18 13:02
西安理工大学 C++ 点赞 评论 收藏
分享
拿到ssp可以么:有钱真好啊,有钱还拿到50w+真好啊,50w+还能wlb更好了,我要嫉妒到发疯了
点赞 评论 收藏
分享