Comment on page

593.Valid-Square

593. Valid Square

题目地址

题目描述

Given the coordinates of four points in 2D space, return whether the four points could construct a square.
​
The coordinate (x,y) of a point is represented by an integer array with two integers.
​
Example:
Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: True
​
Note:
All the input integers are in the range [-10000, 10000].
A valid square has four equal sides with positive length and four equal angles (90-degree angles).
Input points have no order.

代码

Approach #1 Brute Force

Time: O(1) && Space: O(1)
class Solution {
public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
int[][] p = {p1, p2, p3, p4};
return checkAllPermutations(p, 0);
}
​
boolean checkAllPermutations(int[][] p, int l) {
if (l == 4) {
return check(p[0], p[1], p[2], p[3]);
} else {
boolean res = false;
for (int i = l; i < 4; i++) {
swap(p, l, i);
res |= checkAllPermutations(p, l + 1);
swap(p, l, i);
}
return res;
}
}
​
private double dist(int[] p1, int[] p2) {
return (p2[1] - p1[1]) * (p2[1] - p1[1]) + (p2[0] - p1[0]) * (p2[0] - p1[0]);
}
​
private boolean check(int[] p1, int[] p2, int[] p3, int[] p4) {
return dist(p1, p2) > 0
&& dist(p1, p2) == dist(p2, p3)
&& dist(p2, p3) == dist(p3, p4)
&& dist(p3, p4) == dist(p4, p1)
&& dist(p1, p3) == dist(p2, p4);
}
​
private void swap(int[][] p, int x, int y) {
int[] temp = p[x];
p[x] = p[y];
p[y] = temp;
}
}

Approach #2 Using Sorting

public class Solution {
public double dist(int[] p1, int[] p2) {
return (p2[1] - p1[1]) * (p2[1] - p1[1]) + (p2[0] - p1[0]) * (p2[0] - p1[0]);
}
public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
int[][] p = {p1,p2,p3,p4};
Arrays.sort(p, (l1, l2) -> l1[0] == l2[0] ? l1[1] - l2[1] : l1[0] - l2[0]);
​
return dist(p[0], p[1]) != 0
&& dist(p[0], p[1]) == dist(p[1], p[3])
&& dist(p[1], p[3]) == dist(p[3], p[2])
&& dist(p[3], p[2]) == dist(p[2], p[0])
&& dist(p[0], p[3]) == dist(p[1],p[2]);
}
}