讨论/题目交流/🐱 第 23 场夜喵双周赛/
🐱 第 23 场夜喵双周赛

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

image.png

3 分 - 统计最大组的数目
5 分 - 构造 K 个回文字符串
5 分 - 圆和矩形是否有重叠
6 分 - 做菜顺序

展开讨论

统计最大组的数目

思路

  1. 按照题目要求计算分组,按照分组存
  2. 数一下

答题

    int f(int x)
    {
        int cnt = 0;
        while (x != 0)
        {
            cnt += (x % 10);
            x /= 10;
        }
        return cnt;
    }

    int countLargestGroup(int n) 
    {
        unordered_map<int, int> mp;
        for (int i = 1; i <= n; i++)
        {
            mp[f(i)]++;
        }

        int ans = 0;
        int cnt = 0;
        for (auto it : mp)
        {
            if (cnt < it.second)
            {
                cnt = it.second;
                ans = 0;
            }
            ans += (cnt == it.second);
        }
        return ans;
    }

构造 K 个回文字符串

思路

  1. 构成回文串的特点是, 1 个字母可以构成回文串,2 个相同的字母可以构成回文串
  2. 所以只要想一下单个(奇数个)字母怎么处理
  3. 对字母计数
  4. 判断奇数个字母的数量

答题

    bool canConstruct(string s, int k) 
    {
        if (s.size() < k) return false;
        vector<int> cnt(26, 0);
        for (auto c : s)
        {
            cnt[c - 'a']++;
        }

        int odd = 0;
        for (auto x : cnt)
        {
            odd += (x % 2 == 1);
        }

        return odd <= k;
    }

圆和矩形是否有重叠

查看详细

图片.png

思路

  1. 计算矩形的中心点 (x0, y0)
  2. 计算矩形的中心点到圆点的向量 p
    21. 通过绝对值,将圆形转移至第一象限
  3. 计算矩形的中心点到矩形右上角的向量 q
  4. 通过 p - q 得到从矩形右上角到圆点的向量 u
    41. 将分量为负数设置为 0
  5. 比较 u 和圆形半径 radius 的长度

答题

    bool checkOverlap(int radius, int x_center, int y_center, int x1, int y1, int x2, int y2) 
    {
        double x0 = (x1 + x2) / 2.0;
        double y0 = (y1 + y2) / 2.0;

        vector<double> p = { abs(x_center - x0) , abs(y_center - y0) };
        vector<double> q = { x2 - x0, y2 - y0 };
        
        vector<double> u = { max(p[0] - q[0], 0.0), max(p[1] - q[1], 0.0) };

        return sqrt(u[0] * u[0] + u[1] * u[1]) <= radius;   
    }

做菜顺序

思路

  1. 贪心
  2. 越往后乘积越大,越大的数应该放在最后,所以先排个序
  3. 从后面一个一个加入,每新加一个数,之前加过的所有数都会多加一遍

答题

    int maxSatisfaction(vector<int>& satisfaction)
    {
        sort(satisfaction.rbegin(), satisfaction.rend());
        int ans = 0;
        int sum = 0;
        for (int i = 0; i < satisfaction.size(); i++)
        {
            sum += satisfaction[i];
            if (sum < 0) break;
            ans += sum;
        }
        return ans;
    }

致谢

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

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

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

17
展开全部 28 讨论