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

March2615

1. def daily382(s: str, k: int) -> int:
   
2.     # 解题思路：
   
3.     # 最长字串 -> 字符串要连续且要求最长(连续很重要)
   
4.     # 遍历字符串s，如果字符ch的数量小于k，则证明t中没有这个字符
   
5.     # -> 将s以ch为界分割，选取最长的一段进行重复操作
   
6.     # 将分割后的列表按字符串长度进行排序
   
7.     # 如果len(s) < k -> 必不可能存在满足题意的t -> return 0
   
8.     if len(s) < k:
   
9.         return 0
   
10.     for each in s:
    
11.         if s.count(each) < k:
    
12.             t = sorted(s.split(each), key=lambda x: len(x))[-1]
    
13.             return daily382(t, k)
    
14.     return len(s)

复制代码

仔细想了想，选取最长一段进行递归有点不严谨
解答是有误的，修改后的写在下面了

March2615

1. def daily382(s: str, k: int) -> int:
   
2.     # 解题思路：
   
3.     # 最长字串 -> 字符串要连续且要求最长
   
4.     # 遍历字符串s，如果字符ch的数量小于k，则证明字串中没有这个字符
   
5.     # -> 将s以ch为界分割，对所有分割得到的字符串进行递归操作取最大值
   
6.     # 如果len(s) < k -> 必不可能存在满足题意的t -> return 0
   
7.     if len(s) < k:  # 结束递归的条件
   
8.         return 0
   
9.     for each in s:
   
10.         if s.count(each) < k:
    
11.             return max(daily382(new_s, k) for new_s in s.split(each))
    
12.     return len(s)

复制代码

1. def daily382_1(s: str, k: int) -> int:
   
2.     # 改进思路：不需要通过遍历判断ch是否在t中
   
3.     # 每次找s中出现次数最少的字符，如果小于k，则必不在t中
   
4.     # 仍然分割字符串并进行递归操作取最大值
   
5.     # 反之，若出现次数最少的字符都满足大于k，则此时的长度就是要求的长度
   
6.     if len(s) < k:  # 结束递归的条件
   
7.         return 0
   
8.     min_ch = min(set(s), key=s.count)
   
9.     if s.count(min_ch) >= k:
   
10.         return len(s)
    
11.     return max(daily382_1(new_s, k) for new_s in s.split(min_ch))

复制代码

March2615

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

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

March2615

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

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