[已解决]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

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

复制代码

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

复制代码

跳转到最佳答案楼层

永恒的蓝色梦想

zhanlou

TJBEST

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

1. def fun382(s,k):
   
2.     if s == '':
   
3.         return 0
   
4.     stringSet = set(s)
   
5.     for eachChar in stringSet:
   
6.         number = s.count(eachChar)
   
7.         if number < k:
   
8.             position = []
   
9.             temp = 0
   
10.             for index in range(0,number):
    
11.                 temp = s.index(eachChar,temp)
    
12.                 position.append(temp)
    
13.                 temp += 1
    
14.             StringLst = [s[:position[0]]]
    
15.             for index in range(0,number-1):
    
16.                 StringLst.append(s[(position[index]+1):(position[index+1])])
    
17.             StringLst.append(s[(position[-1]+1):])
    
18.             return max([fun382(eachStr,k) for eachStr in StringLst])
    
19.     else:
    
20.         return len(s)

复制代码

风魔孤行者

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

复制代码

ouyunfu

1. from collections import Counter
   
2. def f382(s,k):
   
3.     L=[]
   
4.     for i in range(len(s)-k):
   
5.         t=s[i:]
   
6.         Flag=1
   
7.         while Flag:
   
8.             a=(Counter(t))
   
9.             if min([i[1] for i in a.items()])>=k:
   
10.                 L.append(len(t))
    
11.                 Flag=0
    
12.             else:t=t[:-1]
    
13.             if len(t)<k:
    
14.                 Flag=0
    
15.     return max(L)

复制代码

kinkon

1. from collections import Counter
   
2. 
   
3. def f382(s, k):   
   
4.     for val, c in Counter(s).items():
   
5.         if c < k:
   
6.             return max(f382(v, k) for v in s.split(val))
   
7.     return len(s)

复制代码

优化递归深度1

1. def f382(s, k):
   
2.     mlen = 0
   
3.     for val, c in Counter(s).items():
   
4.         if c < k:           
   
5.             for i in s.split(val):               
   
6.                 if len(i) >= k:
   
7.                     mlen = max(f382(i, k), mlen)
   
8.             return mlen
   
9.     return len(s)

复制代码

优化递归深度2

1. def f382(s, k):
   
2.     mlen = 0
   
3.     for c in set(s):
   
4.         if s.count(c) < k:
   
5.             for i in s.split(c):               
   
6.                 if len(i) >= k:
   
7.                     mlen = max(f382(i, k), mlen)
   
8.             return mlen
   
9.     return len(s)

复制代码

NAMELESSONE

1. def solve(s,k):
   
2.     string = set(s)
   
3.     l = []
   
4.     r = ''
   
5.     for i in string:
   
6.         if s.count(i) < k:
   
7.             l.append(i)
   
8.     for i in range(len(l)):
   
9.         if i == 0 :
   
10.             r += l[i]
    
11.         else :
    
12.             r += '|' + l[i]
    
13.     s = re.split(r,s)
    
14.     return max([len(i) for i in s])

复制代码

March2615

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

复制代码

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

liuzhengyuan

1. def m382(s, k):
   
2.         fin_ans = 0
   
3.         for wlen in range(k, len(s) + 1): #一个个枚举，wlen 是子串的长度
   
4.                 for pos in range(len(s) - (wlen - 1)): #规矩子串的位置
   
5.                         sub = s[pos:pos + wlen]
   
6.                        
   
7.                         wordsdict = [] #储存字符数
   
8.                         for i in range(26):
   
9.                                 wordsdict.append(0)
   
10.                         for w in sub: #统计字符数
    
11.                                 wordsdict[ord(w) - 97] += 1 #统计
    
12.                                
    
13.                         panb = True
    
14.                         for num in wordsdict: #判断是否符合
    
15.                                 if num < k and num != 0:
    
16.                                         panb = False #bool 类型
    
17. 
    
18.                         if panb == True:
    
19.                                 fin_ans = len(sub) #赋值
    
20.         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

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

复制代码

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

复制代码

fan1993423

bddcbefb 这种bbb是不是子串

pythonczk

Python3005

1. def fun(s : str, k : int) -> int:
   
2.         target = []
   
3.         for each in s:
   
4.                 if s.count(each) < k:
   
5.                         target.append(each)
   
6.         result = []
   
7.         count = 0
   
8.         for each in s:
   
9.                 if each not in target:
   
10.                         count += 1
    
11.                 else:
    
12.                         result.append(count)
    
13.                         count = 0
    
14.         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邪神

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

1. def func382(s,k):
   
2.     splitlist=[]
   
3.     resultlist=[s]
   
4.     newresultlist=[]
   
5.     t=0
   
6.     for each1 in s:
   
7.         if s.count(each1)< k and each1 not in splitlist:
   
8.             splitlist.append(each1)
   
9.     print(splitlist)
   
10.    
    
11.     for each2 in splitlist:
    
12.         for string in resultlist:
    
13.             newresultlist=string.split(each2)
    
14.         resultlist=newresultlist
    
15.     print(resultlist)
    
16.     for each3 in resultlist:
    
17.         t=[len(each3),t][t>len(each3)]
    
18.     return t
    
19.             

复制代码

dengyk

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

复制代码

斐波纳税

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

1. def f382(s, k):
   
2.     for each_one in s:
   
3.         if each_one == '0':
   
4.             continue
   
5.         if s.count(each_one) < k:
   
6.             s = s.replace(each_one, '0')
   
7. 
   
8.     count = max = 0
   
9.     for each_one in s:
   
10.         if each_one == '0':
    
11.             max = count if count > max else max
    
12.             count = 0
    
13.         else:
    
14.             count += 1
    
15.     return max if max > count else count

复制代码

kkk999de

1. def f382(s, k):
   
2.     a = set(s)
   
3.     counter = 0
   
4.     for i in a:
   
5.         if s.count(i) >= k:
   
6.             counter += s.count(i)
   
7.     return counter

复制代码

xiangjianshinan

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

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