讨论/题目交流/🏆 第 185 场力扣周赛/
🏆 第 185 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛】

image.png

3 分 - 重新格式化字符串
4 分 - 点菜展示表
5 分 - 数青蛙
6 分 - 生成数组

展开讨论

重新格式化字符串

思路

  1. 分开统计字母和数字的个数
  2. 将个数多的放在前面
  3. 如果个数相差超过 1 ,就无法重新排列

答题

    string reformat(string s) 
    {
        vector<char> vc_a;
        vector<char> vc_b;
        for (auto c : s)
        {
            if (isalpha(c))
            {
                vc_a.push_back(c);
            }
            if (isdigit(c))
            {
                vc_b.push_back(c);
            }
        }
        if (vc_a.size() < vc_b.size())
        {
            swap(vc_a, vc_b);
        }
        if (vc_a.size() - vc_b.size() > 1) return {};

        string ans = "";
        for (int i = 0; i < vc_a.size(); i++)
        {
            ans += vc_a[i];
            if (i >= vc_b.size()) continue;
            ans += vc_b[i];
        }
        return ans;
    }

点菜展示表

思路

  1. 从最后要展示的时候思考
  2. 标题行包含:Table, food1, food2, ...
  3. 首先需要一个 set<string> foodList 保存所有餐品名称
  4. 然后还需要一个按照桌子保存的 map<int, map<string, int>> tableList

    即:map<桌号,map<餐品名称,数量>>

  5. 将输入按照这个格式存储
  6. 转成输出格式

图解

图片.png

答题

    vector<vector<string>> displayTable(vector<vector<string>>& orders) 
    {
        set<string> foodList;
        map<int, map<string, int>> tableList;

        for (auto& o : orders)
        {
            foodList.insert(o[2]);
            tableList[stoi(o[1])][o[2]]++;
        }

        vector<vector<string>> ans;
        vector<string> title = { "Table" };
        for (auto& s : foodList)
        {
            title.push_back(s);
        }
        ans.push_back(title);
        for (auto& p : tableList)
        {
            vector<string> t = { to_string(p.first) };
            for (auto& s : foodList)
            {
                t.push_back(to_string(p.second[s]));
            }
            ans.push_back(t);
        }

        return ans;
    }

数青蛙

思路

  1. 因为字母混杂在一起,所以要按照正确的行进顺序区分
  2. 为了方便编码,先制作两个互相转换的映射
    21. const string croak = "croak"; 方便索引对字母
    22. unordered_map<char, int> dic; 方便字母对索引
  3. 先简化思考,假设每个 croak 都是一直新青蛙喊的,先验证喊叫声是否合法
    31. 使用一个 vector<int> cnt 记录这个青蛙喊到哪个字母了
    32. 当开始喊第一个字母 c 的时候,记录 cnt[0]++ (因为 dic['c'] == 0)
    33. 当它喊第二个字母 r 的时候,把 cnt[0]-- 然后 cnt[1]++
    34. 通过这样的记录,当发现喊的字母的前一步并没有人正在喊时,就说明不合法
    35. 最后当所有字母都喊完,除了最后一个字母 cnt[4] (dic['k'] == 4)之外,其他字母还有残留,也不合法
  4. 通过上一步操作,可以验证所有 croak 都是顺序出现,并且完整
  5. 接下来,将青蛙合并,求出最小青蛙数
    51. 加入一个开始计数 start 表示已经开始了几只青蛙
    52. 结束计数就是 cnt[4]
    53. 当有新青蛙开始叫的时候,就可以 ans = max(ans, start - cnt[4])

图解

答题

    int minNumberOfFrogs(string croakOfFrogs) 
    {
        const string croak = "croak";
        unordered_map<char, int> dic;
        for (int i = 0; i < croak.size(); i++)
        {
            dic[croak[i]] = i;
        }

        vector<int> cnt(croak.size(), 0);
        int ans = 0;
        int start = 0;
        for (auto c : croakOfFrogs)
        {
            if (dic[c] == 0 || cnt[dic[c] - 1] > 0)
            {
                if (dic[c] != 0)
                {
                    cnt[dic[c] - 1]--;
                }
                start += (dic[c] == 0);
                cnt[dic[c]]++;
                ans = dic[c] == 0 ? max(ans, start - cnt[4]) : ans;
                continue;
            }
            return -1;
        }

        for (int i = 0; i < cnt.size() - 1; i++)
        {
            if (cnt[i] != 0) return -1;
        }
        return ans;
    }

生成数组

啥时候才能学好 dp
啥时候才能学好排列组合
菜哭!

致谢

感谢您的观看,希望对您有帮助,欢迎热烈的交流!

如果感觉还不错就点个赞吧~

这是 我的leetcode ,帮助我收集整理题目,可以方便的 visual studio 调试,欢迎关注,star

5
展开全部 25 讨论