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

zltzlt

今天的题目：

给定一个只包含大写字母 A 和 B 的字符串。删除最少的字符使得字符串变成 A...AB...B 的形式。

返回需要删除的最少字符数。

示例 1：

输入："BAAABAB"
输出：2
解释：删除第一个 B 和最后一个 A，构成 "AAABB"。

示例 2：

输入："BBABAA"
输出：3
解释：可以删除所有的 A 或 B。

示例 3：

输入："AABBBB"
输出：0
解释：不需要删除任何字符，因为字符串本身符合条件。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

wanting-for

2020-2-13 20:29:53

1. def solve_311(s: str):
   
2.     a_c, b_c, len_s, count = s.count('A'), s.count('B'), len(s), float('inf')
   
3.     a_cc, b_cc, i = 0, 0, 0
   
4.     i = 0
   
5.     while i < len_s - 1:
   
6.         if s[i] == 'A' and s[i+1] == 'B':
   
7.             now = a_c - a_cc - 1
   
8.             if now + b_cc < count:
   
9.                 count = now + b_cc
   
10.             i += 2
    
11.             a_cc += 1
    
12.             b_cc += 1
    
13.         elif s[i] == 'B':
    
14.             b_cc += 1
    
15.             i += 1
    
16.         elif s[i] == 'A':
    
17.             a_cc += 1
    
18.             i += 1
    
19.     return min(a_c,b_c,count)
    
20. print(solve_311("AABBBB"))

复制代码

看似简便，就是不知道效率怎们样，
这道题感觉方法还是比较明确的

跳转到最佳答案楼层

TJBEST

也就是 AAA 或 BBB也算？

塔利班

1. def f331(x):
   
2.     m,sa,sb,ta=len(x),0,0,x.count('A')
   
3.     for e in x:
   
4.         if e=='A':
   
5.             sa+=1
   
6.         if e=='B':
   
7.             sb+=1
   
8.         m=min(sb+ta-sa,m)
   
9.     return m

复制代码

TJBEST

zltzlt 发表于 2020-2-13 18:09
不算，而且字符串一定既包含 A 也包含 B

BBABAA 为什么是3？ 最少4个吧？

zltzlt

塔利班 发表于 2020-2-13 18:09

解答错误

输入：

1. "BBABABBBABABABBBABABABAABBBBABAABBBBABABBBBABBAABBBABBBBABBABAAABBBABAABAAAAAABABAABABBAABBBABBABAAAAAABBBBAAAAAAABBBBAABAABAABABABAABBAAABBAABBBBABBBBAAAABABBBBBBABBBBBAABAAAAAABABABBAABBABBABAABABABABABABBAAABBBBBBBBABBABABBABBBBBBBABBBBAABBBAABBAABBABAAABABBAAAAAAAABBAAABAAABBAAABBABBBAAABBBBBABABBABBBBBABBBBBAAAAAABBAABABAAABABBAAAABBBBBAAAAAABBAAABAABAABBABBBBAABABBAABAAAAAAAAABAABBBBABBBBBAABABABBBABBAABBBAAAABABABBBABAABBBBABAABABAAABBABBBBBABBBBBABBBAABABBAABBBBAABABAABBBAABABBBAAAABAAAABBBAAABAABAABAAAAAAABBBABABBBBABBABBBBABAABABBABABBBABBABBAAAABAABBBBABAABABBBABBBAABBBBBBBBBABAAAABAAAAAABABAABAABBAABAAAAAABBBBBBAABBBBBAAAAAAAABBAAAABAAABBAABAABAABAAAABAAAAABABBAABAABAABAAAABABABABBAABBBAABAAABBABABAAABBBBBABBBAABBBABBBABBBABABBBBBAAAABAABBBBBAABABBAABBABBABBBABBBABBBBABAABBAAAAABBAAAABABBABBBBBAABBBBBAABBBBBABBBABBBBABABAAABBABABAAAAAABABAABBABBABABAABBBBABABBAAAABBBABABBBBABBBAAABAAAAABAAABBABBBBAAAABBBBABBBBBBAABABBBBAABBABAABBAABBBABAAAABABBBAAAABAABABBABBBBBAABBBBABBBAA"

复制代码

输出：476
预期结果：475

zltzlt

TJBEST 发表于 2020-2-13 18:10
BBABAA 为什么是3？ 最少4个吧？

自相矛盾了……

刚刚说错了，AAA 或 BBB 也算

