leetcode767

1. 优先队列的使用，需要重写比较器

class Solution {
    public String reorganizeString(String S) {
        int nums[] = new int[26];
        for(int i=0; i<S.length(); i++){
            nums[S.charAt(i)-'a']++;
        }
        PriorityQueue<MyChar> queue = new PriorityQueue<MyChar>(new Comparator<MyChar>(){
            @Override
            public int compare(MyChar ch1, MyChar ch2){
                return ch2.count-ch1.count;
            }
            
        });
        for(int i=0; i<26; i++){
            if(nums[i]>=0 && nums[i] <= ((S.length()+1)/2)){
                if(nums[i]>0)
                    queue.add(new MyChar(nums[i],(char)(i+'a')));
              // System.out.println(nums[i]);
            } else{
                return "";
            }
        }
        StringBuilder result = new StringBuilder();
        while(queue.size()>1){
            MyChar ch1 = queue.poll();
            MyChar ch2 = queue.poll();
            if(result.length() == 0 || result.charAt(result.length()-1)!=ch1.ch){
                result.append(ch1.ch);
                result.append(ch2.ch);
            }
            if(--(ch1.count)>0){
                queue.add(ch1);
            }
            if(--(ch2.count)>0){
                queue.add(ch2);
            }
        }
        if(!queue.isEmpty())
            result.append(queue.poll().ch);
        return result.toString();
    }
}
class MyChar{
    int count;
    char ch;
    public MyChar(int count,char ch){
        this.count = count;
        this.ch = ch;
    }
}

2. 比较器

• Comparable可以认为是一个内比较器，实现了Comparable接口的类有一个特点，就是这些类是可以和自己比较的，至于具体和另一个实现了Comparable接口的类如何比较，则依赖compareTo方法的实现，compareTo方法也被称为自然比较方法。如果开发者add进入一个Collection的对象想要Collections的sort方法帮你自动进行排序的话，那么这个对象必须实现Comparable接口
• Comparator可以认为是是一个外比较器，个人认为有两种情况可以使用实现Comparator接口的方式：

1、一个对象不支持自己和自己比较（没有实现Comparable接口），但是又想对两个对象进行比较

2、一个对象实现了Comparable接口，但是开发者认为compareTo方法中的比较方式并不是自己想要的那种比较方式