LeetCode 第23场双周赛

一看最后一题就6分，感觉今天稳了🙃排名183 / 2037

Contents

1 第一题：统计最大组的数目
2 第二题：构造 K 个回文字符串
3 第三题：圆和矩形是否有重叠
4 第四题：做菜顺序

第一题：统计最大组的数目

难度简单

题目描述

给你一个整数 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 个组拥有的数字并列最多。

输入：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]。

输入：n = 2

输出：2

解释：总共有 2 个大小为 1 的组 [1]，[2]。

示例 3：

输入：n = 15
输出：6

输入：n = 15

输出：6

示例 4：

输入：n = 24
输出：5

输入：n = 24

输出：5

提示：

1 <= n <= 10^4

题目链接

https://leetcode-cn.com/problems/count-largest-group/

思路:

　　① 统计1~n每个数字的数位和并把相同的放在一起计次；
　　② 找出次数最多的；
　　③ 统计次数最多的出现了几次。　　

代码:

from collections import defaultdict

class Solution:
    def countLargestGroup(self, n: int) -> int:

        nums = defaultdict(int)
        for i in range(1, n+1):
            count = 0
            for digit in str(i):
                count += int(digit)
            nums[count] += 1

        # print(nums)
        maximum = sorted(nums.values())[-1]
        ans = 0
        for key in nums:
            if nums[key] == maximum:
                ans += 1
        return ans

from collections import defaultdict

class Solution:

def countLargestGroup(self, n: int) -> int:

nums = defaultdict(int)

for i in range(1, n+1):

count = 0

for digit in str(i):

count += int(digit)

nums[count] += 1

# print(nums)

maximum = sorted(nums.values())[-1]

ans = 0

for key in nums:

if nums[key] == maximum:

ans += 1

return ans

第二题：构造 K 个回文字符串

难度中等

题目描述

给你一个字符串 s 和一个整数 k 。请你用 s 字符串中 所有字符 构造 k 个非空 回文串 。

如果你可以用 s 中所有字符构造 k 个回文字符串，那么请你返回 True ，否则返回 False 。

示例 1：

输入：s = "annabelle", k = 2
输出：true
解释：可以用 s 中所有字符构造 2 个回文字符串。
一些可行的构造方案包括："anna" + "elble"，"anbna" + "elle"，"anellena" + "b"

输入：s = "annabelle", k = 2

输出：true

解释：可以用 s 中所有字符构造 2 个回文字符串。

一些可行的构造方案包括："anna" + "elble"，"anbna" + "elle"，"anellena" + "b"

示例 2：

输入：s = "leetcode", k = 3
输出：false
解释：无法用 s 中所有字符构造 3 个回文串。

输入：s = "leetcode", k = 3

输出：false

解释：无法用 s 中所有字符构造 3 个回文串。

示例 3：

输入：s = "true", k = 4
输出：true
解释：唯一可行的方案是让 s 中每个字符单独构成一个字符串。

输入：s = "true", k = 4

输出：true

解释：唯一可行的方案是让 s 中每个字符单独构成一个字符串。

示例 4：

输入：s = "yzyzyzyzyzyzyzy", k = 2
输出：true
解释：你只需要将所有的 z 放在一个字符串中，所有的 y 放在另一个字符串中。那么两个字符串都是回文串。

输入：s = "yzyzyzyzyzyzyzy", k = 2

输出：true

解释：你只需要将所有的 z 放在一个字符串中，所有的 y 放在另一个字符串中。那么两个字符串都是回文串。

示例 5：

输入：s = "cr", k = 7
输出：false
解释：我们没有足够的字符去构造 7 个回文串。

输入：s = "cr", k = 7

输出：false

解释：我们没有足够的字符去构造 7 个回文串。

提示：

1 <= s.length <= 10^5
s 中所有字符都是小写英文字母。
1 <= k <= 10^5

题目链接

https://leetcode-cn.com/problems/construct-k-palindrome-strings/

思路:

　　注意要用上所有字符。
　　① 统计每个字母的出现次数；
　　② 出现奇数次的字母必须单独放在一个回文串中，因此最少的回文串数目 = 出现奇数次的字母个数；
　　③ 最多的回文串数目 = s的字母数；
　　④ 判断k是否在最少的回文串数目和最多的回文串数目之间即可。

代码:

