给定一个长度为 n 的字符串,请你重新排列这个字符串,使其每个相邻的字符都不同。
你可以返回任意一个合法的结果,如果没有合法结果请返回空字符串
数据范围:字符串长度满足 ,字符串中仅包含小写英文字母
"abcdd"
"adbcd"
"nowcoder"
"nowcoder"
本身就是合法字符串,无需再排,但返回重排的字符串也是正确的
"aaab"
""
# -*- coding: utf-8 -*- import collections # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param str string字符串 # @return string字符串 # class Solution: """ 题目: https://www.nowcoder.com/practice/6c3a5604cf274b2287fbe27c5dc74743?tpId=196&tqId=40510&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title= 参考: 大神:居梇梇 算法: 1. 统计每个字符出现的次数,collections.Counter(str) 2. 获取出现次数最多的字符的出现次数,判断是否能够填充 3. 对count按字符出现次数进行排序 4. 将排序结果,转化为字符数组data,如[('d', 4), ('a', 1), ('c', 1), ('b', 1)] ==> ['d', 'd', 'd', 'd', 'a', 'c', 'b'] 5. 取数组data的前后两部分,进行交叉合并 复杂度: 时间复杂度:O(mlogm + m + n/2), m为count的长度, n为字符串的长度 空间复杂度:O(m) """ def rearrangestring(self, s): # write code here n = len(s) if not s&nbs***bsp;n == 1: return s count = collections.Counter(s) # 统计s中每个字符出现次数 maxCount = max(count.values()) if maxCount > (n + 1) // 2: # 判断是否能够填充 return "" count = sorted(count.items(), key=lambda x: -x[1]) # 按字符出现次数对count进行排序,sorted支持对可迭代对象排序,sort只支持列表排序 # print count data = [] for k, v in count: data += [k] * v # print data # m = (n + 1) // 2 # i, j, res = 0, m, "" # while i < m and j < n: # 遍历的方式进行合并,不通过 # res += data[i] + data[j] # i += 1 # j += 1 # if i < m: # res += data[i] # return res res = ["" for _ in range(len(s))] res[::2], res[1::2] = data[:(n + 1) // 2], data[(n + 1) // 2:] return "".join(res) if __name__ == "__main__": sol = Solution() # str = "abcdd" # str = "nowcoder" # str = "aaab" # str = "cdarzo" # str = "aaaabbbb" # str = "wlrbbmqb" str = "abcdddd" res = sol.rearrangestring(str) print res