当前位置:网站首页>Leetcode simple question: find the nearest point with the same X or Y coordinate
Leetcode simple question: find the nearest point with the same X or Y coordinate
2022-07-05 22:03:00 【·Starry Sea】
subject
Here are two integers x and y , It means that you are in a Cartesian coordinate system (x, y) It's about . meanwhile , Give you an array in the same coordinate system points , among points[i] = [ai, bi] It means that (ai, bi) There's a point in the middle . When a point has the same... As where you are x Coordinates or the same y Coordinates , We call this point Effective .
Please return to your current position Manhattan distance Current It works Subscript of point ( Subscript from 0 Start ). If there are multiple nearest valid points , Please return to subscript Minimum One of the . If it doesn't work , Please return -1 .
Two points (x1, y1) and (x2, y2) Between Manhattan distance by abs(x1 - x2) + abs(y1 - y2)
Example 1:
Input :x = 3, y = 4, points = [[1,2],[3,1],[2,4],[2,3],[4,4]]
Output :2
explain : Of all the points ,[3,1],[2,4] and [4,4] It's effective . In effect ,[2,4] and [4,4] Manhattan is the closest to your current location , All for 1 .[2,4] The lowest subscript of , So back 2 .
Example 2:
Input :x = 3, y = 4, points = [[3,4]]
Output :0
Tips : The answer can be the same as your current position .
Example 3:
Input :x = 3, y = 4, points = [[2,3]]
Output :-1
explain : No, Effective point .
Tips :
1 <= points.length <= 10^4
points[i].length == 2
1 <= x, y, ai, bi <= 10^4
source : Power button (LeetCode)
Their thinking
According to the meaning of the topic , Find the effective point first . The definition of effective point is points The element of has one or two with a given x and y It corresponds to equality , Then the current element is a valid point . Then calculate the distance between the given point and the effective point , Count the nearest valid point and return the subscript .
class Solution:
def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:
distance=float('inf')
index=-1
for i in range(len(points)):
if x==points[i][0] or y==points[i][1]:
if distance>abs(points[i][0]-x)+abs(points[i][1]-y):
distance=abs(points[i][0]-x)+abs(points[i][1]-y)
index=i
return index
边栏推荐
- Talking about MySQL index
- Huawei fast game failed to call the login interface, and returned error code -1
- U盘的文件无法删除文件怎么办?Win11无法删除U盘文件解决教程
- CA certificate trampled pit
- EBS Oracle 11g cloning steps (single node)
- Codeforces 12D Ball 树形阵列模拟3排序元素
- Evolution of large website architecture and knowledge system
- [Yugong series] go teaching course in July 2022 004 go code Notes
- 如何组织一场实战攻防演练
- MySQL disconnection reports an error MySQL ldb_ exceptions. OperationalError 4031, The client was disconnected by the server
猜你喜欢
An exception occurred in Huawei game multimedia calling the room switching method internal system error Reason:90000017
Implementing Lmax disruptor queue from scratch (IV) principle analysis of multithreaded producer multiproducersequencer
Oracle triggers
Common interview questions of redis factory
K210 learning notes (IV) k210 runs multiple models at the same time
Advantages and disadvantages of the "Chris Richardson microservice series" microservice architecture
Sentinel production environment practice (I)
Oracle checkpoint queue - Analysis of the principle of instance crash recovery
Pl/sql basic case
MySQL disconnection reports an error MySQL ldb_ exceptions. OperationalError 4031, The client was disconnected by the server
随机推荐
Oracle checkpoint queue - Analysis of the principle of instance crash recovery
Granularity of blocking of concurrency control
About the writing method of SQL field "this includes" and "included in" strings
Database recovery strategy
如何開發引入小程序插件
Create a virtual machine on VMware (system not installed)
Oracle hint understanding
Regular expressions and re Libraries
AD637 usage notes
Interview questions for basic software testing
Analysis and test of ModbusRTU communication protocol
[Yugong series] go teaching course in July 2022 004 go code Notes
MySQL disconnection reports an error MySQL ldb_ exceptions. OperationalError 4031, The client was disconnected by the server
Getting started with microservices (resttemplate, Eureka, Nacos, feign, gateway)
Decorator learning 01
Codeforces 12D Ball 树形阵列模拟3排序元素
SecureCRT使用提示
CA certificate trampled pit
ICMP introduction
总结出现2xx、3xx、4xx、5xx状态码的原因