LeetCode - 593 有效的正方形
LeetCode 有效 正方形
2023-09-14 09:04:04 时间
目录
题目来源
题目描述
给定2D空间中四个点的坐标 p1, p2, p3 和 p4,如果这四个点构成一个正方形,则返回 true 。
点的坐标 pi 表示为 [xi, yi] 。 输入没有任何顺序 。
一个 有效的正方形 有四条等边和四个等角(90度角)。
示例
输入: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
输出: True
输入:p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]
输出:false
输入: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
题目解析
假设输入的四点分别为A,B,C,D,我们可以固定A点,然后求
AB长度、AC长度、AD长度,如果四点可以组成正方形,则必然有两条边的长度相等,且另一条边的平方 = 相等的两条边的各自平方之和。
但是以上判断还不足以判定四点可以形成正方形,我们还需要保证正方形的对角线垂直,如果AB,AC相等的话,则AD就是对角线,BC也是对角线。
我们可以通过向量内积为0来判断两个向量是否垂直,因此我们可以计算
(A.x - D.x) * (B.x - C.x) + (A.y - D.y) * (B.y - C.y) === 0
来判断对角线是否垂直。
若以上条件都满足,则说明是四点可以组成正方形。
另外,我们需要处理特殊情况,比如四点中有两点或者更多的点相同,此时就无法形成四边形,更别说形成正方形了,因此我们需要排除掉这些特殊情况。
算法源码
/**
* @param {number[]} p1
* @param {number[]} p2
* @param {number[]} p3
* @param {number[]} p4
* @return {boolean}
*/
var validSquare = function(p1, p2, p3, p4) {
const set = new Set([p1,p2,p3,p4].map(p => p[0]+' '+p[1]))
if(set.size < 4) return false
let [x1, y1] = p1
let [x2, y2] = p2
let [x3, y3] = p3
let [x4, y4] = p4
let l12 = Math.pow(x2-x1, 2) + Math.pow(y2-y1,2)
let l13 = Math.pow(x3-x1, 2) + Math.pow(y3-y1,2)
let l14 = Math.pow(x4-x1, 2) + Math.pow(y4-y1,2)
let v12 = [x2-x1, y2-y1]
let v13 = [x3-x1, y3-y1]
let v14 = [x4-x1, y4-y1]
if(l12===l13 && l12 + l13===l14) {
let v23 = [x3-x2, y3-y2]
return isVertical(v14, v23)
}
else if(l12===l14 && l12 +l14===l13){
let v24 = [x4-x2, y4-y2]
return isVertical(v24, v13)
}
else if(l13===l14 && l13+l14===l12){
let v34 = [x4-x3, y4-y3]
return isVertical(v34, v12)
}
else {
return false
}
};
function isVertical(v1, v2) {
return v1[0]*v2[0] + v1[1]*v2[1] === 0
}
数学公式求解
具体数学公式推导请看下面文章
/**
* @param {number[]} p1
* @param {number[]} p2
* @param {number[]} p3
* @param {number[]} p4
* @return {boolean}
*/
var validSquare = function (p1, p2, p3, p4) {
let arr = [p1, p2, p3, p4];
const set = new Set(arr.map((p) => p[0] + " " + p[1]));
if (set.size < 4) return false;
let combination = [];
dfs(4, 2, 0, [], combination);
let flag = false;
for (let i = 0; i < combination.length; i++) {
let [x1, y1] = arr[combination[i][0]];
let [x2, y2] = arr[combination[i][1]];
let x3 = x1 - (y1 - y2);
let y3 = y1 + (x1 - x2);
let x4 = x2 - (y1 - y2);
let y4 = y2 + (x1 - x2);
if (set.has(x3 + " " + y3) && set.has(x4 + " " + y4)) {
flag = true;
break;
}
let x5 = x1 + (y1 - y2);
let y5 = y1 - (x1 - x2);
let x6 = x2 + (y1 - y2);
let y6 = y2 - (x1 - x2);
if (set.has(x5 + " " + y5) && set.has(x6 + " " + y6)) {
flag = true;
break;
}
}
return flag;
};
function dfs(n, k, index, path, result) {
if (path.length === k) {
return result.push([...path]);
}
for (let i = index; i < n; i++) {
path.push(i);
dfs(n, k, i + 1, path, result);
path.pop();
}
}
相关文章
- 有效的括号(leetcode 20)
- 拼写单词(leetcode 1160)
- LeetCode笔记:Weekly Contest 302
- LeetCode笔记:Weekly Contest 304
- LeetCode周赛302,这也太卷了,20分钟ak也只有300名……
- Leetcode 题目069-求平方根
- LeetCode 刷题笔记——day 8
- LeetCode 155. 最小栈
- Leetcode No.147 对链表进行插入排序
- JavaScript刷LeetCode模板技巧篇(二)
- 用Js怒刷LeetCode_2023-02-27
- Leetcode每日一题
- LeetCode | 有效的括号
- JavaScript刷LeetCode拿offer-js版字典
- JavaScript刷LeetCode心得
- Leetcode 560. 和为 K 的子数组
- LeetCode排列组合问题合集详解编程语言