leetcode
leetcode 501 ~ 550
有效的正方形

有效的正方形

难度:

标签:

题目描述

代码结果

运行时间: 25 ms, 内存: 16.0 MB


// 思路: 与Java普通解法相同,但使用Stream和lambda表达式简化代码。
 
import java.util.Arrays;
import java.util.stream.IntStream;
 
public class ValidSquare {
    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        int[] points = new int[][]{p1, p2, p3, p4};
        int[] d = IntStream.range(0, 3)
            .flatMap(i -> IntStream.range(i + 1, 4)
            .map(j -> dist(points[i], points[j])))
            .sorted()
            .toArray();
        return d[0] > 0 && d[0] == d[1] && d[1] == d[2] && d[2] == d[3] && d[4] == d[5];
    }
 
    private int dist(int[] p1, int[] p2) {
        return (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
    }
}
 

解释

方法:

这个题解的思路是通过检查两对对角线是否等长且垂直来判断四个点是否能构成一个正方形。首先定义了一些辅助函数:checkLength用于检查两个向量的长度是否相等,checkMidPoint用于检查两对点的中点是否相同,calCos用于计算两个向量的点积。然后定义了一个主要的辅助函数help,它接受四个点作为参数,计算两对对角线的向量,然后使用前面定义的辅助函数检查这两对对角线是否满足正方形的条件(等长且垂直)。最后,在Solution类中的validSquare方法中,首先检查任意两个点是否相同(如果相同,则它们不能构成正方形)。然后,它尝试将四个点分成不同的两对,使用help函数检查它们是否能构成正方形。如果其中任何一对满足条件,就返回True,否则返回False。

时间复杂度:

O(1)

空间复杂度:

O(1)

代码细节讲解

🦆
在检查任意两个点是否相同时,你是如何处理所有点对的检查?是逐一比较还是有其他高效的方法?
题解中采用的是逐一比较的方法。具体地,它在调用`help`函数之前,会先检查`p1`是否与`p2`、`p3`或`p4`相同,以此类推。这种方法虽然直接,但在效率上并不是最优的。一个更高效的方法可能是使用哈希集合来存储所有点,然后检查集合的大小是否等于4(即没有重复的点),这样可以在常数时间内完成所有点对的比较。
🦆
为什么在计算向量的点积时,结果为0就可以判断两个向量垂直?
向量的点积(或称为内积)定义为两个向量的对应坐标相乘后的总和。数学上,两个向量的点积等于它们的模长乘积与它们夹角的余弦值的乘积。当两个向量垂直时,它们之间的夹角为90度,余弦90度的值为0。因此,如果两个向量的点积为0,这意味着它们之间的夹角是90度,从而可以确认这两个向量是垂直的。
🦆
函数`checkMidPoint`是如何确保两对对角线的中点相同有助于验证形状是正方形的?
在平面几何中,正方形的两条对角线不仅等长且相互垂直,而且它们会在正方形的中心相交。这意味着两条对角线的中点必须相同,即是正方形的中心。因此,通过验证两对对角线的中点是否相同,可以帮助确认这四个点构成的四边形是否具有正方形的这一重要属性。
🦆
题解中提到将四个点分成不同的两对,具体是如何选择这些点对的?有没有可能选择的点对方式会影响最终的结果?
题解中尝试了三种不同的点对组合来形成两对对角线,分别是:(p1, p2)与(p3, p4),(p1, p3)与(p2, p4),(p1, p4)与(p2, p3)。这种方式是基于将四个点进行全排列后,选择可能的对角线组合。由于是要检查所有可能形成的对角线组合,因此选择的点对方式并不会影响最终结果。只要有任何一种组合满足正方形的条件,函数就会返回`True`。

相关问题