[已解决]Python：每日一题 382

zltzlt

今天的题目：

找到给定字符串（由小写字符组成）中的最长子串 t ，要求 t 中的每一字符出现次数都不少于 k 。返回 t 的长度。

示例 1：

输入：s = "aaabb", k = 3
输出：3
解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。

示例 2：

输入：s = "ababbc", k = 2
输出：5
解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

March2615

2020-4-22 21:35:23

def daily382(s: str, k: int) -> int:
    # 解题思路：
    # 最长字串 -> 字符串要连续且要求最长
    # 遍历字符串s，如果字符ch的数量小于k，则证明字串中没有这个字符
    # -> 将s以ch为界分割，对所有分割得到的字符串进行递归操作取最大值
    # 如果len(s) < k -> 必不可能存在满足题意的t -> return 0
    if len(s) < k:  # 结束递归的条件
        return 0
    for each in s:
        if s.count(each) < k:
            return max(daily382(new_s, k) for new_s in s.split(each))
    return len(s)

def daily382_1(s: str, k: int) -> int:
    # 改进思路：不需要通过遍历判断ch是否在t中
    # 每次找s中出现次数最少的字符，如果小于k，则必不在t中
    # 仍然分割字符串并进行递归操作取最大值
    # 反之，若出现次数最少的字符都满足大于k，则此时的长度就是要求的长度
    if len(s) < k:  # 结束递归的条件
        return 0
    min_ch = min(set(s), key=s.count)
    if s.count(min_ch) >= k:
        return len(s)
    return max(daily382_1(new_s, k) for new_s in s.split(min_ch))

跳转到最佳答案楼层

永恒的蓝色梦想

zhanlou

TJBEST

就26个字母所以递归深度最大不超过30，超不超时不知道，但是正确性我觉得没问题

def fun382(s,k):
    if s == '':
        return 0
    stringSet = set(s)
    for eachChar in stringSet:
        number = s.count(eachChar)
        if number < k:
            position = []
            temp = 0
            for index in range(0,number):
                temp = s.index(eachChar,temp)
                position.append(temp)
                temp += 1
            StringLst = [s[:position[0]]]
            for index in range(0,number-1):
                StringLst.append(s[(position[index]+1):(position[index+1])])
            StringLst.append(s[(position[-1]+1):])
            return max([fun382(eachStr,k) for eachStr in StringLst])
    else:
        return len(s)

风魔孤行者

def f(s,k):
    n = 0
    for each in s:
        if s.count(each) >= k:
            n += 1
    return n

ouyunfu

from collections import Counter
def f382(s,k):
    L=[]
    for i in range(len(s)-k):
        t=s[i:]
        Flag=1
        while Flag:
            a=(Counter(t))
            if min([i[1] for i in a.items()])>=k:
                L.append(len(t))
                Flag=0
            else:t=t[:-1]
            if len(t)<k:
                Flag=0
    return max(L)

kinkon

from collections import Counter

def f382(s, k):    
    for val, c in Counter(s).items():
        if c < k:
            return max(f382(v, k) for v in s.split(val))
    return len(s)

优化递归深度1

def f382(s, k):
    mlen = 0
    for val, c in Counter(s).items():
        if c < k:           
            for i in s.split(val):                
                if len(i) >= k:
                    mlen = max(f382(i, k), mlen)
            return mlen
    return len(s)

优化递归深度2

def f382(s, k):
    mlen = 0
    for c in set(s):
        if s.count(c) < k:
            for i in s.split(c):                
                if len(i) >= k:
                    mlen = max(f382(i, k), mlen)
            return mlen
    return len(s)

NAMELESSONE

def solve(s,k):
    string = set(s)
    l = []
    r = ''
    for i in string:
        if s.count(i) < k:
            l.append(i)
    for i in range(len(l)):
        if i == 0 :
            r += l[i]
        else :
            r += '|' + l[i]
    s = re.split(r,s)
    return max([len(i) for i in s])

March2615

def daily382(s: str, k: int) -> int:
    # 解题思路：
    # 最长字串 -> 字符串要连续且要求最长(连续很重要)
    # 遍历字符串s，如果字符ch的数量小于k，则证明t中没有这个字符
    # -> 将s以ch为界分割，选取最长的一段进行重复操作
    # 将分割后的列表按字符串长度进行排序
    # 如果len(s) < k -> 必不可能存在满足题意的t -> return 0
    if len(s) < k:
        return 0
    for each in s:
        if s.count(each) < k:
            t = sorted(s.split(each), key=lambda x: len(x))[-1]
            return daily382(t, k)
    return len(s)

