LeetCode刷题-有效的正方形

前言说明

算法学习，日常刷题记录。

题目连接

有效的正方形

题目内容

给定二维空间中四点的坐标，返回四点是否可以构造一个正方形。

一个点的坐标(x，y)由一个有两个整数的整数数组表示。

示例:

输入: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]

输出: true

注意：

所有输入整数都在 [-10000，10000] 范围内。

一个有效的正方形有四个等长的正长和四个等角(90度角)。

输入点没有顺序。

分析过程

这里展示我的做题分析过程，先想出方法1，但是方法1是错误的；后来改进为方法2，但是方法2也是错误的；然后改进为方法3，但是方法3也是错误的；接着再改进为方法4，终于正确；最后想出方法5，用另一种更加简洁的思路解决。

方法1(错误)

如果四个点能构成正方形，那么三个点就能构成三角形，所以通过勾股定理判断三个点是否能构成三角形。

求两点之间的距离，用求距离的公式：

两点距离的公式

挑选三个点的两两距离定义为p12、p13、p23，因为如果是正方形就有p23 = p14，所以转化为判断p12 ^ 2 + p13 ^ 2 = p14 ^ 2是否成立。

代码如下：

class Solution {
    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        // p1和p2之间的距离，根据公式，a点和b点的距离 = (a^2 + b^2)的开根号
        double p12 = Math.sqrt(Math.pow((p1[0] - p2[0]), 2) + Math.pow((p1[1] - p2[1]), 2));

        // p1和p3之间的距离
        double p13 = Math.sqrt(Math.pow((p1[0] - p3[0]), 2) + Math.pow((p1[1] - p3[1]), 2));

        // p1和p4之间的距离
        double p14 = Math.sqrt(Math.pow((p1[0] - p4[0]), 2) + Math.pow((p1[1] - p4[1]), 2));

        // 若四个点能构成正方形，那么三个点就能构成三角形，根据勾股定理，如果p12^2 + p13^2 = p23^2，那么这三点就能构成三角形，如果是正方形，那么交叉线相等，所以p14 = p23，所以p12^2 + p13^2 = p14^2，所以这里只需要判断p12^2 + p13^2 = p14^2是否成立即可，如果成立，那么四个点能构成正方形，否则不能(注意：这里的顺序可能会不同，所以要判断三种情况，有一种情况满足即可)
        return Math.pow(p12, 2) + Math.pow(p13, 2) == Math.pow(p14, 2) || Math.pow(p12, 2) + Math.pow(p14, 2) == Math.pow(p13, 2) || Math.pow(p13, 2) + Math.pow(p14, 2) == Math.pow(p12, 2);
    }
}

但是还没有提交，仅仅是执行代码就发现结果不对了。

运行结果错误

为什么呢？因为开方导致了精度丢失，而且就算三个点能构成三角形，也不能证明四个点能构成正方形，也有可能是长方形。

方法2(错误)

所以我对方法1进行改进，改为判断三个点是否能构成等腰直角三角形。

计算距离时只计算距离的平方，因为距离的平方再开方，首先是多此一举，其次是开方后会精度丢失，导致结果错误。

依然是挑选三个点的两两距离定义为p12、p13、p23，因为如果是正方形就有p23 = p14，所以转化为判断p12 ^ 2 + p13 ^ 2 = p14 ^ 2是否成立。

代码如下：

class Solution {
    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        // p1和p2之间的距离的平方，根据公式，a点和b点的距离 = (a^2 + b^2)的开根号
        double p12 = Math.pow((p1[0] - p2[0]), 2) + Math.pow((p1[1] - p2[1]), 2);

        if (p12 == 0) {
            // // 点p1和点p2不能重复，若有两个点的距离的平方等于0，那么两个点的距离等于0，那么两个点重合，有两个点重合就可能构成正方形
            return false;
        }

        // p1和p3之间的距离的平方
        double p13 = Math.pow((p1[0] - p3[0]), 2) + Math.pow((p1[1] - p3[1]), 2);

        if (p13 == 0) {
            // 点p1和点p3不能重复
            return false;
        }

        // p1和p4之间的距离的平方
        double p14 = Math.pow((p1[0] - p4[0]), 2) + Math.pow((p1[1] - p4[1]), 2);

        if (p14 == 0) {
            // 点p1和点p4不能重复
            return false;
        }

        // 若四个点能构成正方形，那么三个点就能构成等腰直角三角形，根据勾股定理，如果p12 == p13并且p12^2 + p13^2 = p23^2，那么这三点就能构成等腰直角三角形，如果是正方形，那么交叉线相等，所以p14 = p23，所以p12^2 + p13^2 = p14^2，所以这里只需要判断p12^2 + p13^2 = p14^2是否成立即可，如果成立，那么四个点能构成正方形，否则不能(注意：这里的顺序可能会不同，所以要判断三种情况，有一种情况满足即可)

