LeetCode451. Sort Characters By

LeetCode451

题目还好，常规思路就可以解决。以及表达式。

LeetCode451
基本思路
将字符串中出现的各个字母及其频率的映射保存到字典树中，修改字典树的比较规则，将按键比较改为按值比较。之后用迭代器将字符输出，每个字符输出的个数为以该字符为键对应的值。

方案1

使用表达式修改的比较规则，这种方式最为简洁。

代码

import java.util.Iterator;
import java.util.TreeMap;

class Solution {
    public static String frequencySort(String s) {
        TreeMap<Character,Integer> map = new TreeMap<>();
        for(int i = 0; i < s.length(); i ++){
            if(!map.containsKey(s.charAt(i)))
                map.put(s.charAt(i), 1);
            else
                map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
        }
        TreeMap<Character, Integer> reorder = new TreeMap<>((a, b) ->
                (map.get(b) - map.get(a)) == 0 ? a - b : (map.get(b) - map.get(a)));
        reorder.putAll(map);
        
        Iterator iter = reorder.keySet().iterator();
        StringBuilder res = new StringBuilder();
        while(iter.hasNext()){
            char c = (char)iter.next();
            for(int i = 0; i < map.get(c); i ++)
                res.append(c);
        }
        return res.toString();
    }
   
}

方案2

将比较在我们自己实现的数据结构中实现，用重新定义比较规则。

代码

import java.util.*;
class Solution {
    private static class Freq implements Comparable<Freq>{
        public char c;
        public int num;
        public Freq(char c, int n){
            this.c = c;
            this.num = n;
        }
        @Override
        public int compareTo(Freq s){
            return s.num - this.num;
        }
    }
    public static String frequencySort(String s) {
        int count[] = new int[256];
        for(int i = 0; i < s.length(); i ++)
            count[s.charAt(i)] ++;
        PriorityQueue<Freq> queue = new PriorityQueue<>();
        for(int i = 0; i < count.length; i ++){

            if(count[i] != 0)
                queue.add(new Freq((char)i, count[i]));
        }
        StringBuilder res = new StringBuilder();
        while(!queue.isEmpty()){
            Freq m = queue.poll();
            for(int i = 0; i < m.num; i ++)
                res.append(m.c);
        }
        return res.toString();
    }
    
}

方案3

与方案1相同，只是我们是显式修改的，改为按值比较。

代码

import java.util.*;
class Solution{
    static class myCompare implements Comparator<Character>{
        public TreeMap<Character,Integer> map;
        public myCompare(TreeMap<Character, Integer> map){
            this.map = map;
        }
        @Override
        public int compare(Character a, Character b){
            if(map.get(a) - map.get(b) > 0) return -1;//value从大到小
            else if(map.get(a) - map.get(b) < 0) return 1;
            else{
                return a - b;
            }     
        }
    }
    public static String frequencySort(String s) {
        TreeMap<Character,Integer> map = new TreeMap<>();
        for(int i = 0; i < s.length(); i ++){
            if(!map.containsKey(s.charAt(i)))
                map.put(s.charAt(i), 1);
            else
                map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
        }
        TreeMap res_map = new TreeMap<>(new myCompare(map));
        res_map.putAll(map);

        Iterator iter = res_map.keySet().iterator();
        List<Character> l = new ArrayList<>();
        StringBuilder res = new StringBuilder();
        while(iter.hasNext()){
            char c = (char)iter.next();
            for(int i = 0; i < map.get(c); i ++)
                res.append(c);
        }
        return res.toString();
    }
}