Posted on 2023-08-23 16:31
Uriel 阅读(9)
评论(0) 编辑 收藏 引用 所属分类:
贪心 、
闲来无事重切Leet Code
将一列字符串中的字符重新排序，使得相邻字符不相同
贪心思想，用priority queue将字符按照出现次数从多到少排序，然后一次填入结果字符串，如果单种字符次数超过字符串总长度一半，则不能实现。先填充所有奇数位，然后填偶数位
1 #767
2 #Runtime: 11 ms (Beats 98.89%)
3 #Memory: 13.5 MB (Beats 11.11%)
4
5 class Solution(object):
6 def reorganizeString(self, s):
7 """
8 :type s: str
9 :rtype: str
10 """
11 n = len(s)
12 freq = defaultdict(int)
13 for i in range(n):
14 freq[s[i]] += 1
15 hp = [(-v, k) for k, v in freq.items()]
16 heapify(hp)
17 i = 0
18 ans = [""] * n
19 while hp:
20 v, k = heappop(hp)
21 if 2 * (-v) - 1 > n:
22 return ""
23 for _ in range(-v):
24 ans[i] = k
25 if i + 2 < n:
26 i += 2
27 else:
28 i = 1
29 return "".join(ans)