有效的正方形
难度:
标签:
题目描述
代码结果
运行时间: 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)
代码细节讲解
🦆
在检查任意两个点是否相同时,你是如何处理所有点对的检查?是逐一比较还是有其他高效的方法?
▷🦆
为什么在计算向量的点积时,结果为0就可以判断两个向量垂直?
▷🦆
函数`checkMidPoint`是如何确保两对对角线的中点相同有助于验证形状是正方形的?
▷🦆
题解中提到将四个点分成不同的两对,具体是如何选择这些点对的?有没有可能选择的点对方式会影响最终的结果?
▷