目录

在既定时间做作业的学生人数

给你两个整数数组 startTime（开始时间）和 endTime（结束时间），并指定一个整数 queryTime 作为查询时间。

已知，第 i 名学生在 startTime[i] 时开始写作业并于 endTime[i] 时完成作业。

请返回在查询时间 queryTime 时正在做作业的学生人数。形式上，返回能够使 queryTime 处于区间 [startTime[i], endTime[i]]（含）的学生人数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-students-doing-homework-at-a-given-time

示例

输入：startTime = [1,2,3], endTime = [3,2,7], queryTime = 4
输出：1
解释：一共有 3 名学生。
第一名学生在时间 1 开始写作业，并于时间 3 完成作业，在时间 4 没有处于做作业的状态。
第二名学生在时间 2 开始写作业，并于时间 2 完成作业，在时间 4 没有处于做作业的状态。
第二名学生在时间 3 开始写作业，预计于时间 7 完成作业，这是是唯一一名在时间 4 时正在做作业的学生。

思路

一次遍历循环，判断queryTime是否在startTime[i]和endTime[i]之间即可。时间复杂度O(n)。

代码

1
2
3
4
5
6
7

class Solution:
    def busyStudent(self, startTime: List[int], endTime: List[int], queryTime: int) -> int:
        res = 0
        for time in zip(startTime, endTime):
            if time[0] <= queryTime <= time[1]:
                res += 1
        return res

重新排列句子中的单词

「句子」是一个用空格分隔单词的字符串。给你一个满足下述格式的句子 text :

句子的首字母大写 text 中的每个单词都用单个空格分隔。 请你重新排列 text 中的单词，使所有单词按其长度的升序排列。如果两个单词的长度相同，则保留其在原句子中的相对顺序。

请同样按上述格式返回新的句子。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rearrange-words-in-a-sentence

示例

输入：text = “Leetcode is cool”
输出：“Is cool leetcode”
解释：句子中共有 3 个单词，长度为 8 的 “Leetcode” ，长度为 2 的 “is” 以及长度为 4 的 “cool” 。
输出需要按单词的长度升序排列，新句子中的第一个单词首字母需要大写。

思路

将text先split成字符串列表，然后遍历该列表，用字符串及其在列表的中的位置做成列表放入列表tmp中，同时在遍历过程中记录最短单词长度。
当首单词长度大于最短长度时，说明该单词不在队首了，因此需要将其首字母变成小写。
用匿名函数对tmp排序，首先优先按单词长度排序，然后按单词在原列表中的位置排序。
最后将排序后的首单词的首字母变成大写即可。
不一定正确：sorted()的时间复杂度是O(nlogn)，不确定加了匿名函数后的时间复杂度。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def arrangeWords(self, text: str) -> str:
        text = text.split()
        tmp = []
        minLen = float("inf")
        for i in range(len(text)):
            if len(text[i]) < minLen:
                minLen = len(text[i])
            tmp.append([text[i], i])
        if len(text[0]) > minLen:
            tmp[0][0] = tmp[0][0].lower()
        tmp = sorted(tmp, key=lambda x:(len(x[0]),x[1]))
        res = []
        for t in tmp:
            res.append(t[0])
        res[0] = res[0].capitalize()
        return " ".join(res)

收藏清单

给你一个数组 favoriteCompanies ，其中 favoriteCompanies[i] 是第 i 名用户收藏的公司清单（下标从 0 开始）。

请找出不是其他任何人收藏的公司清单的子集的收藏清单，并返回该清单下标。下标需要按升序排列。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/people-whose-list-of-favorite-companies-is-not-a-subset-of-another-list

示例

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

思路

遍历名单列表，将列表内的名单转为set，并记录这些set里的最大长度。
遍历这些set，因为题目中所有字符串各不相同，所以如果有set的长度等于最大长度，则该set必不是子集。这里做一个剪枝。
对于其它长度的set，用issubset()判断当前set是否是其它set的子集。
因为

1

set[i].issubset(set[j])

可以用

1

set[i] & set[j] == set[i]

代替。

而集合与运算的时间复杂度为O(min(len(set[i],set[j]))，故这里的时间复杂度为O(L*n^2），L为名单长度。
实际上，经leetcode的系统测试，issubset()要比与运算快。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        res = []
        n = len(favoriteCompanies)
        maxLen = 0  
        for i in range(n):
            favoriteCompanies[i] = set(favoriteCompanies[i])
            if maxLen < len(favoriteCompanies[i]):
                maxLen = len(favoriteCompanies[i])
        # favoriteCompanies = sorted(favoriteCompanies, key=lambda x:len(x))
        for i in range(n):
            isSub = False
            if len(favoriteCompanies[i]) == maxLen:
                res.append(i)
                continue
            for j in range(n):
                if i != j and favoriteCompanies[i].issubset(favoriteCompanies[j]):
                    isSub = True
                    break
            if not isSub:
                res.append(i)
        return res

圆形靶内的最大飞镖数量

墙壁上挂着一个圆形的飞镖靶。现在请你蒙着眼睛向靶上投掷飞镖。

投掷到墙上的飞镖用二维平面上的点坐标数组表示。飞镖靶的半径为 r 。

请返回能够落在 任意 半径为 r 的圆形靶内或靶上的最大飞镖数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-number-of-darts-inside-of-a-circular-dartboard

示例

输入：points = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5
输出：5
解释：如果圆形的飞镖靶的圆心为 (0,4) ，半径为 5 ，则除了 (7,8) 之外的飞镖都落在靶上，此时落在靶上的飞镖数最大，值为 5 。

思路

枚举。
选两个点，设这两个点在圆上，通过这两点的坐标及圆的半径求出圆心坐标。
然后枚举所有点判断是否在圆内。
时间复杂度O(n^3)。

代码

 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

import math

class Solution:
    def numPoints(self, points: List[List[int]], r: int) -> int:
        
        def getDist(p1, p2):
            """求p1和p2两点间的距离"""
            return ((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)**0.5
        
        def getCenter(p1, p2):
            """求p1和p2在圆上，半径为r的圆心坐标"""
            mid = [(p1[0]+p2[0]) / 2, (p1[1]+p2[1]) / 2] # 求两点连线中点坐标
            dist = (r**2 - getDist(p1, mid)**2)**0.5 # 勾股定理求圆心到中点的距离
            angle = math.atan2(p1[0]-p2[0],p2[1]-p1[1]) # 求p1-p2连线与??的夹角（弧度） 
            return [mid[0]+dist*math.cos(angle), mid[1]+dist*math.sin(angle)]
        
        n = len(points)
        res = 1
        eps = 1e-8
        for i in range(n):
            for j in range(i+1, n):
                if getDist(points[i], points[j]) > 2 * r:
                    continue
                center = getCenter(points[i], points[j])
                cnt = 0
                for k in range(n):
                    if getDist(center, points[k]) < r + eps:
                        cnt += 1
                res = max(res, cnt)
            
        return res

总结

第一次AK，排名 58/3690。
中间两题用Python的内置函数非常好做。 最后一题是数学问题，因为套了模板，所以不算完全靠自己做的，还是很菜。