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

zltzlt

今天的题目：

给定一串英文字母，每次可以删掉一个英文字母，求最少删多少次可以让每个字母出现的次数不同。

示例 1：

输入："aaabbb"
输出：1
解释：因为 'a' 和 'b' 都有三个，所以删掉一个 'a' 或者一个 'b' 都可以满足题意。

示例 2：

输入："abcd"
输出：3
解释：因为 'a'、'b'、'c'、'd' 各有一个，所以需要删掉任意三个来满足题意。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

Croper

2020-1-31 15:57:02

def func320(sz:str):
    dct={}
    for i in sz:
        dct[i]=dct.get(i,0)+1
    lst=list(dct.values())
    lst.sort(reverse=True)
    ret,pre=0,0xFFFFFFFF
    for i in lst:
        pre=max(0,min(i,pre-1))
        ret+=i-pre
    return ret

跳转到最佳答案楼层

最后的魁拔

a,b,c,d删除3个，那是不是，b,c,d它们三个次数相同了

Croper

def func320(sz:str):
    dct={}
    for i in sz:
        dct[i]=dct.get(i,0)+1
    lst=list(dct.values())
    lst.sort(reverse=True)
    ret,pre=0,0xFFFFFFFF
    for i in lst:
        pre=max(0,min(i,pre-1))
        ret+=i-pre
    return ret

wanting-for

def solve_320(str1:str):
    dict1 = {}
    for i in str1:
        if i not in dict1:
            dict1[i]=1
        else:
            dict1[i]+=1
    count,value = 0,[]
    sorted(zip(dict1.values(),dict1.keys()),reverse= True)
    for i in dict1.values():
        value.append(i)
    for j in range(1,len(value)):
        if value[j] == 1:
            if value[0] == 1:
                count+=len(value)-j
            else:
                count+=len(value)-j-1
            break
        elif value[j] == value[j-1]:
            value[j]-=1
            count+=1
    return count
print(solve_320("abcd"))

塔利班

def f320(s):
    if len(s)==1:
        return 0
    d=dict()
    for e in s:
        d[e]=d.get(e,0)+1
    L=sorted(list(d.values()))
    l=len(L)

    if l==1:
        return 0
    else:
        r=l-2
        res=0
        while r>=0:
            if L[r]>=L[r+1]:
                if L[r+1]==0:
                    res+=L[r]
                    L[r]=0
                else:
                    dd=L[r]-L[r+1]+1
                    res+=dd
                    L[r]-=dd
            r-=1
        return res

zltzlt

最后的魁拔 发表于 2020-1-31 15:43

不是，删掉 3 个，只剩下一个。

fan1993423

abbaba 这种也算a,b各三个对吧

zltzlt

fan1993423 发表于 2020-1-31 17:10
abbaba 这种也算a,b各三个对吧

对

fan1993423

题目的意思是不是 aaabbb减少任意一个字母 使得a和b的次数不一样 这里就是2和3不一样，然后abcd 减少abc的话 就是0,0,0,1次，0不算，所以1和他们都不同，是这个意思嘛？

zltzlt

fan1993423 发表于 2020-1-31 17:21
题目的意思是不是 aaabbb减少任意一个字母 使得a和b的次数不一样 这里就是2和3不一样，然后abcd 减少abc的 ...

是。

zltzlt

wanting-for 发表于 2020-1-31 16:07

解答错误

输入："aaabbbccc"
输出：1
预期结果：3

wanting-for

zltzlt 发表于 2020-1-31 17:39
解答错误

输入："aaabbbccc"

def solve_320(str1:str):
    dict1 = {}
    for i in str1:
        if i not in dict1:
            dict1[i]=1
        else:
            dict1[i]+=1
    count,value = 0,[]
    for i in dict1.values():
        value.append(i)
    value.sort(reverse = True)
    ls = [value[0]]
    for j in range(1,len(value)):
        if value[j] >= min(ls):
            if min(ls)==0:
                count+=value[j]
            else:
                count+=(value[j]-min(ls))+1
                value[j] = min(ls)-1            
        ls = value[:j+1]
    return count
