难度: Medium
原题连接
内容描述
Given the coordinates of four points in 2D space, return whether the four points could construct a square.
The coordinate (x,y) of a point is represented by an integer array with two integers.
Example:
Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: True
Note:
All the input integers are in the range [-10000, 10000].
A valid square has four equal sides with positive length and four equal angles (90-degree angles).
Input points have no order.
思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******
只要满足3个条件就行,
- 每个点都不相等,处理掉比如4个点都是(0, 0)啥的case
- 4条边相等
- 其中2条边夹角为90度
或者,
- 每个点都不相等,处理掉比如4个点都是(0, 0)啥的case
- 有其中一组相邻边相等
- 有一对对角均为90度
第一种方式代码如下:
class Solution(object):
def validSquare(self, p1, p2, p3, p4):
"""
:type p1: List[int]
:type p2: List[int]
:type p3: List[int]
:type p4: List[int]
:rtype: bool
"""
# corner cases
points = [p1, p2, p3, p4]
for i in range(len(points)):
for j in range(i + 1, len(points)):
if points[i][0] == points[j][0] and points[i][1] == points[j][1]:
return False
points = sorted(points, key=lambda p: (p[0], p[1])) # []
import math
# for this part , we calculate the four sides
tmp = pow(points[-1][0] - points[1][0], 2) + pow(points[-1][1] - points[1][1], 2)
len_bottom = math.sqrt((tmp))
tmp = pow(points[-2][0] - points[0][0], 2) + pow(points[-2][1] - points[0][1], 2)
len_top = math.sqrt((tmp))
tmp = pow(points[1][0] - points[0][0], 2) + pow(points[1][1] - points[0][1], 2)
len_left = math.sqrt((tmp))
tmp = pow(points[-1][0] - points[-2][0], 2) + pow(points[-1][1] - points[-2][1], 2)
len_right = math.sqrt((tmp))
# now this is our angle part
vector_bottom = [points[-1][0] - points[1][0], points[-1][1] - points[1][1]]
vector_left = [points[1][0] - points[0][0], points[1][1] - points[0][1]]
dikall = vector_bottom[0] * vector_left[0] + vector_bottom[1] * vector_left[1]
if len_bottom == len_top == len_left == len_right and dikall == 0:
return True
return False
第二种代码如下:
class Solution(object):
def validSquare(self, p1, p2, p3, p4):
"""
:type p1: List[int]
:type p2: List[int]
:type p3: List[int]
:type p4: List[int]
:rtype: bool
"""
# corner cases
points = [p1, p2, p3, p4]
for i in range(len(points)):
for j in range(i + 1, len(points)):
if points[i][0] == points[j][0] and points[i][1] == points[j][1]:
return False
points = sorted(points, key=lambda p: (p[0], p[1])) # []
import math
# for this part , we calculate the four sides
tmp = pow(points[-1][0] - points[1][0], 2) + pow(points[-1][1] - points[1][1], 2)
len_bottom = math.sqrt((tmp))
tmp = pow(points[1][0] - points[0][0], 2) + pow(points[1][1] - points[0][1], 2)
len_left = math.sqrt((tmp))
# now this is our angle part
vector_bottom = [points[-1][0] - points[1][0], points[-1][1] - points[1][1]]
vector_left = [points[1][0] - points[0][0], points[1][1] - points[0][1]]
vector_top = [points[2][0] - points[0][0], points[2][1] - points[0][1]]
vector_right = [points[2][0] - points[-1][0], points[2][1] - points[-1][1]]
vec_product1 = vector_bottom[0] * vector_left[0] + vector_bottom[1] * vector_left[1]
vec_product2 = vector_top[0] * vector_right[0] + vector_top[1] * vector_right[1]
if len_bottom == len_left and vec_product1 == vec_product2 == 0:
return True
return False
思路 2 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******
这个思路是根据后面Follow up大佬告诉我的,根据三个点就可以算出正方形的第四个点了,然后我们需要考虑的就是下面的几个case
- 如果4个点中有两个点相等,那么肯定不行
- 如果是菱形,肯定不行,即夹角不为90度
- 如果相邻边长度不相等,那肯定不行
满足以上3个条件,就返回True,否则返回False
class Solution(object):
def validSquare(self, p1, p2, p3, p4):
"""
:type p1: List[int]
:type p2: List[int]
:type p3: List[int]
:type p4: List[int]
:rtype: bool
"""
points = [p1, p2, p3, p4]
points = sorted(points, key=lambda p: (p[0], p[1]))
for i in range(len(points)): # for same point case
for j in range(i + 1, len(points)):
if points[i][0] == points[j][0] and points[i][1] == points[j][1]:
return False
x4, y4 = points[2][0] + points[1][0] - points[0][0], points[1][1] - points[0][1] + points[2][1]
if x4 == points[-1][0] and y4 == points[-1][1]: # for point4 not exist case
distance_bottom = pow((x4-points[1][0]), 2) + pow((y4-points[1][1]), 2)
distance_left = pow((points[0][1]-points[1][1]), 2) + pow((points[0][0]-points[1][0]), 2)
if distance_bottom == distance_left: # for diamond case
vec_product = (x4-points[1][0]) * (points[0][0]-points[1][0]) + (y4-points[1][1]) * (points[0][1]-points[1][1])
if vec_product == 0: # for angle != 90 degree case
return True
return False
如果给一个列表的点,返回一共能组成多少个正方形。input里面可能有重复的点
开始我很sb的想着4 个 for loop取得4个点,然后用上面的函数判断是否可以组成正方形,最后叠加结果并且返回
这里感谢微信墨汁大佬的指导,
- 首先将input去重
- 然后可以先将所有点放到一个字典里面去
- 然后我们用2个for loop去确定好2个点,根据正方形的性质我们就可以自己算出正方形的另外两个点了
- 随后我们判断这两个点是否在我们的字典里面
这样我们最终的时间复杂度是O(N^2),空间复杂度是O(N),完美!!