leetcode1610. 可见点的最大数目(java)
可见点的最大数目
- 题目描述
- 滑动窗口
题目描述
难度 - 困难
leetcode1610. 可见点的最大数目
给你一个点数组 points 和一个表示角度的整数 angle ,你的位置是 location ,其中 location = [posx, posy] 且 points[i] = [xi, yi] 都表示 X-Y 平面上的整数坐标。
最开始,你面向东方进行观测。你 不能 进行移动改变位置,但可以通过 自转 调整观测角度。换句话说,posx 和 posy 不能改变。你的视野范围的角度用 angle 表示, 这决定了你观测任意方向时可以多宽。设 d 为你逆时针自转旋转的度数,那么你的视野就是角度范围 [d - angle/2, d + angle/2] 所指示的那片区域。
对于每个点,如果由该点、你的位置以及从你的位置直接向东的方向形成的角度 位于你的视野中 ,那么你就可以看到它。
同一个坐标上可以有多个点。你所在的位置也可能存在一些点,但不管你的怎么旋转,总是可以看到这些点。同时,点不会阻碍你看到其他点。
返回你能看到的点的最大数目。
示例1:
输入:points = [[2,1],[2,2],[3,3]], angle = 90, location = [1,1]
输出:3
解释:阴影区域代表你的视野。在你的视野中,所有的点都清晰可见,尽管 [2,2] 和 [3,3]在同一条直线上,你仍然可以看到 [3,3] 。
示例 2:
输入:points = [[2,1],[2,2],[3,4],[1,1]], angle = 90, location = [1,1]
输出:4
解释:在你的视野中,所有的点都清晰可见,包括你所在位置的那个点。
输入:points = [[1,0],[2,1]], angle = 13, location = [1,1]
输出:1
解释:如图所示,你只能看到两点之一。
提示:
1 <= points.length <= 10^5
points[i].length == 2
location.length == 2
0 <= angle < 360
0 <= posx, posy, xi, yi <= 100