print(solve_320("abcddajdfhsdfiitujhjsfjajjajjjjjajkakdksakdjkaskjdfhjfjkadawiwuqehuhhdmcnjfhajdnasdlkasdjkaljfheufhauiiqedqwioiadfnc"))

菜鸟与大佬的差距就是，大佬啥都考虑的清清楚楚。而我就漏这漏那，不严谨....

fan1993423

from collections import Counter
def fun320(s):
    lst=sorted(list(Counter(s).values()),reverse=True)
    count=0
    def loop(lst):
        nonlocal count
        if 0 in lst:
            index0=lst.index(0)
            if len(lst[:index0])==len(set(lst[:index0])):
                return count
        if len(lst)==len(set(lst)):
            return count
        for i in lst:
            if lst.count(i)!=1:
                lst[lst.index(i)]-=1
                count+=1
                return loop(sorted(lst,reverse=True))
            else:
                lst.remove(i)
    return loop(lst)

阴阳神万物主

娱乐向解题，嗯，好像是。(AWA)

def solve(s:str)->int:
    '''
    给定一串英文字母，
    每次可以删掉一个英文字母，
    求最少删多少次可以让每个字母出现的次数不同。
    '''
    log = [s.count(x) for x in set(s)]          #人口普查
    log.sort(reverse=True)
    res = 0
    for i in range(len(log)):                   #计算排队喊号
        while log[i] and log.count(log[i])-1:   #能提前就提前
            log[i] -= 1
            res += 1
    return res                                  #编不下去了
if __name__ == '__main__':
    print('示例1 输出：',solve("aaabbb"))
    print('示例2 输出：',solve("abcd"))

zltzlt

阴阳神万物主 发表于 2020-1-31 18:41
娱乐向解题，嗯，好像是。(AWA)

想象力真丰富

fan1993423

阴阳神万物主 发表于 2020-1-31 18:41
娱乐向解题，嗯，好像是。(AWA)

是啊，我又想多了，原来可以这么巧

SHRS23

string = input('输入字符串：')
list1 = [0] * 26
for each in string:
    list1[ord(each)-97] += 1
list1.sort(reverse = True)
#print(list1)
count = 0
finish = False
while not finish:
    for i in range(26):
        if list1[i] == 0:
            finish = True
            break
        if list1[i] != list1[i+1]:
            continue
        #print(i)
        list1[i] -= 1
        count += 1
        list1.sort(reverse = True)
        break
print(count)

请版主帮忙测试

TJBEST

非常朴素的做法

def fun320(string):
    dictionary = dict()
    for each in string:
        try:
            dictionary[each] += 1
        except KeyError:
            dictionary[each] = 1
    data = list(dictionary.values())
    data.sort()
    data.reverse()
    M = len(data)
    result = 0
    for i in range(0,M-1):
        temp = data[i]
        if temp > data[M-1]:
             for m in range(i+1,M):
                if data[m] == temp:
                    data[m] = temp - 1
                    result += 1
                else:
                    break
        else:
            if i + temp <= M:
                res = ((temp + 1)*temp)//2
            else:
                res = ((M - i)*(2*temp + i - M +1))//2
            result += (M-i)*temp-res
            break 
    return result

hrp

阴阳神万物主 发表于 2020-1-31 18:41
娱乐向解题，嗯，好像是。(AWA)

思路一样

def func320(s):
    templist = [s.count(i) for i in set(s)]
    templist.sort(reverse=True)
    result, length = 0, len(templist)
    for ind in range(length):
        if len(set(templist)) != length:
            num = templist.count(templist[ind])
            for i in range(ind + 1, ind + num):
                templist[i] -= 1
                result += 1
        else:
            break
    return result

546623863

def fun320(x):
    a = set(x)
    b = set()
    result = 0
    l = []
    for each in a:
        l.append(x.count(each))
    l.sort(reverse = True)
    for each in l:
        if each not in b and each != 0:
            b.add(each)
            continue 
        else:
            while each in b and each != 0:
                each -= 1
                result += 1
        b.add(each)
    return result

print(fun320("aaabbbccc"))

感觉我每次写的思路都比较奇葩。。。。