自娱自乐的精神乐园

余凯迪的博客

0%

leetcode_189_contest

发表于 更新于 分类于 ， 阅读次数：

通过这次周赛，对Python的喜爱又深了一层。

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

思路：
因为数据量较小并且只查询一次，直接遍历比较即可。
多次查询的话，考虑线段树。

1
2
3
4
5
6
7
class Solution:
    def busyStudent(self, startTime: List[int], endTime: List[int], queryTime: int) -> int:
        res = 0
        for i in range(len(startTime)):
            if startTime[i]<=queryTime<=endTime[i]:
                res += 1
        return res

5413. 重新排列句子中的单词

思路：
Python大法好！！！

1
2
3
4
5
class Solution:
    def arrangeWords(self, text: str) -> str:
        items = text.lower().split(' ')
        items = sorted(items, key = lambda x:len(x))
        return ' '.join(items).capitalize()

5414. 收藏清单

思路：
看数据量不大，直接双重循环即可。运用Python中set相减的操作可快速判断是否为子集。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        res = []
        for i in range(len(favoriteCompanies)):
            flag = False
            for j in range(len(favoriteCompanies)):
                if i==j:
                    continue
                if len(set(favoriteCompanies[i]) - set(favoriteCompanies[j])) == 0:
                    flag=True
            if not flag:
                res.append(i)
        return res

5415. 圆形靶内的最大飞镖数量

思路：
目前看到的做法都是两重循环，根据两个点确定最远的圆心位置，然后遍历判断个数。
通过向量运算确定最远圆心的位置，给出两点$A, B$，中点$m$向量$[(A.x+B.x)/2, (A.y+B.y)/2]$, 向量$\overrightarrow{AB}$为$[(A.x-B.x)/2, (A.y-B.y)/2]$，对应两点连线的单位法向量$\overrightarrow{MP}$为$[(A.y-B.y)/2/|AB|, -(A.x-B.x)/2/|AB|]$，$MP$对应的长度通过勾股定理$AP^2-MP^2$求出， 可得到对应的最远的圆心$P$。
图解
具体的图解可参考：图解圆心计算方法

题解评论区看到的比较精简的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def numPoints(self, points: List[List[int]], r: int) -> int:
        J = lambda o: sum(dist(p, o) <= r for p in points)
        m = 1
        for p1 in points:
            for p2 in points:
                if 0 < dist(p1, p2) <= 2 * r:
                    s = [(p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2]
                    d = [(p1[0] - p2[0]) / 2, (p1[1] - p2[1]) / 2]
                    z = sqrt(r ** 2 - d[0] ** 2 - d[1] ** 2) / hypot(*d)
                    # （d[1]*z, -d[0]*z）是向量垂直连线的向量
                    # p为圆心p1,p2两个点以r为圆心的两个圆的一个交点
                    p = [s[0] + d[1] * z, s[1] - d[0] * z]
                    m = max(m, J(p))
        return m