重排字符串

# -*- 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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串
     */
    string rearrangestring(string str) {
        //字符次数
        int num[26]={0};
        for(int i=0;i<str.size();i++)
        {
            num[str[i]-'a']++;
        }
        //元组统计
        map<char,int> my_map;
        vector<int> my_sort;
        for(int i=0;i<26;i++)
        {
            if(num[i]!=0)
            {
                my_map[i]=num[i];
                my_sort.push_back(i);
            }
        }
        //排序
        for(int i=0;i<my_sort.size();i++)
        {
            for(int j=i+1;j<my_sort.size();j++)
            {
                if(my_map[my_sort[i]]<
                    my_map[my_sort[j]])
                {
                    int temp;
                    temp=my_sort[i];
                    my_sort[i]=my_sort[j];
                    my_sort[j]=temp;
                }
            }
        }
        //特判
        if(my_map[my_sort[0]]>=str.size()/2+1)
        {
            return "";
        }
        //插入
        //d   d  
        //0 1 2 3 4 
        string str_ans(str.size(),' ');
        //找到第一个空的头
        int head=0;
        for(int i=0;i<my_sort.size();i++)
        {
            for(int j=0;j<my_map[my_sort[i]];j++)
            {
                str_ans[head]=my_sort[i]+'a';
                head+=2;
                if(head>=str_ans.size())
                {
                    head=1;
                }
            }
        }
        return str_ans;
    }
};

package main
import "strings"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str string字符串 
 * @return string字符串
*/
func rearrangestring( str string ) string {
    cnt:=map[byte]int{}
    max:=0
    var tar byte
    for _,ch:=range []byte(str){
        cnt[ch]++
        if cnt[ch]>max{
            max=cnt[ch]
            tar=ch
        }
    }
    if len(str)-max<max-1{
        return ""
    }
    ans:=make([]string,max)
    for i,_:=range ans{
        ans[i]=string(tar)
    }
    delete(cnt,tar)
    add:=""
    for k,v:=range cnt{
        add+=strings.Repeat(string(k), v)
    }
    for len(add)>0{
        for i:=0;i<max;i++{
            if len(add)==0{
                break
            }
            ans[i]+=string(add[0])
            add=add[1:]
        }
    }
    return strings.Join(ans,"")
}