title | date | draft | categories | tags | author | showToc | TocOpen | hidemeta | comments | description | canonicalURL | disableShare | disableHLJS | hideSummary | searchHidden | ShowReadingTime | ShowBreadCrumbs | ShowPostNavLinks | ShowWordCount | ShowRssButtonInSectionTermList | UseHugoToc | editPost | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
LeetCode Biweekly Contest 89 |
2022-10-03 01:21:46 +0800 |
false |
|
|
Me |
true |
false |
false |
true |
LeetCode Biweekly Contest 89 |
false |
false |
false |
true |
true |
true |
true |
true |
true |
true |
|
2423. Remove Letter To Equalize Frequency
You are given a 0-indexed string word, consisting of lowercase English letters. You need to select one index and remove the letter at that index from word so that the frequency of every letter present in word is equal.
Return true if it is possible to remove one letter so that the frequency of all letters in word are equal, and false otherwise.
Note:
The frequency of a letter x is the number of times it occurs in the string. You must remove exactly one letter and cannot chose to do nothing.
Constraints:
2 <= word.length <= 100 word consists of lowercase English letters only.
- 字串長度 2..100
- 元素僅會出現 a..z
將字串轉成字元陣列,從頭開始遍歷,計算整個陣列不含當前元素,每個字元出現次數,如果次數相等,則回傳 true
- each_char 轉成陣列
- 扣除當前元素,用 hash 計算字母出現次數
- 取出 hash 的所有 value,去除零後如果只剩一種數字,即為次數相等,回傳
true
- 迴圈跑完未回傳
true
,回傳false
時間複雜度:O(n^2)
# @param {String} word
# @return {Boolean}
def equal_frequency(word)
word.each_char do |char|
frequency = { char => -1 }
word.each_char do |c|
if frequency[c]
frequency[c] += 1
else
frequency[c] = 1
end
end
return true if frequency.values.reject(&:zero?).uniq.size == 1
end
false
end
- 先求出所有字母出現次數 -> Array(frequency_of_letter)
- 判斷 次數-1 後, 有無符合題目要求
時間複雜度:O(n^2)
def equal_frequency(word)
frequency = 'a'.upto('z').map { |char| word.count(char) }.reject(&:zero?)
frequency.each_index do |i|
frequency[i] -= 1
return true if frequency.reject(&:zero?).uniq.size == 1
frequency[i] += 1
end
false
end
- 次數求出後,分不同情境判斷
次數 >= 3 種 ==>> false
次數 == 1 種 ==>> 等於 1 => true, 只有一種字母 => true, 其他 false
次數 == 2 種 ==>> 分別 -1,判斷符不符合題目要求
時間複雜度:O(n)
def equal_frequency(word)
frequency = 'a'.upto('z').map { |char| word.count(char) }.reject(&:zero?)
return true if frequency.size == 1
return true if frequency.uniq.size == 1 && frequency.uniq.last == 1
return false if frequency.uniq.size >= 3
frequency.sort!
frequency[0] -= 1
return true if frequency.reject(&:zero?).uniq.size == 1
frequency[0] += 1
frequency[-1] -= 1
return frequency.reject(&:zero?).uniq.size == 1
end