        // 这里前面不开根号，直接保留平方，这里判断的时候直接使用上面计算好的平方来判断
        // 前面不能开根号，因为开根号后精度会丢失，开根号后这里再平方一次，已经不是原来的值了
        return (p12 == p13 && p12 + p13 == p14) || (p12 == p14 && p12 + p14 == p13) || (p13 == p14 && p13 + p14 == p12);
    }
}

提交代码后，提示运行错误。

运行错误结果

输入[0,1],[1,2],[0,2],[0,0]时，运行错误。

我们分析发现，[0,1],[1,2],[0,2],[0,0]，实际上是三个点在一条直线上，无法组成正方形，如图：

三点一线

假如p1为点A，p2为点D，p3为点C，p4为点B，那么p12 ^ 2 = 1，p13 ^ 2 = 1，p14 ^ 2 = 2，刚好p12 = p13，并且p12 + p13 = p14。

我们从图中可以看出，不能用另一条对角线来代替判断是否能构成三角形，必须用p12、p13、p23来判断，p23不能用p14来代替。

方法3(错误)

根据上面的结论，不能用另一条对角线来代替判断是否能构成三角形，必须用p12、p13、p23来判断。

代码如下：

class Solution {
    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        // p1和p2之间的距离的平方，根据公式，a点和b点的距离 = (a^2 + b^2)的开根号
        double p12 = Math.pow((p1[0] - p2[0]), 2) + Math.pow((p1[1] - p2[1]), 2);

        if (p12 == 0) {
            // // 点p1和点p2不能重复，若有两个点的距离的平方等于0，那么两个点的距离等于0，那么两个点重合，有两个点重合就可能构成正方形
            return false;
        }

        // p1和p3之间的距离的平方
        double p13 = Math.pow((p1[0] - p3[0]), 2) + Math.pow((p1[1] - p3[1]), 2);

        if (p13 == 0) {
            // 点p1和点p3不能重复
            return false;
        }

        // p2和p3之间的距离的平方
        double p23 = Math.pow((p2[0] - p3[0]), 2) + Math.pow((p2[1] - p3[1]), 2);

        if (p23 == 0) {
            // 点p1和点p4不能重复
            return false;
        }

        // 若四个点能构成正方形，那么三个点就能构成等腰直角三角形，根据勾股定理，如果p12 == p13并且p12^2 + p13^2 = p23^2，那么这三点就能构成等腰直角三角形(注意：这里的顺序可能会不同，所以要判断三种情况，有一种情况满足即可)

        // 这里前面不开根号，直接保留平方，这里判断的时候直接使用上面计算好的平方来判断
        // 前面不能开根号，因为开根号后精度会丢失，开根号后这里再平方一次，已经不是原来的值了
        return (p12 == p13 && p12 + p13 == p23) || (p12 == p23 && p12 + p23 == p13) || (p13 == p23 && p13 + p23 == p12);
    }
}

但是提交代码后，还是提示运行错误。

运行结果错误

输入[0,1],[1,1],[1,0],[0,2]时，运行错误。

我们分析发现，[0,1],[1,1],[1,0],[0,2]，实际上是一个菱形，如图：

菱形

假如p1为点B，p2为点A，p3为点C，那么p12 ^ 2 = 1，p13 ^ 2 = 1，p23 ^ 2 = 2，刚好p12 = p13，并且p12 + p13 = p23。

所以只判断一对三个点是否能构成等腰直角三角形是不够的，必须判断任意三个点是否能构成等腰直角三角形才可以。

方法4(正确)

按照前面的思路，判断任意三个点是否能构成等腰直角三角形。

把前面方法3改为一个专门判断三个点是否能构成等腰直角三角形的函数。

四次调用这个函数，传入四种情况，如果每一种情况都返回true，那么每一种情况都能构成等腰直角三角形，那么任意三个点都能构成等腰直角三角形，那么这四个点构成正方形。

代码如下：

