On the shoulders of giants.

biweekly-contest-23

统计最大组的数目

给你一个整数 n 。请你先求出从 1 到 n 的每个整数 10 进制表示下的数位和(每一位上的数字相加),然后把数位和相等的数字放到同一个组中。

请你统计每个组中的数字数目,并返回数字数目并列最多的组有多少个。

示例 1:

输入:n = 13
输出:4
解释:总共有 9 个组,将 1 到 13 按数位求和后这些组分别是:
[1,10],[2,11],[3,12],[4,13],[5],[6],[7],[8],[9]。总共有 4 个组拥有的数字并列最多。

示例 2:

输入:n = 2
输出:2
解释:总共有 2 个大小为 1 的组 [1],[2]。

示例 3:

输入:n = 15
输出:6

示例 4:

输入:n = 24
输出:5

提示:

  • 1 <= n <= 10^4
题解

每一个数都计算一边,然后记录最大重复次数。

时间复杂度:\(O(n\log n)\)

class Solution {
public:
    int countLargestGroup(int n) {
        map<int, int> h;
        int lim = -1, result = 0;
        for(int i = 1; i <= n; i++) {
            int x = i, sum = 0;
            while(x) {
                sum += x % 10;
                x /= 10;
            }
            h[sum]++;
            if(lim < h[sum]) lim = h[sum], result = 1;
            else if(lim == h[sum]) result++;
        }
        return result; 
    }
};

构造 K 个回文字符串

给你一个字符串 s 和一个整数 k 。请你用 s 字符串中 所有字符 构造 k 个非空 回文串 。

如果你可以用 s 中所有字符构造 k 个回文字符串,那么请你返回 True ,否则返回 False 。

示例 1:

输入:s = "annabelle", k = 2
输出:true
解释:可以用 s 中所有字符构造 2 个回文字符串。
一些可行的构造方案包括:"anna" + "elble","anbna" + "elle","anellena" + "b"

示例 2:

输入:s = "leetcode", k = 3
输出:false
解释:无法用 s 中所有字符构造 3 个回文串。

示例 3:

输入:s = "true", k = 4
输出:true
解释:唯一可行的方案是让 s 中每个字符单独构成一个字符串。

示例 4:

输入:s = "yzyzyzyzyzyzyzy", k = 2
输出:true
解释:你只需要将所有的 z 放在一个字符串中,所有的 y 放在另一个字符串中。那么两个字符串都是回文串。

示例 5:

输入:s = "cr", k = 7
输出:false
解释:我们没有足够的字符去构造 7 个回文串。

提示:

  • 1 <= s.length <= 10^5
  • s 中所有字符都是小写英文字母。
  • 1 <= k <= 10^5
题解

我们要找一个正确的构造方法:记录每个字符的出现次数。

如果出现奇数次数与 k 相同,我们可以分别以它们为中心构造 k 的回文串;如果出现次数大于 k,则一定无解。

如果我们可以把奇次数单独构成一个回文串,剩下考虑出现偶数次的。

如果剩下的位置还有奇数个,那么不管偶数次的字符怎么放都是不合法的;

如果剩下的卫视还有偶数个,那么我们两个位置放一对,剩下的可以组合出合法的回文串。

时间复杂度:\(O(n)\)

class Solution {
public:
    bool canConstruct(string s, int k) {
        if(s.length() < k) return false;
        if(s.length() == k) return true;
        map<char, int> count;
        for(auto c : s) count[c]++;
        int a = 0, b = 0;
        for(auto& x : count) {
            if(x.second & 1) a++;
            b += x.second / 2;
        }
        if(k == a) return true;
        if(k < a) return false;
        if((k - a) & 1) b--;
        return (k - a - 1) <= 2 * b;
    }
};

圆和矩形是否有重叠

给你一个以 (radius, x_center, y_center) 表示的圆和一个与坐标轴平行的矩形 (x1, y1, x2, y2),其中 (x1, y1) 是矩形左下角的坐标,(x2, y2) 是右上角的坐标。

