C#刷遍Leetcode面试题系列连载（5）：No.593 – 有效的正方形
- 2019 年 10 月 28 日
- 筆記
上一篇 LeetCode 面试题中，我们分析了一道难度为 Easy 的数学题 – 自除数，提供了两种方法。今天我们来分析一道难度为 Medium 的面试题。
系列教程索引
传送门：https://enjoy233.cnblogs.com/articles/leetcode_csharp_index.html
- C#刷遍Leetcode面试题系列连载（1） – 入门与工具简介
- C#刷遍Leetcode面试题系列连载（2）: No.38 – 报数
- C# 刷遍 Leetcode 面试题系列连载（3）: No.728 – 自除数
- C#刷遍Leetcode面试题系列连载（4）：No.633 – 平方数之和
- C#刷遍Leetcode面试题系列连载（5）：No.593 – 有效的正方形
今天要给大家分析的面试题是 LeetCode 上第 593 号问题，
LeetCode – 593. 有效的正方形
https://leetcode-cn.com/problems/valid-square
题目描述
给定二维空间中四点的坐标，返回四点是否可以构造一个正方形。
一个点的坐标（x，y）由一个有两个整数的整数数组表示。
示例:
输入: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1] 输出: True注意:
- 所有输入整数都在 [-10000，10000] 范围内。
- 一个有效的正方形有四个等长的正长和四个等角（90度角）。
- 输入点没有顺序。
-
题目难度：中等
-
通过次数：1.9K
-
提交次数：4.7K
-
贡献者：LeetCode
-
相关标签
解题思路:
可以基于正方形的特征来判断~
方法1: 由于点是以坐标形式给出的，于是可以围绕向量垂直以及对角线长度的平方为边长的 2 倍来做.
而向量垂直地判定依据是向量点乘的乘积为0)。
方法2: 判断4条边完全相等.
临界情况: 4个输入的点中有两个或多个相同，直接返回false。
方法1 已AC代码:
public class Solution { public bool ValidSquare(int[] p1, int[] p2, int[] p3, int[] p4) { int[] vect1 = { p2[0] - p1[0], p2[1] - p1[1] }; int[] vect2 = { p4[0] - p1[0], p4[1] - p1[1] }; int[] vect3 = { p3[0] - p1[0], p3[1] - p1[1] }; List<int[]> vects = new List<int[]> { vect1, vect2, vect3 }; if (vects.Any(x => x.SequenceEqual(new[]{0, 0}))) // 输入的点中存在相同的, 即有(0， 0)的向量 return false; List<int> lenSquaresFromP1 = new List<int> { GetLenSquare(p2, p1), GetLenSquare(p4, p1), GetLenSquare(p3, p1) }; List<int> extraLenSquares = new List<int> { GetLenSquare(p2, p3), GetLenSquare(p2, p4), GetLenSquare(p3, p4) }; if (lenSquaresFromP1.Max() != extraLenSquares.Max()) return false; // 当从p1出发的最长距离不为所有点两两之间距离的最大值时，只是菱形，不是正方形 var maxLenSquare = lenSquaresFromP1.Max(); // 后面要remove, 此处作备份 int maxPos = lenSquaresFromP1.IndexOf(maxLenSquare); lenSquaresFromP1.RemoveAt(maxPos); vects.RemoveAt(maxPos); if (lenSquaresFromP1[0] == lenSquaresFromP1[1] && lenSquaresFromP1[0] * 2 == maxLenSquare && VectorCross(vects[0], vects[1]) == 0) return true; return false; } private int VectorCross(int[] vect1, int[] vect2) => vect1[0] * vect2[0] + vect1[1] * vect2[1]; private int GetLenSquare(int[] point1, int[] point2) => (point2[0] - point1[0]) * (point2[0] - point1[0]) + (point2[1] - point1[1]) * (point2[1] - point1[1]); }执行用时: 104 ms, 在所有 csharp 提交中击败了80.00%的用户.
方法2 已AC代码:
public class Solution { public bool ValidSquare(int[] p1, int[] p2, int[] p3, int[] p4) { if (GetLenSquare(p1, p2) == 0 || GetLenSquare(p2, p3) == 0 || GetLenSquare(p3, p4) == 0 || GetLenSquare(p1, p4) == 0) return false; return GetLenSquare(p1, p2) == GetLenSquare(p3, p4) && GetLenSquare(p1, p3) == GetLenSquare(p2, p4) && GetLenSquare(p1, p4) == GetLenSquare(p2, p3) && (GetLenSquare(p1, p2) == GetLenSquare(p1, p3) || GetLenSquare(p1, p2) == GetLenSquare(p1, p4) || GetLenSquare(p1, p3) == GetLenSquare(p1, p4)); } private int GetLenSquare(int[] point1, int[] point2) => (point2[0] - point1[0]) * (point2[0] - point1[0]) + (point2[1] - point1[1]) * (point2[1] - point1[1]); }执行用时: 108 ms, 在所有 csharp 提交中击败了80.00%的用户.
欢迎提出更佳的解决思路~
作者简介：Bravo Yeung，计算机硕士，知乎干货答主(获81K 赞同, 38K 感谢, 235K 收藏)。曾在国内 Top3互联网视频直播公司工作过，后加入一家外企做软件开发至今。
如需转载，请加微信 iMath7 申请开白！
欢迎在留言区留下你的观点，一起讨论提高。如果今天的文章让你有新的启发，学习能力的提升上有新的认识，欢迎转发分享给更多人。
欢迎各位读者加入 .NET技术交流群，在公众号后台回复“加群”或者“学习”即可。
文末彩蛋
微信后台回复“asp”，给你：一份全网最强的ASP.NET学习路线图。
回复“cs”，给你：一整套 C# 和 WPF 学习资源！
回复“core”，给你：2019年dotConf大会上发布的.NET core 3.0学习视频！
