Leetcode23双周赛
程序员文章站
2022-07-12 12:09:31
...
排名:75 / 2044
第一题:统计最大组的数目
解题思路:这题是要统计数位上的值相加和相等的数,返回其中并列最多的组。这里可以构建一个足够大的数组,然后进行统计并列最多的组,最后在遍历结果集并记录次数返回。
class Solution {
public int countLargestGroup(int n) {
int[] dict = new int[10000+10];
int max = 0;
for (int i = 1; i <= n; i++) {
int t = i;
int sum = 0;
while (t!=0){
sum+=t%10;
t/=10;
}
dict[sum]++;
max = Math.max(dict[sum],max);
}
int ans = 0;
for (int i = 0; i < dict.length; i++) {
if (max==dict[i]){
ans++;
}
}
return ans;
}
}
第二题:构造 K 个回文字符串
解题思路:题目给出一个字符串s,以及一个整数k,判断能否利用s中的所有字符,构造k个回文字符串,(一个是用光s中的所有字符,一个是回文字符串中的字符个数大于0)。这题只需要统计一下单数字母的个数,然后与k进行比较即可。(回文字符串无非就是类似aa、aba、baab这种,其中单个字符在回文字符串中只能出现一个。而偶数字符的个数其实无所谓)
class Solution {
public boolean canConstruct(String s, int k) {
int[] dict = new int[26];
int n = s.length();
if (n<k)return false;
for (int i = 0; i < n; i++) {
dict[s.charAt(i)-'a']++;
}
int t1=0;
for (int i = 0; i < 26; i++) {
if (dict[i]!=0){
if (dict[i]%2==1){
t1++;
}
}
}
if (t1>k)return false;
return true;
}
}
第三题:圆和矩形是否有重叠
解题思路:题目给一个圆心坐标以及半径,以及矩形左下角坐标和右上角坐标判断圆和矩形是否有重叠部分(相切也算)。首先就判断圆在不在矩形内部,然后在遍历矩形的每条边上的点,看看与圆心的距离是否小于半径。
class Solution {
public boolean checkOverlap(int radius, int x_center, int y_center, int x1, int y1, int x2, int y2) {
if (x_center+radius>=x1 && x_center+radius<=x2 && y_center+radius>=y1 && y_center+radius<=y2){
return true;
}
for (int i = y1; i <= y2; i++) {
if ((x1-x_center)*(x1-x_center)+(i-y_center)*(i-y_center)<=radius*radius)
return true;
if ((x2-x_center)*(x2-x_center)+(i-y_center)*(i-y_center)<=radius*radius)
return true;
}
for (int i = x1; i <= x2; i++) {
if ((i-x_center)*(i-x_center)+(y1-y_center)*(y1-y_center)<=radius*radius)
return true;
if ((i-x_center)*(i-x_center)+(y2-y_center)*(y2-y_center)<=radius*radius)
return true;
}
return false;
}
}
第四题:做菜顺序
解题思路:题意就是给出一个数组,然后你从中选择几个数,如[-1,-8,0,5,-9],选择了-1,0,5三个数,那么结果就为-1*1+0*2+5*3,以此类推。这里我们可以拍个序,然后将负数和正数分别放入一个list中,然后进行枚举负数的个数即可(正数是一定都会用上的,只需要考虑负数使用情况),然后返回结果。
class Solution {
public int maxSatisfaction(int[] satisfaction) {
Arrays.sort(satisfaction);
List<Integer> fushu = new ArrayList<>();
List<Integer> zhengshu = new ArrayList<>();
int n = satisfaction.length;
int ans = 0;
for (int i = 0; i < n; i++) {
if (satisfaction[i]>=0){
zhengshu.add(satisfaction[i]);
ans += zhengshu.size()*satisfaction[i];
}else {
fushu.add(0,satisfaction[i]);
}
}
for (int i = 0; i < fushu.size(); i++) {
int flag = 0;
int t = 0;
for (int j = i; j >= 0; j--) {
flag++;
t+=flag*fushu.get(j);
}
for (int j = 0; j < zhengshu.size(); j++) {
flag++;
t+=flag*zhengshu.get(j);
}
ans = Math.max(t,ans);
}
return ans;
}
}
上一篇: 压缩感知之稀疏基
下一篇: 数据分析集训营-第六次任务(模型融合)