图解LeetCode——593. 有效的正方形（难度：中等）

一、题目

给定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

三、解题思路

根据题意，会传入四个点的x轴和y轴的坐标。由于四个点的坐标都是整形，并且输入也不是按照任何顺序给出的。那么我们可以假设有如下集中正方形图形。一个是“端正”的正方形图形，另一个是有“旋转”的正方形图形。对于有旋转的正方形，我们求其对角线就会很方面，通过节点[-1, 0]与节点[1, 0]之间x轴相减并取绝对值即可；在通过节点[0, 1]与节点[0, -1]之间y轴相减并取绝对值即可；但是，对于“端正”正方形却无法采用这种方式。具体情况如下图所示：

3.1> 思路1：相同等腰直角形验证法

针对正方形，我们其实可以将其拆分成四个等腰直角三角形，如下图所示，A^2 + B^2 = C^2，并且对于其他等边也具有相同的等式，并且对于正方形的对角线也都应该是相同的。所以，我们提供一个验证是否合法的方法，传入3个节点的坐标int[] p, int[] pp和int[] ppp，分别计算这3个节点之间的距离（即：边长），与其他两条边长的长度不相等的就是对角线长度了。我们再计算其他3个节点的对角线长度，如果对角线都相同，则说明是正方形，否则，就不是有效的正方形。

计算两个点之间的距离，我们可以采用(A.x轴 - B.x轴)^2 + (A.y轴 - B.y轴)^2结果开根号，由于我们只是去对比边或者对角线是否相同而并非要具体的值，那么我们就直接使用(A.x轴 - B.x轴)^2 + (A.y轴 - B.y轴)^2值来对比即可，不需要再开根号了。

针对四个节点A、B、C和D，我们需要验证ABC、ABD、ACD、BCD这四种情况，如果都满足等腰直角三角形且斜边都相同，那么就满足有效的正方形，否则就不满足。具体代码实现请移步至——4.1> 实现1：相同等腰直角形验证法

3.2> 思路2：正方形边长验证法

除了上面3.1中的解题思路之外，其实我们可以引申除第二种解题思路；在第一种解题思路中，我们是通过计算和对比边和对角线来确定是不是有效的正方形。那么我们其实可以在其中找到一丝规律。就是，对于一个有效的正方形，它的四个边肯定是相同的，那么对于两条对角线，也是彼此相同的，但是，如果我们统计这六条线的长度，我们就会发现，它实际只有两种长度（蓝色线&红色线）。而其他图形就不只是两种长度了。具体情况如下图所示：

确定了解题方向之后，我们也要像思路1一样，提供一个方法，这是这个方法是用于计算两个节点之间的距离，也就是边长。这个方法需要传入两个节点的坐标。不过在思路1和思路2中，需要注意一点，就是要判断重复节点，比如极端情况下，四个节点都是相同的，例如：A[0, 0] ，B[0, 0]，C[0, 0]，D[0, 0]。这种解题实现代码会比思路1少很多，而且逻辑会更简单。具体代码实现请移步至——4.2> 实现2：正方形边长验证法

四、代码实现

4.1> 实现1：相同等腰直角形验证法

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) {
        // 获得三角形的三个边长
        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); 

        // 如果有一个边长度是0，说明两个点重复，直接返回false
        if (size1 == 0 || size2 == 0 || size3 == 0) return false;

        // 如果不满足A^2 + B^2 = C^2，那么说明不是等腰直角三角形，那么不满足正方形约束
        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：正方形边长验证法

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));
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的点赞&分享。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ (^o^)/ ~ 「干货分享，每天更新」