Leetcode767. 重構(gòu)字符串

題目描述

給定一個(gè)字符串S，檢查是否能重新排布其中的字母，使得兩相鄰的字符不同。
若可行，輸出任意可行的結(jié)果。若不可行，返回空字符串。

示例1

輸入: S = "aab"
輸出: "aba"

示例2

輸入: S = "aaab"
輸出: ""

注意:

S 只包含小寫字母并且長度在[1, 500]區(qū)間內(nèi)。

解決問題的關(guān)鍵：

當(dāng)某個(gè)字符的出現(xiàn)次數(shù)大于字符總數(shù)的一半時(shí)，必然無法進(jìn)行重構(gòu)，返回空字符串。

class Solution(object):
    def reorganizeString(self, S):
        """
        :type S: str
        :rtype: str
        """
        S_dic = {}
        for i in range(len(S)):
            S_dic[S[i]] = S_dic.get(S[i],0) + 1
        S_list = sorted(S_dic, key=lambda x:S_dic[x], reverse=True)
        if S_dic[S_list[0]] > (len(S) + 1) / 2:
            return ""
        A = []
        for i in S_list:
            A.extend(i*S_dic[i])
        ans = [None] * len(S)
        ans[::2], ans[1::2] = A[:(len(S)+1)/2], A[(len(S)+1)/2:]
        return "".join(ans)

---------------------------------------------------------------------------------------------------------

Leetcode1054. 距離相等的條形碼

題目描述

在一個(gè)倉庫里，有一排條形碼，其中第 i 個(gè)條形碼為 barcodes[i]。
請(qǐng)你重新排列這些條形碼，使其中兩個(gè)相鄰的條形碼 不能 相等。 你可以返回任何滿足該要求的答案，此題保證存在答案。

示例 1：

輸入：[1,1,1,2,2,2]
輸出：[2,1,2,1,2,1]

示例 2：

輸入：[1,1,1,1,2,2,3,3]
輸出：[1,3,1,3,2,1,2,1]

class Solution(object):
    def rearrangeBarcodes(self, barcodes):
        """
        :type barcodes: List[int]
        :rtype: List[int]
        """ 
        dic = {}
        for i in barcodes:
            dic[i] = dic.get(i,0) + 1
        b = sorted(dic.keys(), key=lambda x:dic[x], reverse=True)
        a = []
        for i in b:
            a.extend([i,] * dic[i])
        L = len(barcodes)
        result = [None] * L
        result[::2], result[1::2] = a[:(L+1)/2], a[(L+1)/2:]
        return result