TJBEST

zltzlt 发表于 2020-2-13 18:12
自相矛盾了……

刚刚说错了，AAA 或 BBB 也算

好的 也就是 只剩A或者只剩B也算 对吧

zltzlt

TJBEST 发表于 2020-2-13 18:15
好的 也就是 只剩A或者只剩B也算 对吧

对

塔利班

zltzlt 发表于 2020-2-13 18:10
解答错误

输入：

1. def f331(x):
   
2.     m,sa,sb,ta=len(x),0,0,x.count('A')
   
3.     for e in 'C'+x:
   
4.         if e=='A':
   
5.             sa+=1
   
6.         elif e=='B':
   
7.             sb+=1
   
8.         m=min(sb+ta-sa,m)
   
9.     return m

复制代码

zltzlt

塔利班 发表于 2020-2-13 18:29

703 ms

TJBEST

塔利班的方法真的妙，我的方法真的相形见绌了，不过不能抄袭

1. def fun331(string):
   
2.     M = len(string)
   
3.     try:
   
4.         firstCharcter = string[0]
   
5.     except Exception:
   
6.         return 0
   
7.     A_List = []
   
8.     B_List = []
   
9.    
   
10.     temp = firstCharcter
    
11.     count = 1
    
12.     for i in range(1,M):
    
13.         if string[i] == temp:
    
14.             count += 1
    
15.         else:
    
16.             if temp == 'A':
    
17.                 A_List.append(count)
    
18.             else:
    
19.                 B_List.append(count)
    
20.             temp = string[i]
    
21.             count = 1
    
22.     if temp == 'A':
    
23.         A_List.append(count)
    
24.     else:
    
25.         B_List.append(count)
    
26.    
    
27.     possible = []
    
28.     possible.append(min(sum(A_List),sum(B_List)))
    
29.    
    
30.    
    
31.     if len(A_List) > len(B_List):
    
32.         constRes = A_List.pop()
    
33.     elif len(A_List) < len(B_List):
    
34.         constRes = B_List[0]
    
35.         B_List = B_List[1:]
    
36.     else:
    
37.         if firstCharcter == 'A':
    
38.             constRes = 0
    
39.         else:
    
40.             constRes = A_List.pop() + B_List[0]
    
41.             B_List = B_List[1:]
    
42.    
    
43.     index = 0
    
44.     while index < len(A_List):
    
45.         possible.append(constRes + sum(B_List[0:index])+sum(A_List[(index + 1):]))
    
46.         index += 1
    
47.     return min(possible)

复制代码

zltzlt

TJBEST 发表于 2020-2-13 18:53
塔利班的方法真的妙，我的方法真的相形见绌了，不过不能抄袭

超时

TJBEST

还超时吗？

1. def fun331(string):
   
2.     M = len(string)
   
3.     try:
   
4.         firstCharcter = string[0]
   
5.     except Exception:
   
6.         return 0
   
7.    
   
8.     A_has = string.count('A')
   
9.     B_has = M - A_has
   
10.    
    
11.     result = min([A_has,B_has])
    
12.    
    
13.     for i in range(0,M - 1):
    
14.         if string[i] == 'A' and string[i+1] == 'B':
    
15.             result = min([result,string[0:i].count('B')+string[(i+1):].count('A')])
    
16.     return result

复制代码

wanting-for

1. def solve_311(s: str):
   
2.     a_c, b_c, len_s, count = s.count('A'), s.count('B'), len(s), float('inf')
   
3.     a_cc, b_cc, i = 0, 0, 0
   
4.     i = 0
   
5.     while i < len_s - 1:
   
6.         if s[i] == 'A' and s[i+1] == 'B':
   
7.             now = a_c - a_cc - 1
   
8.             if now + b_cc < count:
   
9.                 count = now + b_cc
   
10.             i += 2
    
11.             a_cc += 1
    
12.             b_cc += 1
    
13.         elif s[i] == 'B':
    
14.             b_cc += 1
    
15.             i += 1
    
16.         elif s[i] == 'A':
    
17.             a_cc += 1
    
18.             i += 1
    
19.     return min(a_c,b_c,count)
    
20. print(solve_311("AABBBB"))

复制代码

看似简便，就是不知道效率怎们样，
这道题感觉方法还是比较明确的

塔利班

1. def f331(x):
   
2.     m,sa,sb=len(x),0,0
   
3.     for e in 'C'+x:
   
