网站开发市场情况,网络营销的三大基础,织梦收费,桥梁建设设计网站文章目录1. 比赛结果2. 题目1. LeetCode 5360. 统计最大组的数目 easy2. LeetCode 5362. 构造 K 个回文字符串 medium3. LeetCode 5361. 圆和矩形是否有重叠 medium4. LeetCode 5363. 做菜顺序 hard1. 比赛结果
做出来了 1、3 两题#xff0c;继续加油#xff01; 第二道字符…
文章目录1. 比赛结果2. 题目1. LeetCode 5360. 统计最大组的数目 easy2. LeetCode 5362. 构造 K 个回文字符串 medium3. LeetCode 5361. 圆和矩形是否有重叠 medium4. LeetCode 5363. 做菜顺序 hard1. 比赛结果
做出来了 1、3 两题继续加油 第二道字符串的题又是看错题以后要多读几遍题目题目说要使用所有字符我视而不见去排列组合。。。 第四题想到了贪心又转到动态规划去做没做出来。
全国排名970 / 204447.5%全球排名2946 / 702642%
2. 题目
1. LeetCode 5360. 统计最大组的数目 easy
题目链接
给你一个整数 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解答
class Solution {
public:int countLargestGroup(int n) {unordered_mapint,int m;int sum;for(int i 1; i n; i){sum cal(i);m[sum];}int maxlen 0, count 0;for(auto mi : m){if(mi.second maxlen)//和一样的个数最多的{maxlen mi.second;count 1;}else if(mi.second maxlen)count;}return count;}int cal(int i){ //计算各数位的和int sum 0;while(i){sum i%10;i / 10;}return sum;}
};8 ms 6.4 MB
2. LeetCode 5362. 构造 K 个回文字符串 medium
题目链接
给你一个字符串 s 和一个整数 k 。请你用 s 字符串中 所有字符 构造 k 个非空 回文串 。
如果你可以用 s 中所有字符构造 k 个回文字符串那么请你返回 True 否则返回 False 。
示例 1
输入s annabelle, k 2
输出true
解释可以用 s 中所有字符构造 2 个回文字符串。
一些可行的构造方案包括anna elbleanbna elleanellena 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
class Solution {
public:bool canConstruct(string s, int k) {if(s.size() k)return false;int count[26] {0};for(int i 0; i s.size(); i)count[s[i]-a];int odd 0;for(int i 0; i 26; i){if(count[i]%2 1)odd;} return odd k;}
};60 ms 11.8 MB
3. LeetCode 5361. 圆和矩形是否有重叠 medium
题目链接
给你一个以 (radius, x_center, y_center) 表示的圆和一个与坐标轴平行的矩形 (x1, y1, x2, y2) 其中 (x1, y1) 是矩形左下角的坐标(x2, y2) 是右上角的坐标。
如果圆和矩形有重叠的部分请你返回 True 否则返回 False 。
换句话说请你检测是否 存在 点 (xi, yi) 它既在圆上也在矩形上两者都包括点落在边界上的情况。 解题
检查圆心是否在绿色或者蓝色的矩形内原矩形为红色偏移距离为 半径或者圆心与四个顶点的任意一个的距离小于等于半径
class Solution {
public:bool checkOverlap(int r, int xc, int yc, int x1, int y1, int x2, int y2) {if(dis(xc,yc,x1,y1)r*r||dis(xc,yc,x1,y2)r*r||dis(xc,yc,x2,y1)r*r||dis(xc,yc,x2,y2)r*r)return true;if(x1xc xc x2 y1-r yc yc y2r)return true;if(x1-rxc xc x2r y1 yc yc y2)return true;return false;}double dis(int xc, int yc, int x, int y){return pow((xc-x),2)pow((yc-y),2);}
};0 ms 6 MB
更优美的解Ikaruga大佬
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;vectordouble p { abs(x_center - x0) , abs(y_center - y0) };//圆心与矩形中心的坐标差vectordouble q { x2 - x0, y2 - y0 };//矩形中心与一个顶点的坐标差double a1 max(p[0] - q[0], 0.0);//在上述两个矩形内的话一个分量为0double a2 max(p[1] - q[1], 0.0);//在四个圆角处两个量都不为0return sqrt(a1 * a1 a2 * a2) radius; }
4. LeetCode 5363. 做菜顺序 hard
题目链接
一个厨师收集了他 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解题
参考 ikaruga大佬的解贪心先降序排列满意度最高的系数越大越好
class Solution {
public:int maxSatisfaction(vectorint satisfaction) {sort(satisfaction.rbegin(), satisfaction.rend());int sum 0, ans 0;for(int i 0; i satisfaction.size(); i){sum satisfaction[i];//满意度大的加上if(sum 0)break;ans sum;//循环一次最大的多加1次相当于系数1}return ans;}
};4 ms 6.8 MB
参考 迷糊的康康DP解
class Solution {
public:int maxSatisfaction(vectorint satisfaction) {sort(satisfaction.begin(), satisfaction.end());//需要先排序int i, j, n satisfaction.size();vectorvectorint dp(n1, vectorint(n1,0));//dp[i][j] 表示前i道菜做j道的最大满意度dp[1][0] 0, dp[1][1] satisfaction[0];for(i 2; i n; i){for(j 1; j i; j){if(j i)dp[i][j] dp[i-1][j-1]j*satisfaction[i-1];//每道菜都做了elsedp[i][j] max(dp[i-1][j], dp[i-1][j-1]j*satisfaction[i-1]);//第i道菜不做dp[i-1][j]第i道菜做 dp[i-1][j-1]j*satisfaction[i-1]}}int ans INT_MIN;for(i 0; i n; i)ans max(ans, dp[n][i]);//n道菜做i道的最大值return ans;}
};44 ms 19.4 MB
