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

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

image.png

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

展开讨论
力扣 (LeetCode)发起于 2020-04-04
共 28 个讨论

统计最大组的数目

思路

  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

本来觉得自己彳亍了看见大家都觉得自己彳亍了于是我又觉得自己不彳亍了
明天再来!

6

圆和矩形是否有重叠

将圆在矩形的四边滚上一圈,圆心的轨迹为四条四分之一圆和四条边,简单的判断圆心是不是在这个范围就可以。

class Solution:
    def checkOverlap(self, radius: int, x_center: int, y_center: int, x1: int, y1: int, x2: int, y2: int) -> bool:
        # 先将矩形移动到原点,圆也同步移动
        x_t = (x1+x2)/2
        y_t = (y1+y2)/2
        
        x_center -= x_t
        x1 -= x_t
        x2 -= x_t
        y_center -= y_t
        y1 -= y_t
        y2 -= y_t
        
        # 判断是否在上下两条边范围内
        if x1<=x_center<=x2 and y1-radius<=y_center<=y2+radius:
            return True
        
        # 判断是否在左右两条边范围内
        if x1-radius<=x_center<=x2+radius and y1<=y_center<=y2:
            return True
        
        # 判断是否在四个圆弧范围内
        if ((x1-x_center)**2+(y1-y_center)**2<=radius**2) or ((x1-x_center)**2+(y2-y_center)**2<=radius**2) or ((x2-x_center)**2+(y1-y_center)**2<=radius**2) or ((x2-x_center)**2+(y2-y_center)**2<=radius**2):
            return True
        
        
        return False
3

肯定是看我这周加班多,出点简单题来安慰一下

3

我又觉得自己行了
image.png

3

圆和矩形是否有重叠

image.png

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

        if (x_center < x1) {
            if(y_center>y2){
                // 圆心在左上范围 判断是否相交
                return dist(x_center, y_center, x1, y2, radius);
            }
            if(y_center<y1){
                // 圆心在左下范围 判断是否相交
                return dist(x_center, y_center, x1, y1, radius);
            }
        }
        if (x_center > x2) {
            if(y_center>y2){
                // 圆心在右上范围 判断是否相交
                return dist(x_center, y_center, x2, y2, radius);
            }
            if(y_center<y1){
                // 圆心右下范围 判断是否相交
                return dist(x_center, y_center, x2, y1, radius);
            }
        }

        return true;
    }

    public boolean dist(int x1, int y1, int x2, int y2,int r) {
       double dist =  Math.sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
        return dist<r;
    }
2

这题让我觉得暴力就是艺术

1
菜鸡的第三次ak2333...以下使用Python3实现(当然语言无国界啦),仅供参考,还望各位大佬指导~

T1. 统计最大组的数目
【分析】Array + Sort + Count
(1)对区间[1, n]上的各个数i求各数位之和curSum,并存储映射curSum -> i至一哈希表dic(这里使用字典);
(2)将dic按值的长度递减排序;
(3)排序后,显然dic中的第一对映射对应的键为最大组,然后扫描后续键值对,累加值长度 = 第一对映射值长度的个数。最终返回此个数即可。
时间复杂度O(nlogn), 空间复杂度O(n)。

class Solution:
    def countLargestGroup(self, n: int) -> int:
        dic = collections.defaultdict(list)
        for i in range(1, n + 1):
            temp, curSum = i, 0
            while temp:
                curSum += temp % 10
                temp //= 10
            dic[curSum].append(i)
        dic = sorted(dic.items(), key=lambda k: len(k[1]), reverse=True)
        dic = list(dic)
        res = 1
        for i in range(1, len(dic)):
            if len(dic[i][1]) == len(dic[0][1]):
                res += 1
            else:
                break
        return res

T2. 构建K个回文字符串
【分析】HashTable + Greedy
(1)首先获取串s长度n,显然若n < k,凑不成k个回文串返回false;若n == k,则恰可以凑成k个回文串,返回true;
(2)统计串s中各小写字母出现次数,然后统计出现次数为奇数次的小写字母个数ans;
(3)根据回文串特性:每个回文串中出现次数为奇数的字符最多有一种,而出现次数为偶数的字符可以有若干种,因此ans必须 <= k才能恰好凑成k个回文串。故返回是否满足(ans <= k)即可。
时间复杂度O(n), 空间复杂度O(n)。

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        n = len(s)
        if n < k: return False
        elif n == k: return True
        
        ans, odd = [0] * 26, 0
        for i in range(len(s)):
            ans[ord(s[i]) - 97] += 1
        for i in range(26):
            if ans[i] % 2 == 1:
                odd += 1
        return odd <= k

