[已解决]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

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[i] == 'A' and s[i+1] == '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[i] == 'B':
            b_cc += 1
            i += 1
        elif s[i] == 'A':
            a_cc += 1
            i += 1
    return min(a_c,b_c,count)
print(solve_311("AABBBB"))

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

跳转到最佳答案楼层

TJBEST

也就是 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

TJBEST

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

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

zltzlt

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

解答错误

输入：

"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
解答错误

输入：

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

zltzlt

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

703 ms

TJBEST

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

def fun331(string):
    M = len(string)
    try:
        firstCharcter = string[0]
    except Exception:
        return 0
    A_List = []
    B_List = []
   
    temp = firstCharcter
    count = 1
    for i in range(1,M):
        if string[i] == temp:
            count += 1
        else:
            if temp == 'A':
                A_List.append(count)
            else:
                B_List.append(count)
            temp = string[i]
            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[0]
        B_List = B_List[1:]
    else:
        if firstCharcter == 'A':
            constRes = 0
        else:
            constRes = A_List.pop() + B_List[0]
            B_List = B_List[1:]
    
    index = 0
    while index < len(A_List):
        possible.append(constRes + sum(B_List[0:index])+sum(A_List[(index + 1):]))
        index += 1
    return min(possible)

zltzlt

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

超时

TJBEST

还超时吗？

def fun331(string):
    M = len(string)
    try:
        firstCharcter = string[0]
    except Exception:
        return 0
    
    A_has = string.count('A')
    B_has = M - A_has
    
    result = min([A_has,B_has])
    
    for i in range(0,M - 1):
        if string[i] == 'A' and string[i+1] == 'B':
            result = min([result,string[0:i].count('B')+string[(i+1):].count('A')])
    return result

wanting-for

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[i] == 'A' and s[i+1] == '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[i] == 'B':
            b_cc += 1
            i += 1
        elif s[i] == '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[i] != temp[i]:
                res += 1
                if s1[i] == '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

我的方法好像有点笨：

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[each.start()] = sum
        if flag == 0:
            min_index = min(dist, key=lambda k: dist[k])
            if dist[min_index] > s.count('A'):
                a = s.count('A')
                sb = s.replace('A', '')
                return f'共需删除{a}个字符！\n新字符串为{sb}'
            elif dist[min_index] > 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[min_index + 1:].replace('A', '')
                return f'共需删除{dist[min_index]}个字符！\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

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

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)

fan1993423

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

输入：

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