Leetcode767. 重构字符串
题目描述
给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。
若可行，输出任意可行的结果。若不可行，返回空字符串。
示例1
输入: S = "aab"
输出: "aba"
示例2
输入: S = "aaab"
输出: ""
注意:
S 只包含小写字母并且长度在[1, 500]区间内。
解决问题的关键：
当某个字符的出现次数大于字符总数的一半时，必然无法进行重构，返回空字符串。
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. 距离相等的条形码
题目描述
在一个仓库里，有一排条形码，其中第 i 个条形码为 barcodes[i]。
请你重新排列这些条形码，使其中两个相邻的条形码 不能 相等。 你可以返回任何满足该要求的答案，此题保证存在答案。
示例 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
