刪除字符使頻率相同【LC2423】
給你一個(gè)下標(biāo)從 0 開始的字符串
word，字符串只包含小寫英文字母。你需要選擇 一個(gè) 下標(biāo)并 刪除 下標(biāo)處的字符，使得word中剩余每個(gè)字母出現(xiàn) 頻率 相同。如果刪除一個(gè)字母后，
word中剩余所有字母的出現(xiàn)頻率都相同，那么返回true，否則返回false。注意：
- 字母
x的 頻率 是這個(gè)字母在字符串中出現(xiàn)的次數(shù)。- 你 必須 恰好刪除一個(gè)字母，不能一個(gè)字母都不刪除。
通過率好低的簡單題
暴力枚舉
-
思路
暴力枚舉可以刪除的字符，判斷刪除后頻率是否相同
-
實(shí)現(xiàn)文章來源地址http://www.zghlxwxcb.cn/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; } }- 復(fù)雜度
- 時(shí)間復(fù)雜度： O ( n + C l o g C + C ) O(n+ClogC+ C) O(n+ClogC+C)，本題中C為字符集大小26
- 空間復(fù)雜度： O ( C ) O(C) O(C)
- 復(fù)雜度
特殊判斷
-
思路
如果刪除一個(gè)字符后剩下的頻率相同，那么情況有以下幾種
- 字符串中只有一種字符
- 字符串中所有字母出現(xiàn)次數(shù)都為1
- 字符串中有一個(gè)字母出現(xiàn)1次，其他字母出現(xiàn)次數(shù)相同
- 字符串中有一個(gè)字母多出現(xiàn)一次，其他字母出現(xiàn)次數(shù)相同
因此可以統(tǒng)計(jì)字符的出現(xiàn)次數(shù)，然后進(jìn)行升序排序，判斷以上情況是否成立文章來源：http://www.zghlxwxcb.cn/news/detail-429294.html
-
實(shí)現(xiàn)
class Solution { public boolean equalFrequency(String word) { // 只有一種字母 // 所有字母出現(xiàn)次數(shù)都為1 // 有一個(gè)字母出現(xiàn)1次 其他字母出現(xiàn)次數(shù)相同 // 有一個(gè)字母多出現(xiàn)一次 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])); } }- 復(fù)雜度
- 時(shí)間復(fù)雜度： O ( n + C l o g C ) O(n+ClogC) O(n+ClogC)，本題中C為字符集大小26
- 空間復(fù)雜度： O ( C ) O(C) O(C)
- 復(fù)雜度
到了這里，關(guān)于【每日一題Day191】LC2423刪除字符使頻率相同 | 枚舉 分類討論的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
