LeetCode - 593 有效的正方形

小咪咪 2023-09-24 13:08 126阅读 0赞

**目录**

题目来源

题目描述

示例

提示

题目解析

算法源码

数学公式求解

--------------------

### 题目来源 ###

[593. 有效的正方形 - 力扣（LeetCode）][593. _ - _LeetCode]

### 题目描述 ###

给定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
    }

![65b3c31314944ffa8fd60d5d45edd0a7.png][]

### 数学公式求解 ###

具体数学公式推导请看下面文章

[算法 - 正方形数量\_伏城之外的博客-CSDN博客][- _-CSDN]

/**
     * @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();
      }
    }

![a169e6ecd4984d3d94a1a0ef7b81b4ed.png][]

[593. _ - _LeetCode]: https://leetcode.cn/problems/valid-square/
[65b3c31314944ffa8fd60d5d45edd0a7.png]: https://img-blog.csdnimg.cn/65b3c31314944ffa8fd60d5d45edd0a7.png
[- _-CSDN]: https://blog.csdn.net/qfc_128220/article/details/127417851?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22127417851%22%2C%22source%22%3A%22qfc_128220%22%7D
[a169e6ecd4984d3d94a1a0ef7b81b4ed.png]: https://img-blog.csdnimg.cn/a169e6ecd4984d3d94a1a0ef7b81b4ed.png