Python：每日一题 331
今天的题目：给定一个只包含大写字母 A 和 B 的字符串。删除最少的字符使得字符串变成 A...AB...B 的形式。
返回需要删除的最少字符数。
示例 1：
输入："BAAABAB"
输出：2
解释：删除第一个 B 和最后一个 A，构成 "AAABB"。
示例 2：
输入："BBABAA"
输出：3
解释：可以删除所有的 A 或 B。
示例 3：
输入："AABBBB"
输出：0
解释：不需要删除任何字符，因为字符串本身符合条件。
{:10_298:}欢迎大家一起答题！{:10_298:} 也就是 AAA 或 BBB也算？ def f331(x):
m,sa,sb,ta=len(x),0,0,x.count('A')
for e in x:
if e=='A':
sa+=1
if e=='B':
sb+=1
m=min(sb+ta-sa,m)
return m zltzlt 发表于 2020-2-13 18:09
不算，而且字符串一定既包含 A 也包含 B
BBABAA 为什么是3？ 最少4个吧？ 塔利班 发表于 2020-2-13 18:09
解答错误
输入："BBABABBBABABABBBABABABAABBBBABAABBBBABABBBBABBAABBBABBBBABBABAAABBBABAABAAAAAABABAABABBAABBBABBABAAAAAABBBBAAAAAAABBBBAABAABAABABABAABBAAABBAABBBBABBBBAAAABABBBBBBABBBBBAABAAAAAABABABBAABBABBABAABABABABABABBAAABBBBBBBBABBABABBABBBBBBBABBBBAABBBAABBAABBABAAABABBAAAAAAAABBAAABAAABBAAABBABBBAAABBBBBABABBABBBBBABBBBBAAAAAABBAABABAAABABBAAAABBBBBAAAAAABBAAABAABAABBABBBBAABABBAABAAAAAAAAABAABBBBABBBBBAABABABBBABBAABBBAAAABABABBBABAABBBBABAABABAAABBABBBBBABBBBBABBBAABABBAABBBBAABABAABBBAABABBBAAAABAAAABBBAAABAABAABAAAAAAABBBABABBBBABBABBBBABAABABBABABBBABBABBAAAABAABBBBABAABABBBABBBAABBBBBBBBBABAAAABAAAAAABABAABAABBAABAAAAAABBBBBBAABBBBBAAAAAAAABBAAAABAAABBAABAABAABAAAABAAAAABABBAABAABAABAAAABABABABBAABBBAABAAABBABABAAABBBBBABBBAABBBABBBABBBABABBBBBAAAABAABBBBBAABABBAABBABBABBBABBBABBBBABAABBAAAAABBAAAABABBABBBBBAABBBBBAABBBBBABBBABBBBABABAAABBABABAAAAAABABAABBABBABABAABBBBABABBAAAABBBABABBBBABBBAAABAAAAABAAABBABBBBAAAABBBBABBBBBBAABABBBBAABBABAABBAABBBABAAAABABBBAAAABAABABBABBBBBAABBBBABBBAA"
输出：476
预期结果：475 TJBEST 发表于 2020-2-13 18:10
BBABAA 为什么是3？ 最少4个吧？
自相矛盾了……
刚刚说错了，AAA 或 BBB 也算 zltzlt 发表于 2020-2-13 18:12
自相矛盾了……
刚刚说错了，AAA 或 BBB 也算
好的 也就是 只剩A或者只剩B也算 对吧 TJBEST 发表于 2020-2-13 18:15
好的 也就是 只剩A或者只剩B也算 对吧
对{:10_254:} 本帖最后由 塔利班 于 2020-2-13 18:37 编辑
zltzlt 发表于 2020-2-13 18:10
解答错误
输入：
def f331(x):
m,sa,sb,ta=len(x),0,0,x.count('A')
for e in 'C'+x:
if e=='A':
sa+=1
elif e=='B':
sb+=1
m=min(sb+ta-sa,m)
return m 塔利班 发表于 2020-2-13 18:29
703 ms 塔利班的方法真的妙，我的方法真的相形见绌了，不过不能抄袭
def fun331(string):
M = len(string)
try:
firstCharcter = string
except Exception:
return 0
A_List = []
B_List = []
temp = firstCharcter
count = 1
for i in range(1,M):
if string == temp:
count += 1
else:
if temp == 'A':
A_List.append(count)
else:
B_List.append(count)
temp = string
count = 1
if temp == 'A':
A_List.append(count)
else:
B_List.append(count)
possible = []
possible.append(min(sum(A_List),sum(B_List)))
if len(A_List) > len(B_List):
constRes = A_List.pop()
elif len(A_List) < len(B_List):
constRes = B_List
B_List = B_List
else:
if firstCharcter == 'A':
constRes = 0
else:
constRes = A_List.pop() + B_List
B_List = B_List
index = 0
while index < len(A_List):
possible.append(constRes + sum(B_List)+sum(A_List[(index + 1):]))
index += 1
return min(possible) TJBEST 发表于 2020-2-13 18:53
塔利班的方法真的妙，我的方法真的相形见绌了，不过不能抄袭
超时 还超时吗？
def fun331(string):
M = len(string)
try:
firstCharcter = string
except Exception:
return 0
A_has = string.count('A')
B_has = M - A_has
result = min()
for i in range(0,M - 1):
if string == 'A' and string == 'B':
result = min(.count('B')+string[(i+1):].count('A')])
return result 本帖最后由 wanting-for 于 2020-2-13 23:28 编辑
def solve_311(s: str):
a_c, b_c, len_s, count = s.count('A'), s.count('B'), len(s), float('inf')
a_cc, b_cc, i = 0, 0, 0
i = 0
while i < len_s - 1:
if s == 'A' and s == 'B':
now = a_c - a_cc - 1
if now + b_cc < count:
count = now + b_cc
i += 2
a_cc += 1
b_cc += 1
elif s == 'B':
b_cc += 1
i += 1
elif s == 'A':
a_cc += 1
i += 1
return min(a_c,b_c,count)
print(solve_311("AABBBB"))
看似简便，就是不知道效率怎们样，
这道题感觉方法还是比较明确的 def f331(x):
m,sa,sb=len(x),0,0
for e in 'C'+x:
if e=='A':
sa+=1
elif e=='B':
sb+=1
m=min(sb-sa,m)
return m+sa
想了想count本来就死On，多跑了一圈 不晓得有没有错漏。
def solve(s:str)->int:
s1 = list(s)
temp = sorted(s)
res = 0
while s1 != temp:
for i in range(len(s1)):
if s1 != temp:
res += 1
if s1 == 'A':
temp.pop(0)
else:
temp.pop(-1)
s1.pop(i)
break
if len(set(s1)) == 1:
res = min(s.count('A'),res)
return res
if __name__ == '__main__':
print('示例1 输出：',solve('BAAABAB'))
print('示例2 输出：',solve('BBABBAA'))
print('示例3 输出：',solve('AABBBB'))
本帖最后由 genius_7321 于 2020-2-13 23:10 编辑
我的方法好像有点笨：
import re
def my_answer(s, tar='AB'):
flag = 0
aabb = 0
dist = {}
if s.count('A') == 0 or s.count('B') == 0:
return f'共需删除0个字符！\n字符串本身符合条件'
else:
for each in re.finditer(tar, s):
if s.count('A') == s.count('B'):
aabb = s.count('B')
flag = 1
else:
sum = s.count('A', each.start() + 1, len(s)) + s.count('B', 0, each.start())
if sum == 0:
flag = 2
else:
dist = sum
if flag == 0:
min_index = min(dist, key=lambda k: dist)
if dist > s.count('A'):
a = s.count('A')
sb = s.replace('A', '')
return f'共需删除{a}个字符！\n新字符串为{sb}'
elif dist > s.count('B'):
a = s.count('B')
sa = s.replace('B', '')
return f'共需删除{a}个字符！\n新字符串为{sa}'
else:
sa = s[:min_index + 1].replace('B', '')
sb = s.replace('A', '')
return f'共需删除{dist}个字符！\n新字符串为{sa + sb}'
elif flag == 1:
return f'共需删除{aabb}个字符！\n可以删除所有的 A 或 B'
else:
return f'共需删除0个字符！\n字符串本身符合条件'
print('示例1结果：', my_answer('BAAABAB'))
print('示例2结果：', my_answer('BBABAA'))
print('示例3结果：', my_answer('AABBBB'))
本帖最后由 ouyunfu 于 2020-2-13 21:51 编辑
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)) def fun331(s):
flag = 'A'
c = 0
c_A = s.count('A')
c_B = s.count('B')
t = 0
if (c_A == len(s)) or (c_B == len(s)):
return 0
for i in s:
if i != flag:
c += 1
if t>0:
flag = 'B'
else:
t += 1
return min(c-1,c_A,c_B) zltzlt 发表于 2020-2-13 18:10
解答错误
输入：
这个删除前面两个B最后两个A，不就是A开头，B结束，中间有AB的字符串了吗？A...AB...B到底是什么意思