滑动窗口
今天这道题其实没那么难,我们只需要算出每个坐标相对于 location 与 x 轴的夹角,然后,找到以每个坐标为起点,放置 angle 角度,这么大的辐射范围内的点数的最大值即可。
假设,我们有上图所示的坐标系,里面有一些点,人所在的位置如图中小人标识位置,假设给定的辐射范围 angle 为 90°,那么,我们的计算过程如下:
先算出每个点与人位置坐标与 x 轴的夹角;
把这些点扔到 list 里面,并排序;
为了处理 180° 到 -180° 的过度,我们可以把所有的坐标加上 360° 再加一遍到 list 中。
遍历每一个坐标夹角 x,统计 [x, x+angle] 范围内的点数,这个过程我们可以使用滑动窗口或者二分查找实现,最后返回最大的点数即可。
注意,题目约定了你所在的位置也可能存在点,这些点需要特殊处理。
另外,本题我们可以使用库函数 atan2 直接计算出夹角对应的弧度值,atan2 的返回值为 [-π, π]:
代码演示:
public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {int x = location.get(0), y = location.get(1);List<Double> list = new ArrayList<>();int cnt = 0;double pi = Math.PI, t = angle * pi / 180;for (List<Integer> p : points) {int a = p.get(0), b = p.get(1);if (a == x && b == y && ++cnt >= 0) continue;list.add(Math.atan2(b - y, a - x) + pi);}Collections.sort(list);int n = list.size(), max = 0;for (int i = 0; i < n; i++) list.add(list.get(i) + 2 * pi);for (int i = 0, j = 0; j < 2 * n; j++) {while (i < j && list.get(j) - list.get(i) > t) i++;max = Math.max(max, j - i + 1);}return cnt + max;}
相关文章:
leetcode1610. 可见点的最大数目(java)
可见点的最大数目 题目描述滑动窗口 题目描述 难度 - 困难 leetcode1610. 可见点的最大数目 给你一个点数组 points 和一个表示角度的整数 angle ,你的位置是 location ,其中 location [posx, posy] 且 points[i] [xi, yi] 都表示 X-Y 平面上的整数坐标…...
Apache Flume
Flume 1.9.0 Developer Guide【Flume 1.9.0开发人员指南】 Introduction【介绍】 摘自:Flume 1.9.0 Developer Guide — Apache Flume Overview【概述】 Apache Flume is a distributed, reliable, and available system for efficiently collecting, aggregati…...
【切片】基础不扎实引发的问题
本次文章主要是来聊聊关于切片传值需要注意的问题,如果不小心,则很容易引发线上问题,如果不够理解,可能会出现奇奇怪怪的现象 问题情况: 小 A 负责一个模块功能的实现,在调试代码的时候可能不仔细&#x…...
CVE-2023-5129 libwebp堆缓冲区溢出漏洞影响分析
漏洞简述 近日苹果、谷歌、Mozilla和微软等公司积极修复了libwebp组件中的缓冲区溢出漏洞,相关时间线如下: 9月7日,苹果发布紧急更新,修复了此前由多伦多大学公民实验室报告的iMessage 0-click 漏洞,漏洞被认为已经被…...
leetcode做题笔记155. 最小栈
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。 实现 MinStack 类: MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int get…...
蓝海彤翔亮相2023新疆网络文化节重点项目“新疆动漫节”
9月22日上午,2023新疆网络文化节重点项目“新疆动漫节”(以下简称“2023新疆动漫节”)在克拉玛依科学技术馆隆重开幕,蓝海彤翔作为国内知名的文化科技产业集团应邀参与此次活动,并在美好新疆e起向未来动漫展映区设置展…...
【AI视野·今日NLP 自然语言处理论文速览 第四十四期】Fri, 29 Sep 2023
AI视野今日CS.NLP 自然语言处理论文速览 Fri, 29 Sep 2023 Totally 45 papers 👉上期速览✈更多精彩请移步主页 Daily Computation and Language Papers MindShift: Leveraging Large Language Models for Mental-States-Based Problematic Smartphone Use Interve…...
【VsCode】vscode创建文件夹有小图标显示和配置
效果 步骤 刚安装软件后, 开始工作目录下是没有小图标显示的。 如下图操作,安装vscode-icons 插件,重新加载即可 创建文件夹,显示图标如下:...
celery分布式异步任务队列-4.4.7
文章目录 celery介绍兼容性简单使用安装使用方式 功能介绍常用案例获取任务的返回值任务中使用logging定义任务基类 任务回调函数No result will be storedResult will be stored任务的追踪、失败重试 python setup.py installln -s /run/shm /dev/shmOptional configuration, …...
解决M2苹果芯片Mac无法安装python=3.7的虚拟环境
问题描述 conda无法安装python3.7的虚拟环境: conda create -n py37 python3.7出现错误 (base) ➜ AzurLaneAutoScript git:(master) conda create -n alas python3.7.6 -y Collecting package metadata (current_repodata.json): done Solving environment: fa…...
Sound/播放提示音, Haptics/触觉反馈, LocalNotification/本地通知 的使用
1. Sound 播放提示音 1.1 音频文件: tada.mp3, badum.mp3 1.2 文件位置截图: 1.3 实现 import AVKit/// 音频管理器 class SoundManager{// 单例对象 Singletonstatic let instance SoundManager()// 音频播放var player: AVAudioPlayer?enum SoundOption: Stri…...
Oracle实现主键字段自增
Oracle实现主键自增有4种方式: Identity Columns新特性自增(Oracle版本≥12c)创建自增序列,创建表时,给主键字段默认使用自增序列创建自增序列,使用触发器使主键自增创建自增序列,插入语句&…...
【C++数据结构】二叉树搜索树【完整版】
目录 一、二叉搜索树的定义 二、二叉搜索树的实现: 1、树节点的创建--BSTreeNode 2、二叉搜索树的基本框架--BSTree 3、插入节点--Insert 4、中序遍历--InOrder 5、 查找--Find 6、 删除--erase 完整代码: 三、二叉搜索树的应用 1、key的模型 &a…...
TouchGFX之字体缓存
使用二进制字体需要将整个字体加载到存储器。 在某些情况下,如果字体很大,如大字号中文字体,则这样做可能不可取。 字体缓存使应用能够从外部存储器只能加载显示字符串所需的字母。 这意味着整个字体无需保存到在可寻址闪存或RAM上ÿ…...
windows系统关闭软件开机自启的常用两种方法
win10中安装软件时经常会默认开机自启动,本文主要介绍两种关闭软件开机自启动方法。 方法1 通过任务管理器设置 1.在任务管理器中禁用开机自启动:打开任务管理器,右键已启动的软件,选择禁用。 方法2 通过windows服务控制开机自启…...
巧用@Conditional注解根据配置文件注入不同的bean对象
项目中使用了mq,kafka两种消息队列进行发送数据,为了避免硬编码,在项目中通过不同的配置文件自动识别具体消息队列策略。这里整理两种实施方案,仅供参考! 方案一:创建一个工具类,然后根据配置文…...
论文笔记(整理):轨迹相似度顶会论文中使用的数据集
0 汇总 数据类型数据名称数据处理出租车数据波尔图 原始数据:2013年7月到2014年6月,170万条数据 ICDE 2023 Contrastive Trajectory Similarity Learning with Dual-Feature Attention 过滤位于城市(或国家)区域之外的轨迹 过…...
Python实现单例模式
使用函数装饰器 def singleton(cls):_instance {}def inner():if cls not in _instance:_instance[cls] cls()return _instance[cls]return innersingleton class Demo(object):def __init__(self):passdef test():b1 Demo()b2 Demo()print(b1, b2)使用类装饰器 class si…...
spark相关网站
Spark的五种JOIN策略解析 https://www.cnblogs.com/jmx-bigdata/p/14021183.html 万字详解整个数据仓库建设体系(好文值得收藏) https://mp.weixin.qq.com/s?__bizMzg2MzU2MDYzOA&mid2247484692&idx1&snf624672e62ba6cd4cc69bdb6db28756a&…...
ThreeJS-3D教学四-光源
three模拟的真实3D环境,一个非常炫酷的功能便是对光源的操控,之前教学一中已经简单的描述了多种光源,这次咱们就详细的讲下一些最常见的光源: AmbientLight 该灯光在全局范围内平等地照亮场景中的所有对象。 该灯光不能用于投射阴…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
黑马Mybatis
Mybatis 表现层:页面展示 业务层:逻辑处理 持久层:持久数据化保存 在这里插入图片描述 Mybatis快速入门 医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...

输入:points = [[2,1],[2,2],[3,3]], angle = 90, location = [1,1]
输入:points = [[1,0],[2,1]], angle = 13, location = [1,1]