import collections
class Solution:
    def canConstruct(self, s: str, k: int) -> bool:

        ls = len(s)
        if ls < k:
            return False  # 字符不够

        c = collections.Counter(s)
        odd = 0
        for key in c:
            if c[key] % 2 == 1:
                odd += 1

        # print(odd)
        return k >= odd

import collections

class Solution:

def canConstruct(self, s: str, k: int) -> bool:

ls = len(s)

if ls < k:

return False # 字符不够

c = collections.Counter(s)

odd = 0

for key in c:

if c[key] % 2 == 1:

odd += 1

# print(odd)

return k >= odd

第三题：圆和矩形是否有重叠

难度中等

题目描述

给你一个以 (radius, x_center, y_center) 表示的圆和一个与坐标轴平行的矩形 (x1, y1, x2, y2)，其中 (x1, y1) 是矩形左下角的坐标，(x2, y2) 是右上角的坐标。

如果圆和矩形有重叠的部分，请你返回 True ，否则返回 False 。

换句话说，请你检测是否存在点 (xi, yi) ，它既在圆上也在矩形上（两者都包括点落在边界上的情况）。

示例 1：

输入：radius = 1, x_center = 0, y_center = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1
输出：true
解释：圆和矩形有公共点 (1,0)

输入：radius = 1, x_center = 0, y_center = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1

输出：true

解释：圆和矩形有公共点 (1,0)

示例 2：

输入：radius = 1, x_center = 0, y_center = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1
输出：true

输入：radius = 1, x_center = 0, y_center = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1

输出：true

示例 3：

输入：radius = 1, x_center = 1, y_center = 1, x1 = -3, y1 = -3, x2 = 3, y2 = 3
输出：true

输入：radius = 1, x_center = 1, y_center = 1, x1 = -3, y1 = -3, x2 = 3, y2 = 3

输出：true

示例 4：

输入：radius = 1, x_center = 1, y_center = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1
输出：false

输入：radius = 1, x_center = 1, y_center = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1

输出：false

提示：

1 <= radius <= 2000
-10^4 <= x_center, y_center, x1, y1, x2, y2 <= 10^4
x1 < x2
y1 < y2

题目链接

https://leetcode-cn.com/problems/circle-and-rectangle-overlapping/

思路:

　　① 检测矩形的四个顶点是否在圆中；
　　② 圆是否与矩形的四条边相交(圆是否与线段相交，通过判断圆心是否在以该线段为中心，圆的半径r为边长的矩形内)；
　　③ 圆心是否在矩形内。
　　如果①②③都不满足，则返回False。

代码:

class Solution:
    def checkOverlap(self, radius: int, x_center: int, y_center: int, x1: int, y1: int, x2: int, y2: int) -> bool:
        def pt_in_circle(x, y, x_c, y_c, r): # pt(x, y)  circle(x_c, y_c, r)
            p = complex(x, y)
            c = complex(x_c, y_c)
            if abs(p - c) < r:
                return True
            else:
                return False

        def pt_in_rect(x, y, x1, y1, x2, y2):  # pt(x, y)  rect(x1, y1, x2, y2)  x1 < x2, y1 < y2
            if not (x1 <= x <= x2 or x1 >= x >= x2):
                return False
            if not (y1 <= y <= y2 or y1 >= y >= y2):
                return False
            return True

        def circle_inter_rect(x1, y1, x2, y2, x_c, y_c, r):  # rect(x1, y1, x2, y2)  circle(x_c, y_c, r)
            a = pt_in_circle(x_c, y_c, x1, y1, r)
            b = pt_in_circle(x_c, y_c, x2, y1, r)
            c = pt_in_circle(x_c, y_c, x1, y2, r)
            d = pt_in_circle(x_c, y_c, x2, y2, r)

            e = pt_in_rect(x_c, y_c, x1, y1 + r, x2, y1 - r)
            f = pt_in_rect(x_c, y_c, x1, y2 + r, x2, y2 - r)

            g = pt_in_rect(x_c, y_c, x1 - r, y1, x1 + r, y2)
            h = pt_in_rect(x_c, y_c, x2 - r, y1, x2 + r, y2)

            i = pt_in_rect(x_c, y_c, x1, y1, x2, y2)  # 圆心在矩形内

            return a or b or c or d or e or f or g or h or i


        return circle_inter_rect(x1,y1,x2,y2,x_center,y_center,radius)

class Solution:

