LeetCode 451根据字符出现的频率排序、LeetCode 228汇总区间

题目描述：
给定一个字符串 s ，根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。
返回 已排序的字符串 。如果有多个答案，返回其中任何一个。
示例 1:
输入: s = “tree”
输出: “eert”
解释: 'e’出现两次，'r’和’t’都只出现一次。
因此’e’必须出现在’r’和’t’之前。此外，"eetr"也是一个有效的答案。

示例 2:
输入: s = “cccaaa”
输出: “cccaaa”
解释: 'c’和’a’都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。

示例 3:
输入: s = “Aabb”
输出: “bbAa”
解释: 此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意’A’和’a’被认为是两种不同的字符。

• 时间复杂度O(n+klogk)【将字符按照出现频率排序需要 O(k log k)O(klogk) 的时间。】
• 空间复杂度：O(n + k)O(n+k)，其中 nn 是字符串 ss 的长度，kk 是字符串 ss 包含的不同字符的个数。空间复杂度主要取决于哈希表、列表和生成的排序后的字符串。

public String frequencySort(String s) {
        Map map = new HashMap<>();
        int l = s.length();
        for (int i = 0; i < l; i++) {   // 使用map存出现次数
            char c = s.charAt(i);
            int fre = map.getOrDefault(c, 0) + 1;
            map.put(c, fre);
        }
        List list = new ArrayList(map.keySet());
        Collections.sort(list, (a, b) -> map.get(b) - map.get(a));   // 使用list存字符并自定义排序
        StringBuffer sb = new StringBuffer();   // 新建Stringbuffer提取字符和频率存放答案
        for (int i = 0; i < list.size(); i++) {
            char c = list.get(i);
            int fre = map.get(c);
            for (int j = 0; j < fre; j++) {
                sb.append(c);
            }
        }
        return sb.toString();
    }

• 遍历字符串，统计每个字符出现的频率，同时记录最高频率maxFreq；
• 创建桶，存储从1到maxFreq 的每个出现频率的字符；
• 按照出现频率从大到小的顺序遍历桶，对于每个出现频率，获得对应的字符，然后将每个字符按照出现频率拼接到排序后的字符串。

public String buckets_frequencySort(String s) {
        Map map = new HashMap<>();
        int maxFre = 0;
        for (int i = 0; i < s.length(); i++) {   // 统计出最多频率
            char ch = s.charAt(i);
            int fre = map.getOrDefault(ch, 0) + 1;
            map.put(ch, fre);
            maxFre = Math.max(maxFre, fre);
        }
        StringBuffer[] buckets = new StringBuffer[maxFre + 1];   // 此处从0-maxFre省事，方便最后可以直接从maxFre-1遍历
        for (int i = 0; i <= maxFre; i++) {   // 初始化buckets
            buckets[i] = new StringBuffer();
        }
        for (Map.Entry entry : map.entrySet()) {   // 将从1到maxFre的字符装入桶中（entrySet不含重复key）
            char ch = entry.getKey();
            int fre = entry.getValue();
            buckets[fre].append(ch);
        }
        StringBuffer sb = new StringBuffer();
        for (int i = maxFre; i > 0; i--) {
            StringBuffer bucket = buckets[i];
            for (int j = 0; j < bucket.length(); j++) {   // 长度为i的bucket中可能不止一种字符
                for (int k = 0; k < i; k++) {   // 多次存放相同字符串的所有同一单个字符charAt(j)
                    sb.append(bucket.charAt(j));
                }
            }
        }
        return sb.toString();
    }

题目描述：
给定一个 无重复元素 的 有序 整数数组 nums 。
返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。
列表中的每个区间范围 [a,b] 应该按如下格式输出：
“a->b” ，如果 a != b
“a” ，如果 a == b

示例 1：
输入：nums = [0,1,2,4,5,7]
输出：[“0->2”,“4->5”,“7”]
解释：区间范围是：
[0,2] --> “0->2”
[4,5] --> “4->5”
[7,7] --> “7”

示例 2：
输入：nums = [0,2,3,4,6,8,9]
输出：[“0”,“2->4”,“6”,“8->9”]
解释：区间范围是：
[0,0] --> “0”
[2,4] --> “2->4”
[6,6] --> “6”
[8,9] --> “8->9”

public List summaryRanges(int[] nums) {
        List ret = new ArrayList<>();
        int i = 0;
        int n = nums.length;
        while (i < n) {
            int low = i;
            i++;
            while (i < n && nums[i] == nums[i - 1] + 1) {   // 如果此处的i==i-1处+1，继续while
                i++;
            }
            int high = i - 1;
            StringBuffer temp = new StringBuffer(Integer.toString(nums[low]));   // 存low
            if (low < high) {
                temp.append("->");
                temp.append(Integer.toString(nums[high]));   // 存high
            }
            ret.add(temp.toString());   // StringBuffer有函数toString()可以转为String
        }
        return ret;
    }