Python:每日一题 382
今天的题目:找到给定字符串(由小写字符组成)中的最长子串 t ,要求 t 中的每一字符出现次数都不少于 k 。返回 t 的长度。
示例 1:
输入:s = "aaabb", k = 3
输出:3
解释:最长子串为 "aaa" ,其中 'a' 重复了 3 次。
示例 2:
输入:s = "ababbc", k = 2
输出:5
解释:最长子串为 "ababb" ,其中 'a' 重复了 2 次, 'b' 重复了 3 次。
{:10_298:}欢迎大家一起答题!{:10_298:} zhanlou 本帖最后由 TJBEST 于 2020-4-23 10:35 编辑
就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 = ]]
for index in range(0,number-1):
StringLst.append(s[(position+1):(position)])
StringLst.append(s[(position[-1]+1):])
return max()
else:
return len(s) def f(s,k):
n = 0
for each in s:
if s.count(each) >= k:
n += 1
return n 本帖最后由 ouyunfu 于 2020-4-22 21:49 编辑
from collections import Counter
def f382(s,k):
L=[]
for i in range(len(s)-k):
t=s
Flag=1
while Flag:
a=(Counter(t))
if min( 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 于 2020-4-23 15:34 编辑
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) 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
else :
r += '|' + l
s = re.split(r,s)
return max() 本帖最后由 March2615 于 2020-4-23 10:01 编辑
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 于 2020-4-22 21:39 编辑
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
wordsdict = [] #储存字符数
for i in range(26):
wordsdict.append(0)
for w in sub: #统计字符数
wordsdict += 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 #返回 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 于 2020-4-22 21:45 编辑
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)) bddcbefb 这种bbb是不是子串 {:5_106:} 本帖最后由 Python3005 于 2020-4-22 22:36 编辑
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) def func382(s,k):
c=[]
d=*26
j=0
l=0
re=0
while j<len(s):
for i in range(j,len(s)):
c.append(s)
d)-97]=c.count(s)
for i in range(0,26):
if(d!=0):
if(d<k):
continue
else:
re+=d
if(l<re):
l=re
re=0
c.clear()
d=*26
j+=1
return l 本帖最后由 lucky邪神 于 2020-4-22 22:51 编辑
笨办法,初步想到这么,工作忙完在来想想def func382(s,k):
splitlist=[]
resultlist=
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=
return t
t = input("请输入: ")
n = {i:0 for i in t}
for i in t:
for m in n.keys():
if i == m:
n += 1
s = max(n,key = n.get)
print("最长字符串为%s,其中%s重复了%d次"%(s,s,n)) 我只负责写bug,找bug就交给我们亲爱的版主了{:10_332:}{:10_332:}
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 def f382(s, k):
a = set(s)
counter = 0
for i in a:
if s.count(i) >= k:
counter += s.count(i)
return counter 为什么楼主出题后,你们就马上有答案了。而我还理不清思路呢???
差距不是一般的小呀………………