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

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

image.png

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

展开讨论
力扣 (LeetCode)发起于 2020-04-04
菜鸡的第三次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
展开全部 28 讨论