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

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

image.png

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

展开讨论
共 17 个讨论

第一次全部做完。。。。

16

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

每次都差最后一题,难受

6

圆形靶内的最大飞镖数量

此题其实算是高中数学向量部分以及初中数学勾股定理的应用。
考虑一个半径恒定为r的圆,其覆盖若干(≥2)点,现移动这个圆,则必然存在这种情况:这个圆覆盖的点数不变或增加,且其边界至少通过这些点中的2个。
因此,我们只要求通过两点且半径为r的圆心即可。
image.png
一个比较简单的方法是:求出中点,求出法向(和线段垂直),求出距离(用勾股定理)。有了这三项,即可求出圆心的位置。
之后,只要遍历所有的两点,求出圆心,再计算出落在其中的点的数量即可。

class Solution {
    //获得给定两点坐标和半径,获得圆心。
    public double[] getCenter(int x0,int y0,int x1,int y1,int r){
        int dx=x1-x0,dy=y1-y0;
        double dist=Math.sqrt(dx*dx+dy*dy);
        if(dist>2*r)
            return new double[0]; //不可能有圆心
        double midx=(x0+x1)/2.0,midy=(y0+y1)/2.0;
        if(dist==2*r)
            return new double[]{midx,midy}; //圆心只有1种可能
        double offset=Math.sqrt(r*r-dist*dist/4);
        double offx=-dy/dist,offy=dx/dist;
        return new double[]{midx+offx*offset,midy+offy*offset,midx-offx*offset,midy-offy*offset}; //圆心有2种可能
    }

    public int numPoints(int[][] points, int r) {
        int max=1;
        int length=points.length;
        for(int i=0;i<length;i++){
            for(int j=i+1;j<length;j++){
                double[]center=getCenter(points[i][0],points[i][1],points[j][0],points[j][1],r); //获得所有可能的圆心
                if(center.length<=0)continue;
                int count=0;
                for(int t=0;t<length;t++){
                    double dx=points[t][0]-center[0];
                    double dy=points[t][1]-center[1];
                    if(dx*dx+dy*dy<r*r+0.000001) //计算距离时由于double类型大小比较存在精度问题,所以此处略微扩大r
                        count++;
                }
                if(count>max)
                    max=count;
                if(center.length>=4){ //2个圆心需要分别计算
                    count=0;
                    for(int t=0;t<length;t++){
                        double dx=points[t][0]-center[2];
                        double dy=points[t][1]-center[3];
                        if(dx*dx+dy*dy<r*r+0.000001)
                            count++;
                    }
                    if(count>max)
                        max=count;
                }
            }
        }
        return max;
    }
}
6

怎么大家都精通计算几何的...

5

不会最后一道。。。。。三题很多次了

4

这些题对C语言是真心不友好啊

2

哇最后一道题python最后一步圆心到点的距离这个浮点数,处理了我半天。

2

QWQ

1

为什么最新的周赛题在题库里面搜不到呢?

1