如果圆和矩形有重叠的部分,请你返回 True ,否则返回 False 。

换句话说,请你检测是否 存在 点 (xi, yi) ,它既在圆上也在矩形上(两者都包括点落在边界上的情况)。

示例 1:

输入:radius = 1, x_center = 0, y_center = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1
输出:true
解释:圆和矩形有公共点 (1,0) 

示例 2:

输入:radius = 1, x_center = 0, y_center = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1
输出:true

示例 3:

输入:radius = 1, x_center = 1, y_center = 1, x1 = -3, y1 = -3, x2 = 3, y2 = 3
输出:true

示例 4:

输入:radius = 1, x_center = 1, y_center = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1
输出:false

提示:

  • 1 <= radius <= 2000
  • -10^4 <= x_center, y_center, x1, y1, x2, y2 <= 10^4
  • x1 < x2
  • y1 < y2
题解

把矩形中心映射到原点,然后在把园映射到第一象限,那么我们可以计算圆心到矩形右上角的理解。

时间复杂度:\(O(1)\)

class Solution {
public:
    bool checkOverlap(int radius, int x_center, int y_center, int x1, int y1, int x2, int y2) {
        double x = 0.5 * (x1 + x2), y = 0.5 * (y1 + y2);
        double c_x = abs(x_center - x), c_y = abs(y_center - y);
        double p_x = x2 - x, p_y = y2 - y;
        double u_x = max(0.0, c_x - p_x), u_y = max(0.0, c_y - p_y);
        return sqrt(u_x * u_x + u_y * u_y) <= radius;
    }
};

做菜顺序

一个厨师收集了他 n 道菜的满意程度 satisfaction ,这个厨师做出每道菜的时间都是 1 单位时间。

一道菜的 「喜爱时间」系数定义为烹饪这道菜以及之前每道菜所花费的时间乘以这道菜的满意程度,也就是 time[i]*satisfaction[i] 。

请你返回做完所有菜 「喜爱时间」总和的最大值为多少。

你可以按 任意 顺序安排做菜的顺序,你也可以选择放弃做某些菜来获得更大的总和。

示例 1:

输入:satisfaction = [-1,-8,0,5,-9]
输出:14
解释:去掉第二道和最后一道菜,最大的喜爱时间系数和为 (-1*1 + 0*2 + 5*3 = 14) 。每道菜都需要花费 1 单位时间完成。

示例 2:

输入:satisfaction = [4,3,2]
输出:20
解释:按照原来顺序相反的时间做菜 (2*1 + 3*2 + 4*3 = 20)

示例 3:

输入:satisfaction = [-1,-4,-5]
输出:0
解释:大家都不喜欢这些菜,所以不做任何菜可以获得最大的喜爱时间系数。

示例 4:

输入:satisfaction = [-2,5,-1,0,3,-3]
输出:35

提示:

  • n == satisfaction.length
  • 1 <= n <= 500
  • -10^3 <= satisfaction[i] <= 10^3
题解

动态规划,设 \(dp_{x,y}\) 表示前 x 个菜,选了 y 个菜的最大系数。

有,转移 \(dp_{x,y}=\max (dp_{x-1,y}, dp_{x-1,y-1}+stai_x)\)

x = y 时,最后一个一定要选。

时间复杂度:\(O(n^2)\)

class Solution {
public:
    int maxSatisfaction(vector<int>& satisfaction) {
        int n = satisfaction.size(), result = 0;
        vector<vector<int>> dp(n + 1, vector<int> (n + 1, 0));
        sort(satisfaction.begin(), satisfaction.end());
        dp[1][0] = 0, dp[1][1] = satisfaction[0];
        for(int i = 2; i <= n; i++) {
           for(int j = 1; j <= i; j++) {
                if(j == i) dp[i][j] = dp[i - 1][j - 1] + j * satisfaction[i - 1];
                else {
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + j * satisfaction[i - 1]);
               }
           }
        }
        for(int i = 1; i <= n; i++) result = max(result, dp[n][i]);
        return result;
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注