Skip to content

Latest commit

 

History

History
201 lines (141 loc) · 6.59 KB

0593._Valid_Square.md

File metadata and controls

201 lines (141 loc) · 6.59 KB
Raw

593. Valid Square

难度: 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个条件就行，

  1. 每个点都不相等，处理掉比如4个点都是(0, 0)啥的case
  2. 4条边相等
  3. 其中2条边夹角为90度

或者，

  1. 每个点都不相等，处理掉比如4个点都是(0, 0)啥的case
  2. 有其中一组相邻边相等
  3. 有一对对角均为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

  1. 如果4个点中有两个点相等，那么肯定不行
  2. 如果是菱形，肯定不行，即夹角不为90度
  3. 如果相邻边长度不相等，那肯定不行

满足以上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

Follow up

如果给一个列表的点，返回一共能组成多少个正方形。input里面可能有重复的点

开始我很sb的想着4 个 for loop取得4个点，然后用上面的函数判断是否可以组成正方形，最后叠加结果并且返回

这里感谢微信墨汁大佬的指导，

  • 首先将input去重
  • 然后可以先将所有点放到一个字典里面去
  • 然后我们用2个for loop去确定好2个点，根据正方形的性质我们就可以自己算出正方形的另外两个点了
  • 随后我们判断这两个点是否在我们的字典里面

这样我们最终的时间复杂度是O(N^2)，空间复杂度是O(N)，完美！！