xiangjianshinan 发表于 2020-4-23 08:36
为什么楼主出题后，你们就马上有答案了。而我还理不清思路呢？？？
差距不是一般的小呀………………
然后就是 @zltzlt 回的一堆「解答错误」，
这点我深有感触{:10_266:}
fan1993423 发表于 2020-4-22 22:12
bddcbefb 这种bbb是不是子串
子串和子序列是不同的
子串要求是原字符串中一块连续的字符串
子序列只要求从原字符串中按原顺序取出字符组成的即可
本帖最后由 xiangjianshinan 于 2020-4-26 14:12 编辑
'''
今天的题目：
找到给定字符串（由小写字符组成）中的最长子串 t ，要求 t 中的每一字符出现次数都不少于 k 。返回 t 的长度。
示例 1：
输入：s = "aaabb", k = 3
输出：3
解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。
示例 2：
输入：s = "ababbc", k = 2
输出：5
解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。
解题思路：
1、解题意得，需要截取s字符串中的一段连续的子串t。而子串t中的每一个字符出现次数不能少于k次.
2、想到的办法是通过集合来提取s字符串中的每个不重复的元素。
3、计算每个元素的数量，当数量大于等于k时，提取该元素。
4、通过提取的元素进行re模块的操作。
过程如下：
'''
import re
s = "aaabb"
k = 3
def timu382(s,k):
if len(s)==0:
return '没有匹配的信息。' #当S为空时出错的修改20200424 14:58
seta = set(s)# 1、2
research = '['
researcha = ''
for i in seta:
if s.count(i) >= k:
researcha = researcha + i
if researcha.strip() == '': #s = "weitong" k = 2 处理s字符不符合k条件的情况20200426 0822
return '没有匹配的信息。'
research = research + researcha +']{' + str(k) + ",}"
print("research",research)
temps = re.search(research, s).group()
if temps == None:
return '没有匹配的信息。'
else:
print(temps)
for i in researcha: #输入 s = 'ababacb', k = 3 结果有误 2020042614:09
if temps.count(i)<k:
return '没有匹配的信息。'
return len(temps)
print(timu382(s,k))
print(timu382("ababbc",2))
s = "weitong"
k = 2
print(timu382(s,k))
s = 'ababacb'
k = 3
print(timu382(s,k))
print('done!')
楼主：回复的
当 s 为空字符串时出错
已修改~~~
=======================================
修改 当s = "weitong" k = 2 时，不能处理的情况。20200426 0822
大佬辛苦啦！！！
=======================================
#输入 s = 'ababacb', k = 3 结果有误 2020042614:09
def P382(s,k):
n = len(s)
limit = len(s)
op = 0
while limit >= k-1:
for i in range(n-limit):
t = s
set1 = set(t)
for each in set1:
if t.count(each) < k:
break
else:
op = 1
break
if op == 1:
break
limit -= 1
if op == 1:
return len(t)
else:
return 0
s = input()
k = int(input())
print(P382(s,k))
萌新请大佬赐教
有点像 二分法？2333
def max_sub_str(sub_string, k):
length = len(sub_string)
if length < k:
return 0
for each in sub_string:
if sub_string.count(each) < k:
new_head = sub_string.find(each)
return max(max_sub_str(sub_string[:new_head], k), max_sub_str(sub_string,k))
else:
return length
March2615 发表于 2020-4-23 10:04
子串和子序列是不同的
子串要求是原字符串中一块连续的字符串
子序列只要求从原字符串中按原顺序取出字 ...
这样啊
def f382(s, k):
char_list = set(s)
res = 0
for i in char_list:
if s.count(i) >= k:
res += s.count(i)
return res
if __name__ == "__main__":
s = 'ababbc'
k = 2
print(f382(s, k))
s = "aaabb"
k = 3
print(f382(s, k))
TJBEST 发表于 2020-4-22 20:15
就26个字母所以递归深度最大不超过30，超不超时不知道，但是正确性我觉得没问题
33 ms
风魔孤行者 发表于 2020-4-22 20:17
解答错误
输入：s = 'ababacb', k = 3
输出：6
预期结果：0
子串一定要是连续的
ouyunfu 发表于 2020-4-22 20:29
当 s 为空时出错
kinkon 发表于 2020-4-22 20:31
优化递归深度1
用时分别是 33 ms、72 ms、27 ms
NAMELESSONE 发表于 2020-4-22 20:37
解答错误
输入：s = 'aaabbb', t = 3
输出：1
预期结果：6
zltzlt 发表于 2020-4-23 18:50
用时分别是 33 ms、72 ms、27 ms
收到，第二个反而慢了啊
March2615 发表于 2020-4-22 21:35
第一段代码超时，第二段代码 20 ms
liuzhengyuan 发表于 2020-4-22 21:06
输入以下数据超出时间限制：
s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
t = 1
zltzlt 发表于 2020-4-23 18:55
第一段代码超时，第二段代码 20 ms
果然还是需要优化的
希望能多一点示例，这样测试起来也比较容易找漏
zltzlt 发表于 2020-4-23 18:36
解答错误
输入：
def f(s,k):
list1 = []
a = 0
while a < len(s):
if s.count(s)<k:
a += 1
else:
b = a+1
while b<len(s) and s.count(s)>=k:
b +=1
list1.append(s)
a = b
list1.sort(key=lambda x:len(x), reverse=True)
for each in list1:
list2 = set(each)
judge = True
for n in list2:
if each.count(n)<k:
judge = False
if judge:
return len(each)
return 0
whosyourdaddy 发表于 2020-4-22 21:31
def func382(s,k):
temp = set(s)
l = []
输入 s = "aaabbb", k = 3 时结果有误
Python3005 发表于 2020-4-22 22:28
输入 s = "aaabbb", k = 3 时出错
Joy187 发表于 2020-4-22 22:37
def func382(s,k):
c=[]
d=*26
输入 s = "ababacb", k = 3 时结果有误