1189. Maximum Number of Balloons - Easy

前往題目

想法

• 用hashmap紀錄頻率
• 疊代balloon直到遇到字母數量為0或是null

思路

Code

自己的解

class Solution {
    public int maxNumberOfBalloons(String text) {
        Map<Character, Integer> map = new HashMap();
        String target = "balloon";
        int res = 0;

        // Count each character
        for (char c : text.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        // Find ballons
        while (true) {
            // iterate "balloon"
            for (char c : target.toCharArray()) {

                // Until the character does not exist
                // or it's count is 0 already
                if (map.get(c) == null || map.get(c) == 0) return res;

                // Update count
                map.put(c, map.get(c) - 1);
            }
            ++res;
        }
    }
}

Neetcode給出了另一個種思路

1. 紀錄text和"balloon"的每個字母個數
2. 疊代b a l l o o n，每次都取res或是text[c] // balloon[c]看誰比較小

簡單來說就是，如果b只有一個，那就不可能會湊成兩個以上balloon，除法就是為了看最多能湊幾個

class Solution {
    public int maxNumberOfBalloons(String text) {
        HashMap<Character, Integer> balloon = new HashMap<>();
        HashMap<Character, Integer> countText = new HashMap<>();
        
        char[] balloonArray = "balloon".toCharArray();
        
        for (char c : balloonArray) {
            if (balloon.containsKey(c)) {
                balloon.put(c,balloon.get(c)+1);
            } else {
                balloon.put(c,1);
            }
        }
        
        char[] countTextArray = text.toCharArray();
        
        for (char c : countTextArray) {
            if (countText.containsKey(c)) {
                countText.put(c,countText.get(c)+1);
            } else {
                countText.put(c,1);
            }
        }
        
        int res = text.length();
        for (Character c : balloon.keySet()) {
            res = Math.min(res,countText.getOrDefault(c,0) / balloon.get(c));
        }
    
        return res;
    }
}