1610. 可见点的最大数目

快评

也自己独立完成的一道题,题目很有意思,是雷达扫描场景的抽象问题。思路其实不难想出,但是编码过程中会出现很多corner case,比如笛卡尔坐标转极坐标,比如循环遍历数组等。最后代码成绩还不错,可以直接拿来做一些有趣的事情:)

解题思路

思路很简单:

  1. 在极坐标系中解决,点坐标全部转为相对location的转角,使用一个数组angles存储;
  2. 用双指针(i,j)法扫描angles,求出i,j能拉开的最大距离,即为所求;
  3. 注意第2点扫描的时候需要当作一个循环数组去做,我们不需要自己实现一个循环链表,只需要在快指针j越过尾部时放回头部,并在判断条件中做相应修改即可。

时间复杂度O(NlogN),除了排序部分,其他都写成了O(N)时间的形式。排序部分偷懒直接用sort包了,感兴趣可以写个快排。

file

代码

func visiblePoints(points [][]int, angle int, location []int) int {

    if len(points) <= 1{
        return len(points)
    }

    angles := make([]float64, len(points), len(points))
    angle_f := float64(angle)*math.Pi/180
    x_c := float64(location[0])
    y_c := float64(location[1])

    for i, point := range points{
        if point[0]==location[0] && point[1]==location[1] {
            angles[i] = -1
        }else if point[0]==location[0] && point[1]>location[1] {
            angles[i] = math.Pi/2
        }else if point[0]==location[0] && point[1]<location[1] {
            angles[i] = 3*math.Pi/2
        }else if point[0]<=location[0]{
            angles[i] = math.Pi + math.Atan((float64(point[1])-y_c)/(float64(point[0])-x_c))
        }else if point[0]>=location[0] && point[1]<location[1]{
            angles[i] = 2*math.Pi + math.Atan((float64(point[1])-y_c)/(float64(point[0])-x_c))
        }else{
            angles[i] = math.Atan((float64(point[1])-y_c)/(float64(point[0])-x_c))
        }
    }
    sort.Float64s(angles)

    pre_conut := 0
    i := 0
    for ;i<len(angles);i++{
        if angles[i] == -1{
            pre_conut++
        }else{
            break
        }
    }

    max_count := 0
    j := i

    for ;j<len(angles);{
        if angles[j]-angles[i]<=angle_f{
            if j-i+1>max_count{
                max_count = j-i+1
            }
            j++
        }else{
            for ;i<=j;{
                i++
                if angles[j]-angles[i]<=angle_f{
                    break
                }
            }
        }
    }

    for j=pre_conut;j<i&&i<len(angles);{
        if angles[j]+2*math.Pi-angles[i]<=angle_f{
            if j+len(angles)-i-pre_conut+1>max_count{
                max_count = j+len(angles)-i+1-pre_conut
            }
            j++
        }else{
            for ;i<len(angles);{
                i++
                if i<len(angles) && angles[j]+2*math.Pi-angles[i]<=angle_f{
                    break
                }
            }
        }
    }

    return pre_conut + max_count
}

类似文章

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注