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

_2_

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

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

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

March2615

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

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

xiangjianshinan

'''
今天的题目：
找到给定字符串（由小写字符组成）中的最长子串 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

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

有点像 二分法？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

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

这样啊

findland

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

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

33 ms

zltzlt

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

解答错误

输入：

s = 'ababacb', k = 3

输出：6
预期结果：0

子串一定要是连续的

zltzlt

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

当 s 为空时出错

zltzlt

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

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

zltzlt

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

解答错误

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

kinkon

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

收到，第二个反而慢了啊

zltzlt

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

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

zltzlt

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

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

s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
t = 1

March2615

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

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

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

zltzlt

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

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

zltzlt

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

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