科大讯飞笔试 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

#科大讯飞信息集散地#
全部评论
用set ac0
2 回复 分享
发布于 2023-08-13 15:51 四川
第三题为啥老超时😂
1 回复 分享
发布于 2023-08-13 15:31 上海
怎么回事呢?佬
1 回复 分享
发布于 2023-08-13 15:51 四川
大佬可以发一下第三题代码吗,私发也行,感谢!
点赞 回复 分享
发布于 2023-08-13 16:07 北京
ak了,简历挂了捏
点赞 回复 分享
发布于 2023-08-18 16:55 上海
老哥请问科大讯飞笔试的代码题 需要自己写输入输出吗
点赞 回复 分享
发布于 2023-08-24 15:30 山东

相关推荐

斑驳不同:还为啥暴躁 假的不骂你骂谁啊
点赞 评论 收藏
分享
牛舌:如果我不想去,不管对方给了多少,我一般都会说你们给得太低了。这样他们就会给下一个offer的人更高的薪资了。
点赞 评论 收藏
分享
点赞 5 评论
分享
牛客网
牛客企业服务