科大讯飞笔试 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:51 四川
第三题为啥老超时😂
1 回复 分享
发布于 2023-08-13 15:31 上海
老哥请问科大讯飞笔试的代码题 需要自己写输入输出吗
点赞 回复 分享
发布于 2023-08-24 15:30 山东
ak了,简历挂了捏
点赞 回复 分享
发布于 2023-08-18 16:55 上海
大佬可以发一下第三题代码吗,私发也行,感谢!
点赞 回复 分享
发布于 2023-08-13 16:07 北京

相关推荐

2025-11-13 19:44
哈尔滨工程大学 Java
二战小红书,又是二面挂,还是做不到。先吃饭吧。9.18小红书商业技术实习深挖分布式锁设置五分钟过期并在finally里释放锁会不会有释放不了的时候,看门狗机制如何实现,它的后台线程是什么类型spisynchronized,monitorexit执行两次你知道吗AQS垃圾回收器mysql锁redis过期删除,怎么选取过期key,数据量大的话这键值字典和过期字典会不会比较大手撕最长上升子序列9.24小红书商业技术实习FAQ的理解实习意图识别或者提示词这块有什么细节的困难,怎么解决的实习定时任务和kafka发消息这块实现细节,现在定时任务要扫描的数据变成亿级了该怎么设计实习问答匹配率提升20%怎么来的数据,分子分母是啥看你实习了挺久,没提转正吗如果offer比较多你如何选择无手撕11.10小红书风控工程介绍实习,参数提取检验补齐有了新业务意图是需要再扩展吗,意图识别提升10%哪来的,哪块是最有挑战的,系统吞吐量多少,用到哪些大模型了java注解,自己用过吗jvm内存模型mysql什么情况适合建索引kafka怎么消息去重linux查看端口被哪个进程占用命令手撕全排列11.12小红书风控工程考研辅导经历,考研成绩,本科成绩,为什么考研,高考为什么没考好,本科成绩平平研究生成绩不错是怎么转变的,为什么走工程不走算法实习经历,提取参数的过程中用户问别的会怎么样,挑战困难,转正情况kafka会丢失消息吗,消费者消费失败broker怎么感知到从而重新投递呢,消费者怎么知道自己从哪里重新拉取,消费成功后没及时记录offset会不会重复消费rpc过程怎么找到对应服务的,一直访问注册中心会不会压力大优缺点,自驱力高的原因,怎么做到长期坚持的,平时怎么学习,平时沟通也这么谨慎吗,有什么爱好进程线程,文件内容读到内存是单线程还是多线程好,磁盘是机械磁盘和固态磁盘对答案有影响吗大文件中内容都是单词,需要对单词排序,什么思路,会内存溢出吗无手撕
查看28道真题和解析
点赞 评论 收藏
分享
评论
点赞
5
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务