【每日一题Day191】LC2423删除字符使频率相同 | 枚举 分类讨论

简介: 【每日一题Day191】LC2423删除字符使频率相同 | 枚举 分类讨论

删除字符使频率相同【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;
    }
}

image.png

特殊判断

  • 思路如果删除一个字符后剩下的频率相同,那么情况有以下几种
  • 字符串中只有一种字符
  • 字符串中所有字母出现次数都为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]));
    }
}

image.png

目录
打赏
0
0
0
0
5
分享
相关文章
|
9月前
【每日一题Day201】LC2436有效时间的数目 | 乘法原理 枚举
【每日一题Day201】LC2436有效时间的数目 | 乘法原理 枚举
69 2
|
9月前
【每日一题Day199】LC1010总持续时间可被 60 整除的歌曲 | 哈希表
【每日一题Day199】LC1010总持续时间可被 60 整除的歌曲 | 哈希表
56 1
|
9月前
【每日一题Day159】LC1638统计只差一个字符的子串数目 | 枚举
【每日一题Day159】LC1638统计只差一个字符的子串数目 | 枚举
47 0
|
9月前
【每日一题Day155】LC1630等差子数组 | 枚举+排序
【每日一题Day155】LC1630等差子数组 | 枚举+排序
60 0
|
9月前
|
【每日一题Day131】LC1144递减元素使数组呈锯齿状 | 贪心+枚举
【每日一题Day131】LC1144递减元素使数组呈锯齿状 | 贪心+枚举
61 0
|
9月前
【每日一题Day278】LC2500删除每行中的最大值 | 排序+模拟
【每日一题Day278】LC2500删除每行中的最大值 | 排序+模拟
60 0
|
9月前
【每日一题Day371】LC2586统计范围内的元音字符串数 | 模拟
【每日一题Day371】LC2586统计范围内的元音字符串数 | 模拟
72 1
|
9月前
【每日一题Day217】LC2451差值数组不同的字符串 | 枚举+变量记录
【每日一题Day217】LC2451差值数组不同的字符串 | 枚举+变量记录
54 0
|
9月前
【每日一题Day152】LC1012至少有1位重复的数字 | 数位dp
【每日一题Day152】LC1012至少有1位重复的数字 | 数位dp
64 0
|
9月前
【每日一题Day308】LC57插入区间 | 模拟
【每日一题Day308】LC57插入区间 | 模拟
55 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等