讨论/题目交流/🏆 第 189 场力扣周赛/
🏆 第 189 场力扣周赛

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

image.png

3 分 - 在既定时间做作业的学生人数
4 分 - 重新排列句子中的单词
5 分 - 收藏清单
7 分 - 圆形靶内的最大飞镖数量

展开讨论
力扣 (LeetCode)发起于 2020-05-17

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

数据范围很小,直接暴力判断每个 query 是否在每个人的 [start, end] 之间即可

B:重新排列句子中的单词

先切割单词,然后按题意的要求进行排序,再对排序后的第一个单词进行处理变为大写开头,再拼回一个单词即可

C:收藏清单

  1. 先对每个人的心仪公司排序:favoriteCompanies 的 size 小的排在前面,size 相同则按里面的每个 company 字典序排序
  2. 进过排序,后者的 favoriteCompanies list 不可能是前者的子集,因此只需要判断前者是否为后者的子集,即对于第 i 人,判断是否为 [i+1, n-1] 人中任意一人的子集
  3. 现在问题转移为,判断 favoriteCompanies[i] 是否为 favoriteCompanies[j] 的子集:由于每个人的 favoriteCompanies 都经过排序,用 two pointer 在两个序列中扫一遍即可
  4. 时间复杂度为 O(n * n * m * len),n 为人数,m 为一个人的 favoriteCompanies 个数,len 为一个公司名的字符串长度

D:圆形靶内的最大飞镖数量

计算几何问题:给定二维平面坐标上的 N 个点的坐标,以及圆的半径 R,确定圆的位置,使得圆可以覆盖最多的点(点可以在圆内或者圆边上)

  1. 首先枚举一个点作为圆心 A,然后再循环其它 N-1 个点,设当前循环到的点为 B

  2. 用 atan2 函数求直线 BA 的极角 th,为方便极角排序,对于负角要 + 2pi

  3. 求圆 A, B 的交点与 AB 的夹角 ph = acos(D / 2),D = dist(A, B)

  4. 计算圆 B 覆盖圆 A 的弧的始末极角 th - ph + 2pi 和 th + ph + 2pi,为了避免负角,每个极角均加2pi。同时加上标记区分始末点

  5. 对这 2 * n 个始末点排序,扫描一遍,得到覆盖次数最多的弧的被覆盖次数,更新答案

7
展开全部 17 讨论