乐趣区

关于后端:593-有效的正方形-简单几何运用题

题目形容

这是 LeetCode 上的 593. 无效的正方形 ,难度为 中等

Tag :「模仿」、「数学」、「计算几何」

给定 2D 空间中四个点的坐标 p1p2p3 和 p4,如果这四个点形成一个正方形,则返回 true

点的坐标 pi 示意为 $[x_i, y_i]$。输出 不是 按任何程序给出的。

一个 无效的正方形 有四条等边和四个等角 (90 度角)。

示例 1:

输出: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]

输入: True

示例 2:

输出:p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]

输入:false

示例 3:

输出:p1 = [1,0], p2 = [-1,0], p3 = [0,1], p4 = [0,-1]

输入:true

提醒:

  • $p1.length == p2.length == p3.length == p4.length == 2$
  • $-10^4 <= x_i, y_i <= 10^4$

计算几何

依据题意进行模仿即可。

从给定的 $4$ 个顶点当选 $3$ 个顶点,查看其是否造成「直角三角形」,同时保留下来首个直角三角形的直角边边长,供后续其余直角三角形进行比照(留神不能共点,即直角边长不能为 $0$)。

Java 代码:

class Solution {
    long len = -1;
    public boolean validSquare(int[] a, int[] b, int[] c, int[] d) {return calc(a, b, c) && calc(a, b, d) && calc(a, c, d) && calc(b, c, d);
    }
    boolean calc(int[] a, int[] b, int[] c) {long l1 = (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]);
        long l2 = (a[0] - c[0]) * (a[0] - c[0]) + (a[1] - c[1]) * (a[1] - c[1]);
        long l3 = (b[0] - c[0]) * (b[0] - c[0]) + (b[1] - c[1]) * (b[1] - c[1]);
        boolean ok = (l1 == l2 && l1 + l2 == l3) || (l1 == l3 && l1 + l3 == l2) || (l2 == l3 && l2 + l3 == l1);
        if (!ok) return false;
        if (len == -1) len = Math.min(l1, l2);
        else if (len == 0 || len != Math.min(l1, l2)) return false;
        return true;
    }
}

TypeScript 代码:

let len = -1
function validSquare(a: number[], b: number[], c: number[], d: number[]): boolean {
    len = -1
    return calc(a, b, c) && calc(a, b, d) && calc(a, c, d) && calc(b, c, d)
};
function calc(a: number[], b: number[], c: number[]): boolean {const l1 = (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1])
    const l2 = (a[0] - c[0]) * (a[0] - c[0]) + (a[1] - c[1]) * (a[1] - c[1])
    const l3 = (b[0] - c[0]) * (b[0] - c[0]) + (b[1] - c[1]) * (b[1] - c[1])
    const ok = (l1 == l2 && l1 + l2 == l3) || (l1 == l3 && l1 + l3 == l2) || (l2 == l3 && l2 + l3 == l1)
    if (!ok) return false
    if (len == -1) len = Math.min(l1, l2)
    else if (len == 0 || len != Math.min(l1, l2)) return false
    return true
}
  • 工夫复杂度:$O(1)$
  • 空间复杂度:$O(1)$

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.593 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,局部是有锁题,咱们将先把所有不带锁的题目刷完。

在这个系列文章外面,除了解说解题思路以外,还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:https://github.com/SharingSou…。

在仓库地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台公布

退出移动版