Leetcode1610. Maximum Number of Visible Points (python+cpp)

题目

解析：错误解法

这道题简单来说就是雷达扫点的问题。一开始我想入了一种错误思路。就是类似于动雷达的方式然后判断在当前的范围内有多少个点这样。但是问题是对于雷达应该转任意角度都可以，所以遍历这个转的角度并不行

class Solution:def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:import mathdef compute_angle(ori,point):x1,y1 = ori[0],ori[1]x2,y2 = point[0],point[1]dx = x2-x1dy = y2-y1angle = math.atan2(dy,dx)angle = angle*180/math.piif dx<0 and dy<0:angle = 360+angleif dx>0 and dy<0:angle = 360+anglereturn anglemax_count = 0for d in range(361):count = 0for point in points:temp_angle = compute_angle(location,point)if d-angle/2<=temp_angle<=d+angle/2 or (point[0]==location[0] and point[1]==location[1]):count += 1max_count = max(count,max_count)return max_count

不过这边有个技巧比较值得注意，就是计算两个点的连线和X轴正半轴的夹角，正确的写法如下：

import math
''' atan2(y, x)是4象限反正切，它的取值不仅取决于正切值y/x，还取决于点 (x, y) 落入哪个象限：当点(x, y) 落入第一象限时，atan2(y, x)的范围是 0 ~ pi/2; 当点(x, y) 落入第二象限时，atan2(y, x)的范围是 pi/2 ~ pi; 当点(x, y) 落入第三象限时，atan2(y, x)的范围是 －pi～－pi/2; 当点(x, y) 落入第四象限时，atan2(y, x)的范围是 -pi/2～0. '''
def compute_angle(ori,point):x1,y1 = ori[0],ori[1]x2,y2 = point[0],point[1]dx = x2-x1dy = y2-y1angle = math.atan2(dy,dx)angle = angle*180/math.piif (dx<0 and dy<0) or (dx>0 and dy<0):angle = 360+anglereturn angleori = [0,0]
points = [[2,1],[-2,1],[-2,-1],[2,-1]]
for point in points:print(compute_angle(ori,point))

正确解法：

正确的思路应该是将点的角度排序，然后滑窗去找能覆盖最多点的区间。因为排序之后只需要找到左右边界，然后计算边界内有多少个点就可以了
这边要注意和原点重合的点需要额外计算，然后因为是环形的sliding window，所以常见的技巧是将原来的数组double一下

class Solution:def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:arr, extra = [], 0xx, yy = locationfor x, y in points:if x == xx and y == yy:extra += 1continuearr.append(math.atan2(y - yy, x - xx))arr.sort()arr = arr + [x + 2.0 * math.pi for x in arr]angle = math.pi * angle / 180r = ans = 0for l in range(len(arr)):while r<len(arr) and arr[r]-angle<=arr[l]:r += 1ans = max(ans,r-l)return ans + extra

这边注意滑窗的技巧，遍历左边界，然后右边界滑动寻找下一个不符合条件的点

C++版本
注意一下C++计算角度的函数名相同
pi的表示

class Solution {
    
public:int visiblePoints(vector<vector<int>>& points, int angle, vector<int>& location) {
    vector<double> arr;int extra = 0;for(auto point : points){
    if(point[0] == location[0] && point[1] == location[1]){
    extra += 1;continue;}arr.push_back(atan2(point[1]-location[1],point[0]-location[0]));}sort(arr.begin(),arr.end());int n = arr.size();for(int i=0;i<n;i++){
    arr.push_back(arr[i]+2*M_PI);}int max_point = 0;int l = 0, r = 0;while(r < arr.size()){
    while(l < r && arr[r] - arr[l] > angle*M_PI/180.0){
    l += 1;}max_point = max(max_point,r-l+1);r += 1;}return max_point + extra;}
};