T3. 圆和矩形是否有重叠
【分析】Math
数学题,判断给定圆和矩形的位置关系(相离/相切/相交),符合题意的情况为相切/相交。
(1)相离:4种情况;
(2)相切/相交:从圆的标准方程入手,对x∈[x_center-radius, x_center+radius],求出y(可能有一解/两解,记为y1和y2, y2 < y1),然后判断此矩形中是否有点在(x, y2)和(x, y1)之间即可。
时间复杂度O(n), 空间复杂度O(n)。

class Solution:
        def checkOverlap(self, radius: int, x_center: int, y_center: int, x1: int, y1: int, x2: int, y2: int) -> bool:
        # 相离
        if x_center + radius < x1 or x_center - radius > x2 or y_center + radius < y1 or y_center - radius > y2:
            return False
        # 枚举x∈[x_center-radius, x_center+radius], 求出此x下对应的圆上的点(x, y_pos2)和(x, y_pos1), y_pos2 <= y_pos1
        for x in range(x_center - radius, x_center + radius + 1):
            y_pos1 = math.sqrt(radius * radius - pow((x - x_center), 2)) + y_center
            if math.sqrt(radius * radius - pow((x - x_center), 2)) == 0:
                y_pos2 = y_pos1
            else:
                y_pos2 = y_center - abs(y_pos1 - y_center)
            # 相切/相交
if (x1 <= x <= x2 and y1 <= y_pos1 <= y2) or (x1 <= x <= x2 and y1 <= y_pos2 <= y2) or (x1 <= x <= x2 and y_pos2 <= y1 <= y_pos1) or (x1 <= x <= x2 and y_pos2 <= y2 <= y_pos1):
                return True
        return False

T4. 做菜顺序
【分析】Greedy
根据题意,可对n道菜按满意度递增排序,显然满意度最高的菜为负数时直接返回0(此时只要安排上一道菜,满意度必 < 0,所以只能一道菜都不安排);然后依次自右向左判断安排第i~(n - 1)道菜的满意度,最大化即可。
时间复杂度O(n2), 空间复杂度O(1)。

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        n, res = len(satisfaction), 0
        
        satisfaction.sort()
        if satisfaction[n - 1] < 0:
            return 0
        for i in range(n - 1, -1, -1):
            curSum, curP = 0, 1
            for j in range(i, n):
                curSum += (satisfaction[j] * curP)
                curP += 1
            res = max(res, curSum)
        return res
1

第一题java纯数组不需要hashmap

class Solution {
    public int countLargestGroup(int n) {
        int[] d = new int[37];//因为n为1-10000;所以转化出来的最大值为36,也就是9999
        int max = 0;//用来标记最大组元素的个数
        int num = 0;//最大数组的个数,也就是题目需要的答案
        for(int i =1;i<=n;i++){//遍历n个数
            d[re(i)]++;//re(i)为多少就让下标为它的数组值加一
            if(d[re(i)]>max){
                max = d[re(i)];//max为当前最大组元素的个数
            }
        }
        for(int i = 1;i<37;i++){//遍历数组
            if(d[i]==max){//找出数字数目并列最多的组
                num++;//找到就num+1
            }
        }
        return num;
    }
    public int re(int a){//将数转换为所有位十进制下相加的数
        int sum = 0;
        while(a!=0){
            sum = sum+(a%10);
            a = a/10;
        }
        return sum;
    }
}
1

Line 59: Char 5: error: conflicting types for 'main'
这是嘛呀,我代码一共才53行
Line 62: Char 17: fatal error: use of undeclared identifier 'Solution'
int ret = Solution().countLargestGroup(param_1); return ret;
^
1 error generated.
还有这个,C代码用C++编译提示的错误,完全牛头不对马尾啊

1