删除字符使频率相同【LC2423】
给你一个下标从 0 开始的字符串
word，字符串只包含小写英文字母。你需要选择 一个 下标并 删除 下标处的字符，使得word中剩余每个字母出现 频率 相同。如果删除一个字母后，
word中剩余所有字母的出现频率都相同，那么返回true，否则返回false。注意：
- 字母
x的 频率 是这个字母在字符串中出现的次数。- 你 必须 恰好删除一个字母，不能一个字母都不删除。
通过率好低的简单题
暴力枚举
-
思路
暴力枚举可以删除的字符，判断删除后频率是否相同
-
实现文章来源地址https://www.toymoban.com/news/detail-429294.html
class Solution { public boolean equalFrequency(String word) { int[] count = new int[26]; int n = word.length(); for (int i = 0; i < n; i++){ int c = word.charAt(i) - 'a'; count[c]++; } Arrays.sort(count); int i = 0; while (count[i] == 0){ i++; } for (int j = i; j < 26; j++){ count[j]--; if (isSame(count, i)){ return true; } count[j]++; } return false; } public boolean isSame(int[] count, int i){ int val = 0; while (i < 26 && count[i] == 0){ i++; } for (int j = i + 1; j < 26; j++){ if (count[j] != 0 && count[j] != count[i]){ return false; } } return true; } }- 复杂度
- 时间复杂度： O ( n + C l o g C + C ) O(n+ClogC+ C) O(n+ClogC+C)，本题中C为字符集大小26
- 空间复杂度： O ( C ) O(C) O(C)
- 复杂度
特殊判断
-
思路
如果删除一个字符后剩下的频率相同，那么情况有以下几种
- 字符串中只有一种字符
- 字符串中所有字母出现次数都为1
- 字符串中有一个字母出现1次，其他字母出现次数相同
- 字符串中有一个字母多出现一次，其他字母出现次数相同
因此可以统计字符的出现次数，然后进行升序排序，判断以上情况是否成立文章来源：https://www.toymoban.com/news/detail-429294.html
-
实现
class Solution { public boolean equalFrequency(String word) { // 只有一种字母 // 所有字母出现次数都为1 // 有一个字母出现1次 其他字母出现次数相同 // 有一个字母多出现一次 int[] count = new int[26]; int n = word.length(); for (int i = 0; i < n; i++){ int c = word.charAt(i) - 'a'; count[c]++; } Arrays.sort(count); int i = 0; while (i < 26 && count[i] == 0){ i++; } return i == 25 || count[25] == 1 || (count[i] == 1 && count[i + 1] == count[25]) || (count[i] == count[24] && (count[24] + 1 == count[25])); } }- 复杂度
- 时间复杂度： O ( n + C l o g C ) O(n+ClogC) O(n+ClogC)，本题中C为字符集大小26
- 空间复杂度： O ( C ) O(C) O(C)
- 复杂度
到了这里，关于【每日一题Day191】LC2423删除字符使频率相同 | 枚举 分类讨论的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