def checkOverlap(self, radius: int, x_center: int, y_center: int, x1: int, y1: int, x2: int, y2: int) -> bool:

def pt_in_circle(x, y, x_c, y_c, r): # pt(x, y) circle(x_c, y_c, r)

p = complex(x, y)

c = complex(x_c, y_c)

if abs(p - c) < r:

return True

else:

return False

def pt_in_rect(x, y, x1, y1, x2, y2): # pt(x, y) rect(x1, y1, x2, y2) x1 < x2, y1 < y2

if not (x1 <= x <= x2 or x1 >= x >= x2):

return False

if not (y1 <= y <= y2 or y1 >= y >= y2):

return False

return True

def circle_inter_rect(x1, y1, x2, y2, x_c, y_c, r): # rect(x1, y1, x2, y2) circle(x_c, y_c, r)

a = pt_in_circle(x_c, y_c, x1, y1, r)

b = pt_in_circle(x_c, y_c, x2, y1, r)

c = pt_in_circle(x_c, y_c, x1, y2, r)

d = pt_in_circle(x_c, y_c, x2, y2, r)

e = pt_in_rect(x_c, y_c, x1, y1 + r, x2, y1 - r)

f = pt_in_rect(x_c, y_c, x1, y2 + r, x2, y2 - r)

g = pt_in_rect(x_c, y_c, x1 - r, y1, x1 + r, y2)

h = pt_in_rect(x_c, y_c, x2 - r, y1, x2 + r, y2)

i = pt_in_rect(x_c, y_c, x1, y1, x2, y2) # 圆心在矩形内

return a or b or c or d or e or f or g or h or i

return circle_inter_rect(x1,y1,x2,y2,x_center,y_center,radius)

第四题：做菜顺序

难度困难

题目描述

一个厨师收集了他 n 道菜的满意程度 satisfaction ，这个厨师做出每道菜的时间都是 1 单位时间。

一道菜的「喜爱时间」系数定义为烹饪这道菜以及之前每道菜所花费的时间乘以这道菜的满意程度，也就是 time[i]*satisfaction[i] 。

请你返回做完所有菜「喜爱时间」总和的最大值为多少。

你可以按任意顺序安排做菜的顺序，你也可以选择放弃做某些菜来获得更大的总和。

示例 1：

输入：satisfaction = [-1,-8,0,5,-9]
输出：14
解释：去掉第二道和最后一道菜，最大的喜爱时间系数和为 (-1*1 + 0*2 + 5*3 = 14) 。每道菜都需要花费 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)

输入：satisfaction = [4,3,2]

输出：20

解释：按照原来顺序相反的时间做菜 (2*1 + 3*2 + 4*3 = 20)

示例 3：

输入：satisfaction = [-1,-4,-5]
输出：0
解释：大家都不喜欢这些菜，所以不做任何菜可以获得最大的喜爱时间系数。

输入：satisfaction = [-1,-4,-5]

输出：0

解释：大家都不喜欢这些菜，所以不做任何菜可以获得最大的喜爱时间系数。

示例 4：

输入：satisfaction = [-2,5,-1,0,3,-3]
输出：35

输入：satisfaction = [-2,5,-1,0,3,-3]

输出：35

提示：

n == satisfaction.length
1 <= n <= 500
-10^3 <= satisfaction[i] <= 10^3

题目链接

https://leetcode-cn.com/problems/reducing-dishes/

思路:

　　因为可以调换顺序，尽量后做满意度大的菜。
　　遍历所有可能的做菜数(即0~n)，满意度大的先做，满意度小的后做，计算总的喜爱时间，如果比之前的最大喜爱时间更大就更新最大喜爱时间。

代码:

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort()
        ls = len(satisfaction)


        print(satisfaction)
        ans = 0
        for counts in range(ls, 0, -1):  # 最多都做 最少做0道
            sums = 0
            for i in range(counts, 0, -1):
                sums += satisfaction[i - counts - 1] * i

            # print(counts, sums)
            ans = max(ans, sums)

        return ans

class Solution:

def maxSatisfaction(self, satisfaction: List[int]) -> int:

satisfaction.sort()

ls = len(satisfaction)

print(satisfaction)

ans = 0

for counts in range(ls, 0, -1): # 最多都做最少做0道

sums = 0

for i in range(counts, 0, -1):

sums += satisfaction[i - counts - 1] * i

# print(counts, sums)

ans = max(ans, sums)

return ans