Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
将一列字符串中的字符重新排序,使得相邻字符不相同
贪心思想,用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)

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理