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

zltzlt

今天的题目：

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

示例 1：

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

示例 2：

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

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

Croper

2020-1-31 15:57:02

1. def func320(sz:str):
   
2.     dct={}
   
3.     for i in sz:
   
4.         dct[i]=dct.get(i,0)+1
   
5.     lst=list(dct.values())
   
6.     lst.sort(reverse=True)
   
7.     ret,pre=0,0xFFFFFFFF
   
8.     for i in lst:
   
9.         pre=max(0,min(i,pre-1))
   
10.         ret+=i-pre
    
11.     return ret

复制代码

跳转到最佳答案楼层

最后的魁拔

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

复制代码

Croper

1. def func320(sz:str):
   
2.     dct={}
   
3.     for i in sz:
   
4.         dct[i]=dct.get(i,0)+1
   
5.     lst=list(dct.values())
   
6.     lst.sort(reverse=True)
   
7.     ret,pre=0,0xFFFFFFFF
   
8.     for i in lst:
   
9.         pre=max(0,min(i,pre-1))
   
10.         ret+=i-pre
    
11.     return ret

复制代码

wanting-for

1. def solve_320(str1:str):
   
2.     dict1 = {}
   
3.     for i in str1:
   
4.         if i not in dict1:
   
5.             dict1[i]=1
   
6.         else:
   
7.             dict1[i]+=1
   
8.     count,value = 0,[]
   
9.     sorted(zip(dict1.values(),dict1.keys()),reverse= True)
   
10.     for i in dict1.values():
    
11.         value.append(i)
    
12.     for j in range(1,len(value)):
    
13.         if value[j] == 1:
    
14.             if value[0] == 1:
    
15.                 count+=len(value)-j
    
16.             else:
    
17.                 count+=len(value)-j-1
    
18.             break
    
19.         elif value[j] == value[j-1]:
    
20.             value[j]-=1
    
21.             count+=1
    
22.     return count
    
23. print(solve_320("abcd"))

复制代码

塔利班

1. def f320(s):
   
2.     if len(s)==1:
   
3.         return 0
   
4.     d=dict()
   
5.     for e in s:
   
6.         d[e]=d.get(e,0)+1
   
7.     L=sorted(list(d.values()))
   
8.     l=len(L)
   
9. 
   
10.     if l==1:
    
11.         return 0
    
12.     else:
    
13.         r=l-2
    
14.         res=0
    
15.         while r>=0:
    
16.             if L[r]>=L[r+1]:
    
17.                 if L[r+1]==0:
    
18.                     res+=L[r]
    
19.                     L[r]=0
    
20.                 else:
    
21.                     dd=L[r]-L[r+1]+1
    
22.                     res+=dd
    
23.                     L[r]-=dd
    
24.             r-=1
    
25.         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"

1. def solve_320(str1:str):
   
2.     dict1 = {}
   
3.     for i in str1:
   
4.         if i not in dict1:
   
5.             dict1[i]=1
   
6.         else:
   
7.             dict1[i]+=1
   
8.     count,value = 0,[]
   
9.     for i in dict1.values():
   
10.         value.append(i)
    
11.     value.sort(reverse = True)
    
12.     ls = [value[0]]
    
13.     for j in range(1,len(value)):
    
14.         if value[j] >= min(ls):
    
15.             if min(ls)==0:
    
16.                 count+=value[j]
    
17.             else:
    
18.                 count+=(value[j]-min(ls))+1
    
19.                 value[j] = min(ls)-1            
    
20.         ls = value[:j+1]
    
21.     return count
    
22. print(solve_320("abcddajdfhsdfiitujhjsfjajjajjjjjajkakdksakdjkaskjdfhjfjkadawiwuqehuhhdmcnjfhajdnasdlkasdjkaljfheufhauiiqedqwioiadfnc"))

复制代码

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

fan1993423

1. from collections import Counter
   
2. def fun320(s):
   
3.     lst=sorted(list(Counter(s).values()),reverse=True)
   
4.     count=0
   
5.     def loop(lst):
   
6.         nonlocal count
   
7.         if 0 in lst:
   
8.             index0=lst.index(0)
   
9.             if len(lst[:index0])==len(set(lst[:index0])):
   
10.                 return count
    
11.         if len(lst)==len(set(lst)):
    
12.             return count
    
13.         for i in lst:
    
14.             if lst.count(i)!=1:
    
15.                 lst[lst.index(i)]-=1
    
16.                 count+=1
    
17.                 return loop(sorted(lst,reverse=True))
    
18.             else:
    
19.                 lst.remove(i)
    
20.     return loop(lst)

复制代码

阴阳神万物主

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

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

复制代码

zltzlt

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

想象力真丰富

fan1993423

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

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

SHRS23

1. string = input('输入字符串：')
   
2. list1 = [0] * 26
   
3. for each in string:
   
4.     list1[ord(each)-97] += 1
   
5. list1.sort(reverse = True)
   
6. #print(list1)
   
7. count = 0
   
8. finish = False
   
9. while not finish:
   
10.     for i in range(26):
    
11.         if list1[i] == 0:
    
12.             finish = True
    
13.             break
    
14.         if list1[i] != list1[i+1]:
    
15.             continue
    
16.         #print(i)
    
17.         list1[i] -= 1
    
18.         count += 1
    
19.         list1.sort(reverse = True)
    
20.         break
    
21. print(count)
    

复制代码

请版主帮忙测试

TJBEST

非常朴素的做法

1. def fun320(string):
   
2.     dictionary = dict()
   
3.     for each in string:
   
4.         try:
   
5.             dictionary[each] += 1
   
6.         except KeyError:
   
7.             dictionary[each] = 1
   
8.     data = list(dictionary.values())
   
9.     data.sort()
   
10.     data.reverse()
    
11.     M = len(data)
    
12.     result = 0
    
13.     for i in range(0,M-1):
    
14.         temp = data[i]
    
15.         if temp > data[M-1]:
    
16.              for m in range(i+1,M):
    
17.                 if data[m] == temp:
    
18.                     data[m] = temp - 1
    
19.                     result += 1
    
20.                 else:
    
21.                     break
    
22.         else:
    
23.             if i + temp <= M:
    
24.                 res = ((temp + 1)*temp)//2
    
25.             else:
    
26.                 res = ((M - i)*(2*temp + i - M +1))//2
    
27.             result += (M-i)*temp-res
    
28.             break
    
29.     return result

复制代码

hrp

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

思路一样

1. def func320(s):
   
2.     templist = [s.count(i) for i in set(s)]
   
3.     templist.sort(reverse=True)
   
4.     result, length = 0, len(templist)
   
5.     for ind in range(length):
   
6.         if len(set(templist)) != length:
   
7.             num = templist.count(templist[ind])
   
8.             for i in range(ind + 1, ind + num):
   
9.                 templist[i] -= 1
   
10.                 result += 1
    
11.         else:
    
12.             break
    
13.     return result

复制代码

546623863

1. def fun320(x):
   
2.     a = set(x)
   
3.     b = set()
   
4.     result = 0
   
5.     l = []
   
6.     for each in a:
   
7.         l.append(x.count(each))
   
8.     l.sort(reverse = True)
   
9.     for each in l:
   
10.         if each not in b and each != 0:
    
11.             b.add(each)
    
12.             continue
    
13.         else:
    
14.             while each in b and each != 0:
    
15.                 each -= 1
    
16.                 result += 1
    
17.         b.add(each)
    
18.     return result
    
19. 
    
20. print(fun320("aaabbbccc"))

复制代码

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