删除字符使频率相同【LC2423】
给你一个下标从 0 开始的字符串
word，字符串只包含小写英文字母。你需要选择 一个 下标并 删除 下标处的字符，使得word中剩余每个字母出现 频率 相同。如果删除一个字母后，
word中剩余所有字母的出现频率都相同，那么返回true，否则返回false。注意：
- 字母
x的 频率 是这个字母在字符串中出现的次数。 - 你 必须 恰好删除一个字母，不能一个字母都不删除。
通过率好低的简单题
暴力枚举
- 思路
暴力枚举可以删除的字符，判断删除后频率是否相同 - 实现
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; } }
特殊判断
- 思路如果删除一个字符后剩下的频率相同，那么情况有以下几种
- 字符串中只有一种字符
- 字符串中所有字母出现次数都为1
- 字符串中有一个字母出现1次，其他字母出现次数相同
- 字符串中有一个字母多出现一次，其他字母出现次数相同
- 因此可以统计字符的出现次数，然后进行升序排序，判断以上情况是否成立
- 实现
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])); } }
