[Day 8] Leetcode 1189. Maximum Number of Balloons (C++)

前言

飙车回家又是11点多了，发现今天的daily challenge是easy就顺手解个吧！题目在这边：1189. Maximum Number of Balloons

想法

这就真的蛮简单没什麽好说的XD 但我们可以做的就是用尽量少的时间跟空间~
看到这题目应该很明显就是我们需要去统计各个字母出现的次数，然後去求5个字母的最小次数(l跟o要除以2)
有几种直觉做法：

• 次数表: 我们可以跟昨天一样，建立一个大小为62的vector，用text[i]-'a'去存每个字母的出现次数
  针对这点，因为我们只care balloon这 'b','a','l','o','n'这五个字母，所以我们可以空间优化为只存5个字母就好，至於怎麽存，只有5个可以直接写死，也是可以用unordered map来存比较好看一点(cnt[i]++)，不过这空间有没有省到就难说了。

btw每次遇到这种计算频率就会很想念python的counter可以秒杀~ 如果用python的话强力推荐有很多人实作好的function可以直接用，而且时间都还比自己慢慢算快很多；不过python跟C++的执行速度也不在同一个等级就是了XD

• 次数计算：我们可以用STL的count (count(s.begin(), s.end(), 'a');) 来直接计算字母出现的频率，但就时间而言，每次的count等於都要去扫一遍整个string，5个字母都要扫就需要扫五次，所以还是手动扫过一轮直接一起计算就好。
  完整code如下：

class Solution {
public:
    int maxNumberOfBalloons(string text) {
        // record frequency only for 'b','a','n','l','o'
        vector<int> cnt(5);
        char tmp;
        for(int i=0;i<text.length();++i){
            tmp = text[i];
            if(tmp=='b'){
                cnt[0]++;
            }
            else if(tmp=='a'){
                cnt[1]++;
            }else if(tmp=='n'){
                cnt[2]++;
            }else if(tmp=='l'){
                cnt[3]++;
            }else if(tmp=='o'){
                cnt[4]++;
            }
        }
        return min({cnt[0], cnt[1], cnt[2], cnt[3]/2, cnt[4]/2});
    }
};

也可以像我上面提到的unordered_map写法

class Solution {
public:
    int maxNumberOfBalloons(string text) {
        // record frequency only for 'b','a','n','l','o'
        unordered_map<char, int> cnt;
        char tmp;
        for(int i=0;i<text.length();++i){
            tmp = text[i];
            if(tmp=='b' || tmp=='a' || tmp=='l' || tmp=='o' || tmp=='n'){
                cnt[tmp]++;
            }
        }
        return min({cnt['b'], cnt['l'], cnt['o']/2, cnt['l']/2, cnt['n']});
        
    }
};

第二个这个写法，在最後取cnt['b']...的时候可能会比较快~ 不过这有待更多查证实验了

结语

整个code不是很美观，但是就求一个(自己觉得?)快XD 至少除了写完可以accept都可以多思考一下有哪边是可以优化的地方~
当然如果要写的general就不用写死这麽多条件，直接把26个字母用昨天计算次数表的方式来存就好，code可以整个简洁很多
希望明天的题目可以是easy~medium但是有梗的XD 不然内容好空虚啊
然後可以早点下班回来慢慢写(结语怎麽变成在许愿)~