删除字符使频率相同
难度:
标签:
题目描述
代码结果
运行时间: 26 ms, 内存: 16.0 MB
/*
* 思路:
* 1. 使用流处理计算字母频率。
* 2. 统计频率分布。
* 3. 判断是否满足题目要求的频率情况。
*/
import java.util.Map;
import java.util.stream.Collectors;
public class SolutionStream {
public boolean equalFrequency(String word) {
Map<Character, Long> freqMap = word.chars()
.mapToObj(c -> (char) c)
.collect(Collectors.groupingBy(c -> c, Collectors.counting()));
Map<Long, Long> countMap = freqMap.values().stream()
.collect(Collectors.groupingBy(c -> c, Collectors.counting()));
if (countMap.size() == 1 && countMap.containsKey(1L)) {
return true;
}
if (countMap.size() == 2) {
long minFreq = countMap.keySet().stream().min(Long::compare).orElse(0L);
long maxFreq = countMap.keySet().stream().max(Long::compare).orElse(0L);
if (minFreq == 1 && countMap.get(minFreq) == 1) {
return true;
}
if (maxFreq == minFreq + 1 && countMap.get(maxFreq) == 1) {
return true;
}
}
return false;
}
}
解释
方法:
这个题解的核心思路是尝试删除字符串中任一字符,然后检查剩余字符的频率是否一致。首先,利用Counter统计字符串中每个字符的出现频率,然后将这些频率排序。之后,算法尝试两种可能的删除方式:1)删除出现频率最少的字符后检查剩余字符的频率是否一致;2)删除出现频率最多的字符后检查剩余字符的频率是否一致。如果其中任一操作后所有字符的频率都相同,则返回true,否则返回false。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么题解中提到尝试删除频率最少和最多的字符,而没有考虑删除其他位置的字符?
▷🦆
在恢复初始状态并尝试删除最大频率的字符后,是否需要重新排序lc列表?
▷🦆
当删除一个字符后,如果剩余字符的频率不完全一致但差异很小(例如一种频率多一个),这种情况下算法是否还能正确处理?
▷🦆
算法在检查剩余字符频率是否相同时使用了filter函数和set函数,这种方法在何种情况下可能会导致错误判断?
▷