4.         if e=='A':
   
5.             sa+=1
   
6.         elif e=='B':
   
7.             sb+=1
   
8.         m=min(sb-sa,m)
   
9.     return m+sa

复制代码

想了想count本来就死On，多跑了一圈

阴阳神万物主

不晓得有没有错漏。

1. def solve(s:str)->int:
   
2.     s1 = list(s)
   
3.     temp = sorted(s)
   
4.     res = 0
   
5.     while s1 != temp:
   
6.         for i in range(len(s1)):
   
7.             if s1[i] != temp[i]:
   
8.                 res += 1
   
9.                 if s1[i] == 'A':
   
10.                     temp.pop(0)
    
11.                 else:
    
12.                     temp.pop(-1)
    
13.                 s1.pop(i)
    
14.                 break
    
15.     if len(set(s1)) == 1:
    
16.         res = min(s.count('A'),res)
    
17.     return res
    
18. if __name__ == '__main__':
    
19.     print('示例1 输出：',solve('BAAABAB'))
    
20.     print('示例2 输出：',solve('BBABBAA'))
    
21.     print('示例3 输出：',solve('AABBBB'))
    

复制代码

genius_7321

我的方法好像有点笨：

1. import re
   
2. 
   
3. 
   
4. def my_answer(s, tar='AB'):
   
5.     flag = 0
   
6.     aabb = 0
   
7.     dist = {}
   
8.     if s.count('A') == 0 or s.count('B') == 0:
   
9.         return f'共需删除0个字符！\n字符串本身符合条件'
   
10.     else:
    
11.         for each in re.finditer(tar, s):
    
12.             if s.count('A') == s.count('B'):
    
13.                 aabb = s.count('B')
    
14.                 flag = 1
    
15.             else:
    
16.                 sum = s.count('A', each.start() + 1, len(s)) + s.count('B', 0, each.start())
    
17.                 if sum == 0:
    
18.                     flag = 2
    
19.                 else:
    
20.                     dist[each.start()] = sum
    
21.         if flag == 0:
    
22.             min_index = min(dist, key=lambda k: dist[k])
    
23.             if dist[min_index] > s.count('A'):
    
24.                 a = s.count('A')
    
25.                 sb = s.replace('A', '')
    
26.                 return f'共需删除{a}个字符！\n新字符串为{sb}'
    
27.             elif dist[min_index] > s.count('B'):
    
28.                 a = s.count('B')
    
29.                 sa = s.replace('B', '')
    
30.                 return f'共需删除{a}个字符！\n新字符串为{sa}'
    
31.             else:
    
32.                 sa = s[:min_index + 1].replace('B', '')
    
33.                 sb = s[min_index + 1:].replace('A', '')
    
34.                 return f'共需删除{dist[min_index]}个字符！\n新字符串为{sa + sb}'
    
35.         elif flag == 1:
    
36.             return f'共需删除{aabb}个字符！\n可以删除所有的 A 或 B'
    
37.         else:
    
38.             return f'共需删除0个字符！\n字符串本身符合条件'
    
39. 
    
40. 
    
41. print('示例1结果：', my_answer('BAAABAB'))
    
42. print('示例2结果：', my_answer('BBABAA'))
    
43. print('示例3结果：', my_answer('AABBBB'))
    

复制代码

ouyunfu

def f331(s:str)->int:
    res,tA,a,b,=min(s.count('A'),s.count('B')),s.count('A'),0,0
    for i in s:
        if i=='A':
            a+=1
        if i=='B':
            b+=1
        res=min(b+tA-a,res)
    return res
L=['BAAABAB','BBABAA','AABBBB']
for s in L:
    print(f331(s))

yeyu0142

1. def fun331(s):
   
2.     flag = 'A'
   
3.     c = 0
   
4.     c_A = s.count('A')
   
5.     c_B = s.count('B')
   
6.     t = 0
   
7.     if (c_A == len(s)) or (c_B == len(s)):
   
8.         return 0
   
9.     for i in s:
   
10.         if i != flag:
    
11.             c += 1
    
12.             if t>0:
    
13.                 flag = 'B'
    
14.         else:
    
15.             t += 1
    
16.     return min(c-1,c_A,c_B)

复制代码

fan1993423

zltzlt 发表于 2020-2-13 18:10
解答错误

输入：

这个删除前面两个B最后两个A，不就是A开头，B结束，中间有AB的字符串了吗？A...AB...B到底是什么意思