[leetcode #1189] Maximum Number of Balloons
3586 ワード
Problem
Given a string text, you want to use the characters of text to form as many instances of the word "balloon"as possible.
You can use each character in text at most once. Return the maximum number of instances that can be formed.
Example 1:
Input: text = "nlaebolko"
Output: 1
Example 2:Input: text = "loonbalxballpoon"
Output: 2
Example 3:Input: text = "leetcode"
Output: 0
Constraints:・ 1 <= text.length <= 10⁴
・ text consists of lower case English letters only.
Idea
これは、指定した文字列の文字を抽出することによって、どのくらいの「風船」を作成できるかを決定する問題です.「風船」を構成する文字b,a,l,o,nの数だけ数えて、その文字の最低数を返すだけです.lとoは2つ必要なので、合計の1/2として計算します.
アルゴリズムは以下の通りです.
Solution
class Solution {
public int maxNumberOfBalloons(String text) {
Map<Character, Integer> map = new HashMap<>();
for (int i =0; i < text.length(); i++) {
if (!map.containsKey(text.charAt(i))) {
map.put(text.charAt(i), 1);
} else {
int val = map.get(text.charAt(i));
map.put(text.charAt(i), val+1);
}
}
String balloon = "balon";
int res = Integer.MAX_VALUE;
for (int i=0; i < balloon.length(); i++) {
if (!map.containsKey(balloon.charAt(i)))
return 0;
if (balloon.charAt(i) == 'l' || balloon.charAt(i) == 'o') {
res = Math.min(res, map.get(balloon.charAt(i))/2);
} else
res = Math.min(res, map.get(balloon.charAt(i)));
}
return res;
}
}
mapを使用する必要がなく、直感的にリリースするとパフォーマンスが向上します.class Solution {
public int maxNumberOfBalloons(String text) {
int bCount = 0, aCount = 0, lCount = 0, oCount = 0, nCount = 0;
// Count the frequencey of all the five characters
for (int i = 0; i < text.length(); i++) {
if (text.charAt(i) == 'b') {
bCount++;
} else if (text.charAt(i) == 'a') {
aCount++;
} else if (text.charAt(i) == 'l') {
lCount++;
} else if (text.charAt(i) == 'o') {
oCount++;
} else if (text.charAt(i) == 'n') {
nCount++;
}
}
// Find the potential of each character.
// Except for 'l' and 'o' the potential is equal to the frequency.
lCount = lCount / 2;
oCount = oCount / 2;
// Find the bottleneck.
return Math.min(bCount, Math.min(aCount, Math.min(lCount, Math.min(oCount, nCount))));
}
}
Reference
https://leetcode.com/problems/maximum-number-of-balloons/
Reference
この問題について([leetcode #1189] Maximum Number of Balloons), 我々は、より多くの情報をここで見つけました https://velog.io/@timevoyage/leetcode-1189-Maximum-Number-of-Balloonsテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol