首页 > 阿里0803笔试第二题,求测试样例
头像
tzdnn
编辑于 2020-08-05 20:50
+ 关注

阿里0803笔试第二题,求测试样例

'''
参考了这位大佬的思路:https://blog.csdn.net/qq_22522375/article/details/107771758 如果有发现代码思路有问题,欢迎指教。
给定一个a-f组成的字符串,对其进行删除,要求所有的a在c和e之前且所有的c在e之前,
所有的b在d和f之前且所有的d在f之前,求删除后满足串的最大长度'''

strs = input()

l1,l2 = [],[]
dict = {'b':'a','d':'c','f':'e'}
for item in strs:
    if item in {'a','c','e'}:
        l1.append(item)
    else:
        l2.append(dict[item])
def helper(lists):
    length = len(lists)
    dp = [[0,0,0]for i in range(length)]#表示到当前点,以a/c/e结尾的最长子串
    if lists[0]=='a':
        dp[0][0] = 1
    elif lists[0]=='c':
        dp[0][1] = 1
    else:
        dp[0][2] = 1
    index = 1
    for item in lists[1:]:
        if item == 'a':
            dp[index][0] = dp[index-1][0]+1#加一
            dp[index][1] = dp[index - 1][1]#不变
            dp[index][2] = dp[index - 1][2]#不变
        elif item == 'c':
            dp[index][0] = dp[index - 1][0] #表示不考虑该点
            dp[index][1] = max(dp[index-1][0],dp[index-1][1])+1
            dp[index][2] = dp[index - 1][2] #表示删除该点
        else:
            dp[index][0] = dp[index - 1][0]  # 表示删除该点
            dp[index][1] = dp[index - 1][1]# 表示删除该点
            dp[index][2] =max(dp[index-1])+1#不删除
        index+=1
    return  max(dp[length-1])
print(helper(l1)+helper(l2))

全部评论

(1) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