#牛客堂直播视频#时间复杂度专题一(2015.06.17)
 

【本期题目】
Manacher算法
【题目】
给定一个字符串str,返回str中的最长回文子串的长度。
【举例】
str=“123”。其中的最长回文子串“1”或者“2”或者“3”,所以返回1。
str=“abc1234321ab”。其中的最长回文子串“1234321”,所以返回7。
【进阶题目】
给定一个字符串str,想通过添加字符的方式使得str整体都变成回文字符串,但要求只能在str的末尾添加字符,请返回在str后面添加的最短字符串。
【举例】
str=“12”。在末尾添加“1”之后,str变为“121”是回文串。在末尾添加“21”之后,str变为“1221”也是回文串。但“1”是所有添加方案中最短的,所以返回“1”。
【要求】
如果str长度为N,解决原问题和进阶问题的时间复杂度都达到O(N)。

bfprt算法及其相关
找到无序数组中最小的K个数
【题目】
给定一个无序的整型数组arr,找到其中最小的k个数。
【要求】
如果数组arr的长度为N,排序之后自然可以得到最小的k个数,此时时间复杂度为排序的时间复杂度即O(N*logN)。本题要求读者实现时间复杂度O(N*logK)和O(N)的方法。

KMP算法
【题目】
给定两个字符串str和match,长度分别为N和M。实现一个算法,如果字符串str中含有字串match,则返回match在str中的开始位置,不含有则返回-1。
【举例】
str=“acbc”,match=“bc”。返回2。
str=“acbc”,match=“bcc”。返回-1。
【要求】
如果match的长度大于str长度(M>N),str必然不会含有match,可直接返回-1。但如果N>=M,要求算法复杂度O(N)。

注:下面回帖给出了源代码供参考。

【分享嘉宾介绍】
左程云
华中科技大学本科--计算机科学与技术专业、 芝加哥大学硕士--计算机科学专业
IBM软件工程师、 百度软件工程师、 刷题5年的算法热爱者
《程序员代码面试指南--IT名企算法与数据结构题目最优解》 作者,电子工业出版社7月底将出版发行,书籍涉及算法与数据结构编程题目240道以上,并且个人实现出最优解,大部分题目为面试高频题

【参与牛客堂直播】
每周三晚8:00~9:30,直播页面http://www.nowcoder.com/live/courses

【直播题目讨论】
加入牛客5272820159

【上期牛客堂回顾】

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-20 17:21
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-29 23:08
浙江大学_2021
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 11 评论
分享

全站热榜

正在热议