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

_2_ · 发表于 2020-4-23 08:53:11

xiangjianshinan 发表于 2020-4-23 08:36
为什么楼主出题后，你们就马上有答案了。而我还理不清思路呢？？？

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

然后就是 @zltzlt 回的一堆「解答错误」，
这点我深有感触

March2615 · 发表于 2020-4-23 10:04:38

fan1993423 发表于 2020-4-22 22:12
bddcbefb 这种bbb是不是子串

子串和子序列是不同的
子串要求是原字符串中一块连续的字符串
子序列只要求从原字符串中按原顺序取出字符组成的即可

xiangjianshinan · 发表于 2020-4-23 10:53:04

本帖最后由 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 结果有误 20200426 14: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 结果有误 20200426 14:09

Frozen83 · 发表于 2020-4-23 12:29:20

def P382(s,k):
n = len(s)
limit = len(s)
op = 0
while limit >= k-1:
for i in range(n-limit):
t = s[i:limit+i+1]
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))

复制代码

萌新请大佬赐教

旅途Z · 发表于 2020-4-23 13:23:27

有点像二分法？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[new_head+1:],k))
else:
return length

复制代码

fan1993423 · 发表于 2020-4-23 14:18:35

March2615 发表于 2020-4-23 10:04
子串和子序列是不同的
子串要求是原字符串中一块连续的字符串
子序列只要求从原字符串中按原顺序取出字 ...

这样啊

findland · 发表于 2020-4-23 15:04:48

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))

复制代码

zltzlt · 发表于 2020-4-23 18:34:18

TJBEST 发表于 2020-4-22 20:15
就26个字母所以递归深度最大不超过30，超不超时不知道，但是正确性我觉得没问题

33 ms

zltzlt · 发表于 2020-4-23 18:36:12

风魔孤行者发表于 2020-4-22 20:17

解答错误

输入：

s = 'ababacb', k = 3

复制代码

输出：6
预期结果：0

子串一定要是连续的

zltzlt · 发表于 2020-4-23 18:37:17

ouyunfu 发表于 2020-4-22 20:29

当 s 为空时出错

zltzlt · 发表于 2020-4-23 18:50:08

kinkon 发表于 2020-4-22 20:31
优化递归深度1

用时分别是 33 ms、72 ms、27 ms

zltzlt · 发表于 2020-4-23 18:50:55

NAMELESSONE 发表于 2020-4-22 20:37

解答错误

输入：s = 'aaabbb', t = 3
输出：1
预期结果：6

kinkon · 发表于 2020-4-23 18:52:38

zltzlt 发表于 2020-4-23 18:50
用时分别是 33 ms、72 ms、27 ms

收到，第二个反而慢了啊

zltzlt · 发表于 2020-4-23 18:55:58

March2615 发表于 2020-4-22 21:35

第一段代码超时，第二段代码 20 ms

zltzlt · 发表于 2020-4-23 18:57:01

liuzhengyuan 发表于 2020-4-22 21:06

输入以下数据超出时间限制：

s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
t = 1

复制代码

March2615 · 发表于 2020-4-23 20:21:41

zltzlt 发表于 2020-4-23 18:55
第一段代码超时，第二段代码 20 ms

果然还是需要优化的
希望能多一点示例，这样测试起来也比较容易找漏

风魔孤行者 · 发表于 2020-4-23 22:17:53

zltzlt 发表于 2020-4-23 18:36
解答错误

输入：

def f(s,k):
list1 = []
a = 0
while a < len(s):
if s.count(s[a])<k:
a += 1
else:
b = a+1
while b<len(s) and s.count(s[b])>=k:
b +=1
list1.append(s[a:b])
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

复制代码

zltzlt · 发表于 2020-4-24 13:26:13

whosyourdaddy 发表于 2020-4-22 21:31
def func382(s,k):
temp = set(s)
l = []

输入 s = "aaabbb", k = 3 时结果有误

zltzlt · 发表于 2020-4-24 13:27:02

Python3005 发表于 2020-4-22 22:28

输入 s = "aaabbb", k = 3 时出错

zltzlt · 发表于 2020-4-24 13:28:10

Joy187 发表于 2020-4-22 22:37
def func382(s,k):
c=[]
d=[0]*26

输入 s = "ababacb", k = 3 时结果有误

账号		自动登录	找回密码
密码			立即注册

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

评分

评分

评分

评分

评分