class Solution {
    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        // 判断任意三个点是否构成等腰直角三角形
        return judgeTriangle(p1, p2, p3) && judgeTriangle(p1, p2, p4) && judgeTriangle(p1, p3, p4) && judgeTriangle(p2, p3, p4);
    }

    private boolean judgeTriangle(int[] p1, int[] p2, int[] p3) {
        // p1和p2之间的距离的平方，根据公式，a点和b点的距离 = (a^2 + b^2)的开根号
        double p12 = Math.pow((p1[0] - p2[0]), 2) + Math.pow((p1[1] - p2[1]), 2);

        if (p12 == 0) {
            // // 点p1和点p2不能重复，若有两个点的距离的平方等于0，那么两个点的距离等于0，那么两个点重合，有两个点重合就可能构成正方形
            return false;
        }

        // p1和p3之间的距离的平方
        double p13 = Math.pow((p1[0] - p3[0]), 2) + Math.pow((p1[1] - p3[1]), 2);

        if (p13 == 0) {
            // 点p1和点p3不能重复
            return false;
        }

        // p2和p3之间的距离的平方
        double p23 = Math.pow((p2[0] - p3[0]), 2) + Math.pow((p2[1] - p3[1]), 2);

        if (p23 == 0) {
            // 点p1和点p4不能重复
            return false;
        }

        // 若四个点能构成正方形，那么三个点就能构成正三角形，根据勾股定理，如果p12 == p13并且p12^2 + p13^2 = p23^2，那么这三点就能构成正三角形，如果是正方形，那么交叉线相等，所以p14 = p23，所以p12^2 + p13^2 = p14^2，所以这里只需要判断p12^2 + p13^2 = p14^2是否成立即可，如果成立，那么四个点能构成正方形，否则不能(注意：这里的顺序可能会不同，所以要判断三种情况，有一种情况满足即可)

        // 这里前面不开根号，直接保留平方，这里判断的时候直接使用上面计算好的平方来判断
        // 前面不能开根号，因为开根号后精度会丢失，开根号后这里再平方一次，已经不是原来的值了
        return (p12 == p13 && p12 + p13 == p23) || (p12 == p23 && p12 + p23 == p13) || (p13 == p23 && p13 + p23 == p12);
    }
}

提交代码后，提示运行正确。

运行结果

执行用时1ms，时间击败80.58%的用户，内存消耗36.4MB，空间击败13.27%的用户。

方法5(正确)

我发现前面的思路过于繁杂，所以决定弃用上面的思路，改用其它思路。

先求出任意两个点的距离，一共六个距离。

如果这六个距离，没有0并且只有两种距离，那么就是正方形。

代码如下：

class Solution {
    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        // 这里只计算距离的平方即可，不用开根号多此一举

        // p1和p2之间的距离的平方，根据公式，a点和b点的距离 = (a^2 + b^2)的开根号
        double p12 = Math.pow((p1[0] - p2[0]), 2) + Math.pow((p1[1] - p2[1]), 2);

        // p1和p3之间的距离的平方
        double p13 = Math.pow((p1[0] - p3[0]), 2) + Math.pow((p1[1] - p3[1]), 2);

        // p1和p4之间的距离的平方
        double p14 = Math.pow((p1[0] - p4[0]), 2) + Math.pow((p1[1] - p4[1]), 2);

        // p2和p3之间的距离的平方
        double p23 = Math.pow((p2[0] - p3[0]), 2) + Math.pow((p2[1] - p3[1]), 2);

        // p2和p4之间的距离的平方
        double p24 = Math.pow((p2[0] - p4[0]), 2) + Math.pow((p2[1] - p4[1]), 2);

        // p3和p4之间的距离的平方
        double p34 = Math.pow((p3[0] - p4[0]), 2) + Math.pow((p3[1] - p4[1]), 2);

        // 把6个距离的平方保存成数组
        double[] distances = {p12, p13, p14, p23, p24, p34};

        // 定义列表list，保存距离的平方
        List<Double> list = new ArrayList<>();

        // 遍历距离的平方数组
        for (double distance : distances) {
            if (distance == 0) {
                // 如果距离的平方有出现0的，那么这两个点重合，肯定不能构成正方形，返回false
                return false;
            }

            if (!list.contains(distance)) {
                // 如果列表list中没有包含此距离的平方，添加到列表list中
                list.add(distance);
            }
        }

        // 最后，如果列表list中的长度只有2，那么距离的平方只有两种，只有正方形才会出现距离的平方只有两种
        return list.size() == 2;
    }
}

提交代码后，提示运行正确。

运行结果

执行用时1ms，时间击败89.58%的用户，内存消耗36.1MB，空间击败74.52%的用户。

总结解题

第一，计算距离时不能直接套用计算距离的公式，直接比较两个点的坐标差的平方和即可，不要再进行开方，开方费时而且损失精度。

第二，判断三个点是否能构成三角形时，不能用另外一条对角线来代替判断。

第三，任意两个点不能重复，任意三个点不能在一条直线上。

第四，如果任意两个点的距离不出现0并且只有两种距离，那么就是正方形。

原文链接

原文链接：有效的正方形