主題

LeetCode - 1189. Maximum Number of Balloons 解題心得

Not In My Back Yard | 2021-04-03 01:10:00 | 巴幣 2 | 人氣 78

題目連結:


題目意譯:
給定一個字串 text,你想要使用 text 中的字元來組成儘可能多的字詞 "balloon" 之實例。

你最多可以使用每個 text 中的某個字元一次。回傳最大的能被組出來的實例數。

限制:
1 ≦ text.length ≦ 10^4
text 只由小寫英文字母組成。



範例測資:
範例 1:
輸入: text = "nlaebolko"
輸出: 1

範例 2:
輸入: text = "loonbalxballpoon"
輸出: 2

範例 3:
輸入: text = "leetcode"
輸出: 0


解題思維:
掃過一次字串並統計 b 、 a 、 l 、 o 、 n 這五種字元的出現次數,假設依序出現次數為 B 、 A 、 L 、 O 、 N。

則我們可以看到可以形成多少個 "balloon" 之實例,是取決於裡面出現次數最少(l 跟 o 在該字詞重複了兩次,所以比較特別)的字元,即:
出現次數 = min(B, A, L ÷ 2, O ÷ 2, N)
由於上述的「÷」可能會產生小數點,因此我們這邊忽略小數點以後的值。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作