第一题：在既定时间做作业的学生人数
难度简单
题目描述
给你两个整数数组 startTime（开始时间）和 endTime（结束时间），并指定一个整数 queryTime 作为查询时间。
已知，第 i 名学生在 startTime[i] 时开始写作业并于 endTime[i] 时完成作业。
请返回在查询时间 queryTime 时正在做作业的学生人数。形式上，返回能够使 queryTime 处于区间 [startTime[i], endTime[i]]（含）的学生人数。
示例 1：
|
1 2 3 4 5 6 7 |
输入：startTime = [1,2,3], endTime = [3,2,7], queryTime = 4 输出：1 解释：一共有 3 名学生。 第一名学生在时间 1 开始写作业，并于时间 3 完成作业，在时间 4 没有处于做作业的状态。 第二名学生在时间 2 开始写作业，并于时间 2 完成作业，在时间 4 没有处于做作业的状态。 第二名学生在时间 3 开始写作业，预计于时间 7 完成作业，这是是唯一一名在时间 4 时正在做作业的学生。 |
示例 2：
|
1 2 3 4 |
输入：startTime = [4], endTime = [4], queryTime = 4 输出：1 解释：在查询时间只有一名学生在做作业。 |
示例 3：
|
1 2 3 |
输入：startTime = [4], endTime = [4], queryTime = 5 输出：0 |
示例 4：
|
1 2 3 |
输入：startTime = [1,1,1,1], endTime = [1,3,2,4], queryTime = 7 输出：0 |
示例 5：
|
1 2 3 |
输入：startTime = [9,8,7,6,5,4,3,2,1], endTime = [10,10,10,10,10,10,10,10,10], queryTime = 5 输出：5 |
提示：
startTime.length == endTime.length1 <= startTime.length <= 1001 <= startTime[i] <= endTime[i] <= 10001 <= queryTime <= 1000
题目链接
https://leetcode-cn.com/problems/number-of-students-doing-homework-at-a-given-time/
思路:
数据量很小，暴力即可。
代码:
|
1 2 3 4 5 6 7 8 9 10 |
class Solution: def busyStudent(self, startTime: List[int], endTime: List[int], queryTime: int) -> int: ans = 0 for s, r in zip(startTime, endTime): if s <= queryTime <= r: ans += 1 return ans |
第二题：重新排列句子中的单词
难度中等
题目描述
「句子」是一个用空格分隔单词的字符串。给你一个满足下述格式的句子 text :
- 句子的首字母大写
text中的每个单词都用单个空格分隔。
请你重新排列 text 中的单词，使所有单词按其长度的升序排列。如果两个单词的长度相同，则保留其在原句子中的相对顺序。
请同样按上述格式返回新的句子。
示例 1：
|
1 2 3 4 5 |
输入：text = "Leetcode is cool" 输出："Is cool leetcode" 解释：句子中共有 3 个单词，长度为 8 的 "Leetcode" ，长度为 2 的 "is" 以及长度为 4 的 "cool" 。 输出需要按单词的长度升序排列，新句子中的第一个单词首字母需要大写。 |
示例 2：
|
1 2 3 4 5 6 7 8 9 |
输入：text = "Keep calm and code on" 输出："On and keep calm code" 解释：输出的排序情况如下： "On" 2 个字母。 "and" 3 个字母。 "keep" 4 个字母，因为存在长度相同的其他单词，所以它们之间需要保留在原句子中的相对顺序。 "calm" 4 个字母。 "code" 4 个字母。 |
示例 3：
|
1 2 3 |
输入：text = "To be or not to be" 输出："To be or to be not" |
提示：
text以大写字母开头，然后包含若干小写字母以及单词间的单个空格。1 <= text.length <= 10^5
题目链接
https://leetcode-cn.com/problems/rearrange-words-in-a-sentence/
思路:
这题对python很友好。
代码:
|
1 2 3 4 5 6 7 8 9 |
class Solution: def arrangeWords(self, text: str) -> str: text = text.lower() text = text.split() text.sort(key=len) text[0] = text[0].capitalize() return ' '.join(text) |
第三题：收藏清单
难度中等
题目描述
给你一个数组 favoriteCompanies ，其中 favoriteCompanies[i] 是第 i 名用户收藏的公司清单（下标从 0 开始）。
请找出不是其他任何人收藏的公司清单的子集的收藏清单，并返回该清单下标。下标需要按升序排列。
示例 1：
|
1 2 3 4 5 6 7 |
输入：favoriteCompanies = [["leetcode","google","facebook"],["google","microsoft"],["google","facebook"],["google"],["amazon"]] 输出：[0,1,4] 解释： favoriteCompanies[2]=["google","facebook"] 是 favoriteCompanies[0]=["leetcode","google","facebook"] 的子集。 favoriteCompanies[3]=["google"] 是 favoriteCompanies[0]=["leetcode","google","facebook"] 和 favoriteCompanies[1]=["google","microsoft"] 的子集。 其余的收藏清单均不是其他任何人收藏的公司清单的子集，因此，答案为 [0,1,4] 。 |
示例 2：
|
1 2 3 4 |
输入：favoriteCompanies = [["leetcode","google","facebook"],["leetcode","amazon"],["facebook","google"]] 输出：[0,1] 解释：favoriteCompanies[2]=["facebook","google"] 是 favoriteCompanies[0]=["leetcode","google","facebook"] 的子集，因此，答案为 [0,1] 。 |
示例 3：
|
1 2 3 |
输入：favoriteCompanies = [["leetcode"],["google"],["facebook"],["amazon"]] 输出：[0,1,2,3] |
提示：
1 <= favoriteCompanies.length <= 1001 <= favoriteCompanies[i].length <= 5001 <= favoriteCompanies[i][j].length <= 20favoriteCompanies[i]中的所有字符串 各不相同 。- 用户收藏的公司清单也 各不相同 ，也就是说，即便我们按字母顺序排序每个清单，
favoriteCompanies[i] != favoriteCompanies[j]仍然成立。 - 所有字符串仅包含小写英文字母。
题目链接
思路:
这题也对python很友好。
代码:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Solution: def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]: n = len(favoriteCompanies) ans = [] for i in range(n): fi = set(favoriteCompanies[i]) for j in range(n): if j == i: continue fj = set(favoriteCompanies[j]) if fi.issubset(fj): break else: ans.append(i) return ans |
第四题：圆形靶内的最大飞镖数量
难度困难
题目描述
墙壁上挂着一个圆形的飞镖靶。现在请你蒙着眼睛向靶上投掷飞镖。
投掷到墙上的飞镖用二维平面上的点坐标数组表示。飞镖靶的半径为 r 。
请返回能够落在 任意 半径为 r 的圆形靶内或靶上的最大飞镖数。
示例 1：
|
1 2 3 4 |
输入：points = [[-2,0],[2,0],[0,2],[0,-2]], r = 2 输出：4 解释：如果圆形的飞镖靶的圆心为 (0,0) ，半径为 2 ，所有的飞镖都落在靶上，此时落在靶上的飞镖数最大，值为 4 。 |
示例 2：
|
1 2 3 4 |
输入：points = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5 输出：5 解释：如果圆形的飞镖靶的圆心为 (0,4) ，半径为 5 ，则除了 (7,8) 之外的飞镖都落在靶上，此时落在靶上的飞镖数最大，值为 5 。 |
示例 3：
|
1 2 3 |
输入：points = [[-2,0],[2,0],[0,2],[0,-2]], r = 1 输出：1 |
示例 4：
|
1 2 3 |
输入：points = [[1,2],[3,5],[1,-1],[2,3],[4,1],[1,3]], r = 2 输出：4 |
提示：
1 <= points.length <= 100points[i].length == 2-10^4 <= points[i][0], points[i][1] <= 10^41 <= r <= 5000
题目链接
https://leetcode-cn.com/problems/maximum-number-of-darts-inside-of-a-circular-dartboard/
思路:
枚举法，在所有的点中任选两个点，假设它们都在圆上，由圆上两点和圆的半径可以得到圆心。枚举所有的圆心，计算在圆内的点数。
两点重合时取经过它们的任意圆都可以。
代码:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
from itertools import combinations class Solution: def numPoints(self, points: List[List[int]], r: int) -> int: CN2 = combinations(points, 2) # iteration ans = 1 for i in CN2: # 由圆上两点和半径求两个圆心 (x1,y1),(x2,y2) = i if x1 != x2: c1 = (x2 ** 2 - x1 ** 2 + y2 ** 2 - y1 ** 2) / 2 / (x2-x1) c2 = (y2-y1) / (x2-x1) A = 1. + c2**2 B = 2*(x1-c1) * c2 - 2 * y1 C = (x1-c1) ** 2 + y1 ** 2 - r ** 2 delta = B**2 - 4*A*C if delta < 0: continue b_ac = math.sqrt(delta) y0 = (-B+b_ac) / (2*A) x0 = c1 - c2 * y0 y1 = (-B - b_ac) / 2 / A x1 = c1-c2*y1 else: if (y2-y1)**2 + (x2-x1) ** 2 < 0: continue d = math.sqrt((y2-y1)**2 + (x2-x1) ** 2) if r**2- (d/2)**2 < 0: continue d = math.sqrt(r**2- (d/2)**2) y0 = (y1+y2)/2 x0 = (x1+d) y1 = (y1+y2)/2 x1 = (x1-d) # print(x0,y0,x1,y1) # 两个圆心 count = 0 for x, y in points: if ((x-x0)**2 + (y-y0)**2 <= r**2): count += 1 ans = max(ans, count) count = 0 for x, y in points: if ((x-x1)**2 + (y-y1)**2 <= r**2): count += 1 ans = max(ans, count) return ans |
