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

zltzlt

今天的题目：

给定由字母 a 和 b 组成的字符串。在一次操作中，可以将一个字母替换成另一个字母（a 替换成 b 或 b 替换成 a）。

返回得到不包含连续三个相同字母的字符串所需的最少操作次数。

示例 1：

输入："baaaaa"
输出：1
解释：将字符串变成 "baabaa" 。

示例 2：

输入："baaabbaabbba"
输出：2
解释：将字符串变成 "bbaabbaabbaa" 。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

kinkon

2020-2-13 01:22:46

1. def fun330(s):
   
2.     a, c, t = 'a', 0, 0
   
3.     for i in s:
   
4.         if i == a:
   
5.             t += 1
   
6.             if t == 3:
   
7.                 c += 1
   
8.                 t = 0
   
9.         else:
   
10.             a, t = i, 1
    
11.     return c

复制代码

跳转到最佳答案楼层

一个账号

示例 2 应该输出 2，前面的 a 换成 b ，后面的 b 换成 a 。

fan1993423

建议楼主列举个稍微大点数据的例子，以方便自己做完以后检查正确与否，再提交答案

fan1993423

另外对于这种abba,没有3个连续数的情况，直接返回0吗？

yexing

示例2不是应该输出2嘛，前面的 a 换成 b ，后面的 b 换成 a 。

wanting-for

1. def solve_330(s: str):
   
2.     s = list(s)
   
3.     c_a, c_b, res, i = 0, 0, 0, 0
   
4.     while i<len(s):
   
5.         if s[i] == 'a':
   
6.             c_a += 1
   
7.             res += c_b//3
   
8.             c_b = 0
   
9.         elif s[i] == 'b':
   
10.             c_b += 1
    
11.             res += c_a//3
    
12.             c_a = 0
    
13.         i += 1
    
14.     res+=(c_b//3 + c_a//3)
    
15.     return res

复制代码

前排前排

zltzlt

fan1993423 发表于 2020-2-12 18:02
另外对于这种abba,没有3个连续数的情况，直接返回0吗？

是

zltzlt

yexing 发表于 2020-2-12 18:05
示例2不是应该输出2嘛，前面的 a 换成 b ，后面的 b 换成 a 。

搞错了，不好意思

zltzlt

一个账号 发表于 2020-2-12 17:51
示例 2 应该输出 2，前面的 a 换成 b ，后面的 b 换成 a 。

搞错了

fan1993423

1. from itertools import groupby
   
2. from bisect import bisect_left
   
3. def fun330(s):
   
4.     if not len(s):return 0
   
5.     t,result=[],0
   
6.     for k,v in groupby(s):t.append(len(list(v)))
   
7.     t_sort=sorted(t)
   
8.     if t_sort[-1]<3:return 0
   
9.     index=bisect_left(t_sort,3)
   
10.     for i in t_sort[index:]:result+=i//3
    
11.     return result

复制代码

zltzlt

wanting-for 发表于 2020-2-12 18:14
前排前排

807 ms

zltzlt

fan1993423 发表于 2020-2-12 18:33
简单写了个不知道效率

输入空字符串 "" 出错

fan1993423

zltzlt 发表于 2020-2-12 18:37
输入空字符串 "" 出错

还要考虑空字符串啊

fan1993423

空字符串返回0吗？

zltzlt

fan1993423 发表于 2020-2-12 18:40
空字符串返回0吗？

是

fan1993423

改了

zltzlt

fan1993423 发表于 2020-2-12 18:33

704 ms

fan1993423

zltzlt 发表于 2020-2-12 19:02
704 ms

嗯，可能用groupby慢了点速度，不过groupby更科学，如果这道题不是2个字母，而是26个字母都可以的话。就要多使用一次循环，速度会更慢

wanting-for

zltzlt 发表于 2020-2-12 18:37
807 ms

效率略低啊。。。暂时还没想出这个程序的改进方法，这个程序的时间复杂度，也就 n 啊

546623863

1. def fun330(s):
   
2.     if(len(s) == 0):
   
3.         return 0
   
4.     result = 0
   
5.     count = 1
   
6.     for index in range(1,len(s)):
   
7.         if(s[index] == s[index-1]):
   
8.             count += 1
   
9.             if(count >= 3):
   
10.                 if(s[index] == 'a'):
    
11.                     s[index] == 'b'
    
12.                 else:
    
13.                     s[index] == 'a'
    
14.                 count = 1
    
15.                 result += 1
    
16.         else:
    
17.             count = 1
    
18.     return result

复制代码