zltzlt 发表于 2020-4-22 20:10:07

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:}

永恒的蓝色梦想 发表于 2020-4-22 20:12:24

zhanlou

TJBEST 发表于 2020-4-22 20:15:00

本帖最后由 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)

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

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

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

本帖最后由 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-22 20:31:47

本帖最后由 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)

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

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-22 20:55:54

本帖最后由 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:06:19

本帖最后由 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 #返回

whosyourdaddy 发表于 2020-4-22 21:31:22

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:35:23

本帖最后由 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))

fan1993423 发表于 2020-4-22 22:12:59

bddcbefb 这种bbb是不是子串

pythonczk 发表于 2020-4-22 22:24:20

{:5_106:}

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

本帖最后由 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)

Joy187 发表于 2020-4-22 22:37:10

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:41:31

本帖最后由 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
            

dengyk 发表于 2020-4-23 00:02:15

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

斐波纳税 发表于 2020-4-23 00:09:50

我只负责写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

kkk999de 发表于 2020-4-23 08:32:01

def f382(s, k):
    a = set(s)
    counter = 0
    for i in a:
      if s.count(i) >= k:
            counter += s.count(i)
    return counter

xiangjianshinan 发表于 2020-4-23 08:36:05

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

差距不是一般的小呀………………
页: [1] 2 3 4
查看完整版本: Python:每日一题 382