CodeCollection2018
8/26/2019 - 12:11 PM

rearange String k Distance Apart--按照相同字母距离至少为k来重排字符串--难

leetcode-hard问题，采用的方法是基于贪心算法+堆+Hashmap的方法。如果剩余的字符数量大于k那就要选择k个字符来排列，选的时候采用贪心方法选择出现次数最多的前k个字符所以用到了最大堆来维持。但是如果排的时候发现字符的种类不足k说明无法得到结果。如果剩余的字符数量小于k就排剩余不同种类的字符。

hard
content_copyfile_download
public String rearangeString(String str,int k){
    if(k==0) return str;
    int len = str.length();
    String result;
    HashMap<Character,Integer> hash = new HashMap<>();
    for(char c : str) hash.put(c,hash.get(c)+1);  //利用hash表来存各个字符及其出现的次数
    PriorityQueue<Pair<Integer,Character>> que = new PriorityQueue<>();
    for(Entry<Character,Integer> entry : hash){
        que.add(Pair(entry.getValue(),entry.getKey()));//构建堆的时候是按照个字符出现的次数来排，最大堆，每次都先选剩余出现次数最多的那种字符从而贪心。
    }
    while(!que.isEmpty()){//堆非空说明还有字符可以排
        List<Pair<Integer,Integer>> vec = new ArrayList<>();//保存这一遍下来之后还有剩余的字符及其剩余出现次数
        int cnt = min(k,len);//每次都选择k和当前剩余所有字符之和的最小值
        for(int i = 0; i < cnt; i++){//该循环就是出现次数最多的前cnt个每个都减1排到结果字符串中去，但是循环过程中很可能把堆pop光了说明不能得到结果字符串。
            if(que.isEmpty()) return "";
            Pair<> val = que.pop();
            result += val.value;//每次都选择出现次数最多的字符
            if(--val.key>0) vec.add(val);//如果该字符还有出现次数就得把它在循环结束之后再插入堆里面去，下一轮再用。
        }
        for(Entry val : vec) que.add(val);//插回堆中。
    }
    return result;
}