LeetCode 451根据字符出现的频率排序
题目描述：
给定一个字符串 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’被认为是两种不同的字符。
一、使用哈希表记录每个字符出现的频率，将字符去重后存入列表，再将列表中的字符按照频率list存字符并联系map对列表降序排序。最后使用线程安全的Stringbuffer提取字符和频率来存放答案，输出StringBuffer.toString()
- 时间复杂度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<Character, Integer> 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<Character> list = new ArrayList<Character>(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();
}
二、桶排序使用StringBuffer[] buckets = new StringBuffer[maxFre + 1]次数和字符;【由于每个字符在字符串中出现的频率存在上限，因此可以使用桶排序的思想，根据出现次数生成排序后的字符串。具体做法如下：】
- 遍历字符串，统计每个字符出现的频率，同时记录最高频率maxFreq；
- 创建桶，存储从1到maxFreq 的每个出现频率的字符；
- 按照出现频率从大到小的顺序遍历桶，对于每个出现频率，获得对应的字符，然后将每个字符按照出现频率拼接到排序后的字符串。
可通过完整代码：
public String buckets_frequencySort(String s) {
Map<Character, Integer> 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<Character, Integer> 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();
}
LeetCode 228汇总区间
题目描述：
给定一个 无重复元素 的 有序 整数数组 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”
一、一次遍历，维护下标low和high记录区间的起点和终点，while循环i<n，其中low=i记录，i++判断i<n&&nums[i] == nums[i-1]+1；如果否，high=i-1，这样low==high不满足加"->"的条件了
可运行完整代码：
public List<String> summaryRanges(int[] nums) {
List<String> 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;
}
