当前位置：网站首页>Graphical LeetCode - 593. Valid Squares (Difficulty: Moderate)

Graphical LeetCode - 593. Valid Squares (Difficulty: Moderate)

2022-07-30 01:24:00 【Java Muse】

一、题目

给定2D空间中四个点的坐标 p1, p2, p3 和 p4,如果这四个点构成一个正方形,则返回 true .

点的坐标 pi 表示为 [xi, yi] .输入不是按任何顺序给出的.

一个 有效的正方形 有四条等边和四个等角(90度角).

二、示例

2.1> 示例 1:

【输入】 p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
【输出】 True

2.2> 示例 2:

【输入】p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]
【输出】false

2.3> 示例 3:

【输入】p1 = [1,0], p2 = [-1,0], p3 = [0,1], p4 = [0,-1]
【输出】true

提示:

p1.length == p2.length == p3.length == p4.length == 2
-104 <= xi, yi <= 104

三、解题思路

根据题意,Four points will be passed inx轴和y轴的坐标.Since the coordinates of the four points are all integers,And the inputs are not given in any order either.Then we can assume that there is a concentrated square graph as follows.一个是“端正”square shape,另一个是有“旋转”square shape.For squares with rotation,If we ask for its diagonal, it will be very square,通过节点[-1, 0]与节点[1, 0]之间x轴Subtract and take the absolute value;passing through the node[0, 1]与节点[0, -1]之间y轴Subtract and take the absolute value;但是,对于“端正”Squares cannot do this.具体情况如下图所示：

3.1> 思路1：The same isosceles right angle verification method

for square,We can actually break it down into four isosceles right triangles,如下图所示,A^2 + B^2 = C^2,And also have the same equation for other equilaterals,And it should all be the same for the diagonals of the square as well.所以,We provide a way to verify if it is legitimate,传入3个节点的坐标int[] p, int[] pp和int[] ppp,分别计算这3个节点之间的距离（即：边长）,The length of the diagonal is not equal to the length of the other two sides.Let's count the others3The diagonal length of a node,If the diagonals are all the same,It means it is a square,否则,is not a valid square.

计算两个点之间的距离,我们可以采用(A.x轴 - B.x轴)^2 + (A.y轴 - B.y轴)^2The result is the root sign,Since we are just comparing whether the sides or diagonals are the same, we don't want specific values,那么我们就直接使用(A.x轴 - B.x轴)^2 + (A.y轴 - B.y轴)^2value to compare,No need to open the root number again.

for four nodesA、B、C和D,我们需要验证ABC、ABD、ACD、BCD这四种情况,If both satisfy an isosceles right triangle and have the same hypotenuse,Then a valid square is satisfied,否则就不满足.For specific code implementation, please move to——4.1> 实现1：The same isosceles right angle verification method

3.2> 思路2：Square side length verification method

除了上面3.1beyond the problem-solving ideas in ,In fact, we can extend to the second problem-solving idea;in the first problem-solving approach,We determine if it is a valid square by counting and comparing the sides and diagonals.Then we can actually find a pattern in it.就是,for a valid square,It must be the same on all four sides,Then for the two diagonals,are also identical to each other,但是,If we count the lengths of these six lines,我们就会发现,It actually only has two lengths（蓝色线&红色线）.And other graphics are not just two lengths.具体情况如下图所示：

After determining the direction of the problem,We also have to think like ideas1一样,提供一个方法,This is the method that is used to calculate the distance between two nodes,That is, the side length.This method needs to pass in the coordinates of two nodes.But in thinking1和思路2中,需要注意一点,It is to judge duplicate nodes,比如极端情况下,All four nodes are the same,例如：A[0, 0] ,B[0, 0],C[0, 0],D[0, 0].This kind of problem-solving implementation code will be better than the idea1少很多,And the logic will be simpler.For specific code implementation, please move to——4.2> 实现2：Square side length verification method

四、代码实现

4.1> 实现1：The same isosceles right angle verification method

class Solution {
    public double hypotenuse = 0.0; // 斜边

    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        return calculate(p1, p2, p3) && calculate(p1, p2, p4) && calculate(p2, p3, p4) && calculate(p1, p3, p4);
    }

    public boolean calculate(int[] p, int[] pp, int[] ppp) {
        // Get the lengths of the three sides of the triangle
        double size1 = Math.pow(p[0] - pp[0], 2) + Math.pow(p[1] - pp[1], 2); 
        double size2 = Math.pow(p[0] - ppp[0], 2) + Math.pow(p[1] - ppp[1], 2); 
        double size3 = Math.pow(pp[0] - ppp[0], 2) + Math.pow(pp[1] - ppp[1], 2); 

        // If there is an edge length is 0,Explain that the two points are repeated,直接返回false
        if (size1 == 0 || size2 == 0 || size3 == 0) return false;

        // 如果不满足A^2 + B^2 = C^2,So it's not an isosceles right triangle,Then the square constraint is not satisfied
        if ((size1 + size2) != size3 && (size1 + size3) != size2 && (size2 + size3) != size1) return false;

        double temp = (size1 == size2) ? size3 : Math.max(size1, size2);
        if (hypotenuse == 0.0) {
            hypotenuse = temp;
        } 

        return hypotenuse == temp;
    }
}

4.2> 实现2：Square side length verification method

class Solution {
    Set<Double> sizeSet;

    public static boolean validSquare1(int[] p1, int[] p2, int[] p3, int[] p4) {
        sizeSet = new HashSet();
        calculate(p1, p2);
        calculate(p1, p3);
        calculate(p1, p4);
        calculate(p2, p3);
        calculate(p2, p4);
        calculate(p3, p4);

        return !sizeSet.contains(0.0) && sizeSet.size() == 2;
    }

    public static void calculate(int[] p, int[] pp) {
        sizeSet.add(Math.pow(p[0] - pp[0], 2) + Math.pow(p[1] - pp[1], 2));
    }
}