Posted on 2023-08-23 16:31
Uriel 閱讀(41)
評論(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)