這是小川的第416次更新糟秘，第449篇原創(chuàng)
看題和準(zhǔn)備
今天介紹的是LeetCode算法題中Easy級(jí)別的第267題（順位題號(hào)是1189）亮曹。給定一個(gè)字符串文本严沥，使用文本字符來構(gòu)成單詞"balloon"的盡可能多的實(shí)例焕盟。每個(gè)字符最多可以在文本中使用一次夜畴。返回可以形成的最大實(shí)例數(shù)铝阐。
例如：
輸入：text = "nlaebolko"
輸出：1
輸入：text = "loonbalxballpoon"
輸出：2
輸入：text = "leetcode"
輸出：0
約束：
- 1 <= text.length <= 10^4
- 文本字符串僅包含小寫英文字母址貌。
第一種解法
題目的意思是要在一個(gè)給定的字符串中，找到能夠組成字符串"balloon"的最大字符對(duì)數(shù)徘键，本質(zhì)上和木桶裝水的容量由短板決定類似练对。
直接遍歷text字符串中的字符，對(duì)字母a吹害、b螟凭、l、n它呀、o的出現(xiàn)次數(shù)計(jì)數(shù)螺男，因?yàn)閘和o是需要兩個(gè)，在計(jì)數(shù)完后纵穿，需要對(duì)l和o的次數(shù)除2下隧，然后比較5個(gè)字母出現(xiàn)次數(shù)的最小值，因?yàn)橹挥谐霈F(xiàn)次數(shù)最小的那個(gè)字母才能最終決定組成多少個(gè)"balloon"谓媒。
public int maxNumberOfBalloons(String text) {
if (text == "" || text.length() < 7) {
return 0;
}
int A = 0, B = 0, L = 0, O = 0, N = 0;
int len = text.length();
for (int i=0; i<len; i++) {
if (text.charAt(i) == 'a') {
A++;
} else if (text.charAt(i) == 'b') {
B++;
} else if (text.charAt(i) == 'l') {
L++;
} else if (text.charAt(i) == 'n') {
N++;
} else if (text.charAt(i) == 'o') {
O++;
}
}
L /= 2;
O /= 2;
int min = Math.min(A, B);
min = Math.min(min, N);
if (min == 0) {
return 0;
}
if (L !=0 && O != 0) {
min = Math.min(min, L);
min = Math.min(min, O);
return min;
}
return 0;
}
第二種解法
針對(duì)第一種解法里淆院，在循環(huán)中判斷字母的方式，可以換成使用一個(gè)長(zhǎng)度為26的int數(shù)組句惯，根據(jù)26個(gè)英文字母的順序土辩，直接從數(shù)組中取值即可支救，最后返回5個(gè)數(shù)中的最小值。
public int maxNumberOfBalloons2(String text) {
if (text == "" || text.length() < 7) {
return 0;
}
int A = 0, B = 0, L = 0, O = 0, N = 0;
int len = text.length();
int[] arr = new int[26];
for (int i=0; i<len; i++) {
arr[text.charAt(i)-'a']++;
}
A = arr[0];
B = arr[1];
L = arr[11]/2;
N = arr[13];
O = arr[14]/2;
int min = Math.min(A, B);
min = Math.min(min, N);
min = Math.min(min, L);
min = Math.min(min, O);
return min;
}
第三種解法
針對(duì)第二種解法拷淘，我們可以將5個(gè)局部變量也省略掉搂妻，畢竟只是比較最小值，直接去數(shù)組里取就行辕棚。
public int maxNumberOfBalloons3(String text) {
if (text == "" || text.length() < 7) {
return 0;
}
int len = text.length();
int[] arr = new int[26];
for (int i=0; i<len; i++) {
arr[text.charAt(i)-'a']++;
}
int min = Math.min(arr[0], arr[1]); //a b
min = Math.min(min, arr[13]); // n
min = Math.min(min, arr[11]/2); // l
min = Math.min(min, arr[14]/2); // o
return min;
}
小結(jié)
算法專題目前已更新LeetCode算法題文章273+篇，公眾號(hào)對(duì)話框回復(fù)【數(shù)據(jù)結(jié)構(gòu)與算法】邓厕、【算法】逝嚎、【數(shù)據(jù)結(jié)構(gòu)】中的任一關(guān)鍵詞，獲取系列文章合集详恼。
以上就是全部?jī)?nèi)容补君，如果大家有什么好的解法思路、建議或者其他問題昧互，可以下方留言交流挽铁，點(diǎn)贊、留言敞掘、在看就是對(duì)我最大的回報(bào)和支持叽掘！
