欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
    }
}