仔细想了想，选取最长一段进行递归有点不严谨
解答是有误的，修改后的写在下面了

liuzhengyuan

def m382(s, k):
        fin_ans = 0
        for wlen in range(k, len(s) + 1): #一个个枚举，wlen 是子串的长度
                for pos in range(len(s) - (wlen - 1)): #规矩子串的位置
                        sub = s[pos:pos + wlen]
                        
                        wordsdict = [] #储存字符数
                        for i in range(26):
                                wordsdict.append(0)
                        for w in sub: #统计字符数
                                wordsdict[ord(w) - 97] += 1 #统计
                                
                        panb = True
                        for num in wordsdict: #判断是否符合
                                if num < k and num != 0:
                                        panb = False #bool 类型

                        if panb == True:
                                fin_ans = len(sub) #赋值
        return fin_ans #返回

whosyourdaddy

def func382(s,k):
    temp = set(s)
    l = []
    for i in temp:
        if s.count(i) < k:
            l.append(i)
    for i in l:
        s = s.split(i)
    return max(len(i) for i in s)

March2615

def daily382(s: str, k: int) -> int:
    # 解题思路：
    # 最长字串 -> 字符串要连续且要求最长
    # 遍历字符串s，如果字符ch的数量小于k，则证明字串中没有这个字符
    # -> 将s以ch为界分割，对所有分割得到的字符串进行递归操作取最大值
    # 如果len(s) < k -> 必不可能存在满足题意的t -> return 0
    if len(s) < k:  # 结束递归的条件
        return 0
    for each in s:
        if s.count(each) < k:
            return max(daily382(new_s, k) for new_s in s.split(each))
    return len(s)

def daily382_1(s: str, k: int) -> int:
    # 改进思路：不需要通过遍历判断ch是否在t中
    # 每次找s中出现次数最少的字符，如果小于k，则必不在t中
    # 仍然分割字符串并进行递归操作取最大值
    # 反之，若出现次数最少的字符都满足大于k，则此时的长度就是要求的长度
    if len(s) < k:  # 结束递归的条件
        return 0
    min_ch = min(set(s), key=s.count)
    if s.count(min_ch) >= k:
        return len(s)
    return max(daily382_1(new_s, k) for new_s in s.split(min_ch))

fan1993423

bddcbefb 这种bbb是不是子串

pythonczk

Python3005

def fun(s : str, k : int) -> int:
        target = []
        for each in s:
                if s.count(each) < k:
                        target.append(each)
        result = []
        count = 0
        for each in s:
                if each not in target:
                        count += 1
                else:
                        result.append(count)
                        count = 0
        return max(result)

Joy187

def func382(s,k):
    c=[]
    d=[0]*26
    j=0
    l=0
    re=0
    while j<len(s):
        for i in range(j,len(s)):
                c.append(s[i])
                d[ord(s[i])-97]=c.count(s[i])
        for i in range(0,26):
            if(d[i]!=0):
                if(d[i]<k):
                    continue
                else:
                    re+=d[i]
                    if(l<re):
                        l=re
        re=0
        c.clear()
        d=[0]*26
        j+=1
    return l

lucky邪神

笨办法，初步想到这么，工作忙完在来想想

def func382(s,k):
    splitlist=[]
    resultlist=[s]
    newresultlist=[]
    t=0
    for each1 in s:
        if s.count(each1)< k and each1 not in splitlist:
            splitlist.append(each1)
    print(splitlist)
    
    for each2 in splitlist:
        for string in resultlist:
            newresultlist=string.split(each2)
        resultlist=newresultlist
    print(resultlist)
    for each3 in resultlist:
        t=[len(each3),t][t>len(each3)]
    return t
            

dengyk

t = input("请输入: ")
n = {i:0 for i in t}
for i in t:
    for m in n.keys():
        if i == m:
            n[m] += 1
s = max(n,key = n.get)
print("最长字符串为%s,其中%s重复了%d次"%(s,s,n[s]))

斐波纳税

我只负责写bug，找bug就交给我们亲爱的版主了

def f382(s, k):
    for each_one in s:
        if each_one == '0':
            continue
        if s.count(each_one) < k:
            s = s.replace(each_one, '0')

    count = max = 0
    for each_one in s:
        if each_one == '0':
            max = count if count > max else max
            count = 0
        else:
            count += 1
    return max if max > count else count

kkk999de

def f382(s, k):
    a = set(s)
    counter = 0
    for i in a:
        if s.count(i) >= k:
            counter += s.count(i)
    return counter

xiangjianshinan

为什么楼主出题后，你们就马上有答案了。而我还理不清思路呢？？？

差距不是一般的小呀………………