美文网首页
8.21 - hard - 74

8.21 - hard - 74

作者: 健时总向乱中忙 | 来源:发表于2017-08-22 00:59 被阅读0次

    358. Rearrange String k Distance Apart

    这道题就是把所有值都进行最大区分,在重新加入heap的时候要注意,如果两个值有同样的count,那么后访问过的要先加进去,比如说bba, size=1,先加入b,此时a,b的count都是1,这时候要先加入a,再加入b

    class Solution(object):
        def rearrangeString(self, s, k):
            """
            :type s: str
            :type k: int
            :rtype: str
            """
            if k == 0:
                return s
            h = {}
            for c in s:
                h[c] = h.get(c, 0) + 1
            
            heap = []
            for key, val in h.iteritems():
                heapq.heappush(heap, [-val, key])
            
            res = []
            
            while heap:
                temp = []
                n = len(s) - len(res)
                for _ in range(min(k, n)):
                    if not heap:
                        return ""
                    cur_val, key = heapq.heappop(heap)
                    res.append(key)
                    cur_val += 1
                    if cur_val != 0:
                        temp.append([cur_val, key])
                
                while temp:
                    heapq.heappush(heap, temp.pop())
            
            return "".join(res)
    

    相关文章

      网友评论

          本文标题:8.21 - hard - 74

          本文链接:https://www.haomeiwen.com/subject/cvkkdxtx.html