#牛客堂直播视频#动态规划串讲(上)(2015.7.29)
【本期题目】
1、最长递增子序列
【题目】
给定数组arr,返回arr的最长递增子序列。
【举例】
arr=[2,1,5,3,6,4,8,9,7],返回的最长递增子序列为[1,3,4,8,9]。
【要求】
如果arr长度为N,请实现时间复杂度为O(N*logN)的方法。
2、最长公共子序列问题
【题目】
给定两个字符串str1和str2,返回两个字符串的最长公共子序列。
【举例】
str1=“1A2C3D4B56”,str2=“B1D23CA45B6A”。
“123456”或者“12C4B6”都是最长公共子序列,返回哪一个都行。
【难度】
尉 ★★☆☆
3、最长公共子串问题
【题目】
给定两个字符串str1和str2,返回两个字符串的最长公共子串。
【举例】
str1=“1AB2345CD”,str2=“12345EF”。返回“2345”。
【要求】
如果str1长度为M,str2长度为N,实现时间复杂度为O(M*N),额外空间复杂度为O(1)的方法。
【难度】
校 ★★★☆
4、最小编辑代价
【题目】
给定两个字符串str1和str2,再给定三个整数ic、dc和rc分别代表插入、删除和替换一个字符的代价,返回将str1编辑成str2的最小代价。
【举例】
str1=“abc”,str2=“adc”,ic=5,dc=3,rc=2。
从“abc”编辑成“adc”,把’b’替换成’d’是代价最小的。所以返回2。
str1=“abc”,str2=“adc”,ic=5,dc=3,rc=100。
从“abc”编辑成“abd”,先删除’b’然后插入’d’是代价最小的。所以返回8。
str1=“abc”,str2=“abc”,ic=5,dc=3,rc=2。
不用编辑了,本来就是一样的字符串。所以返回0。
【难度】
校 ★★★☆
5、字符串的交错组成
【题目】
给定三个字符串str1、str2和aim。如果aim包含且仅包含来自str1和str2的所有字符,而且在aim中属于str1的字符之间保持原来在str1中的顺序,属于str2的字符之间保持原来在str2中的顺序,那么称aim是str1和str2的交错组成。实现一个函数,判断aim是否是str1和str2交错组成。
【举例】
str1=“AB”,str2=“12”。那么“AB12”、“A1B2”、“A12B”、“1A2B”和“1AB2”等等都是str1和str2交错组成。
【难度】
校 ★★★☆
注:下面回帖给出了源代码供参考。
【分享嘉宾介绍】
左程云
华中科技大学本科--计算机科学与技术专业、 芝加哥大学硕士--计算机科学专业
IBM软件工程师、 百度软件工程师、 刷题5年的算法热爱者
《程序员代码面试指南--IT名企算法与数据结构题目最优解》 作者,电子工业出版社7月底将出版发行,书籍涉及算法与数据结构编程题目240道以上,并且个人实现出最优解,大部分题目为面试高频题
【参与牛客堂直播】
每周三晚8:00~9:30,直播页面http://www.nowcoder.com/live/courses
【直播题目讨论】
加入牛客5群272820159