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:

  1. All the input integers are in the range [-10000, 10000].
  2. A valid square has four equal sides with positive length and four equal angles (90-degree angles).
  3. Input points have no order.

 

这道题给了我们四个点,让验证这四个点是否能组成一个正方形,刚开始博主考虑的方法是想判断四个角是否是直角,但即便四个角都是直角,也不能说明一定就是正方形,还有可能是矩形。还得判断各边是否相等。其实这里可以仅通过边的关系的来判断是否是正方形,根据初中几何的知识可以知道正方形的四条边相等,两条对角线相等,满足这两个条件的四边形一定是正方形。那么这样就好办了,只需要对四个点,两两之间算距离,如果计算出某两个点之间距离为0,说明两点重合了,直接返回 false,如果不为0,那么就建立距离和其出现次数之间的映射,最后如果我们只得到了两个不同的距离长度,那么就说明是正方形了,参见代码如下:

 

解法一:

class Solution {
public:
    bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
        unordered_map<int, int> m;
        vector<vector<int>> v{p1, p2, p3, p4};
        for (int i = 0; i < 4; ++i) {
            for (int j = i + 1; j < 4; ++j) {
                int x1 = v[i][0], y1 = v[i][1], x2 = v[j][0], y2 = v[j][1];
                int dist = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
                if (dist == 0) return false;
                ++m[dist];
            }
        }
        return m.size() == 2;
    }
};

 

我们其实不用建立映射,直接用个集合 HashSet 来放距离就行了,如果最后集合中不存在0,且里面只有两个数的时候,说明是正方形,参见代码如下:

 

解法二:

class Solution {
public:
    bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
        unordered_set<int> s{d(p1, p2), d(p1, p3), d(p1, p4), d(p2, p3), d(p2, p4), d(p3, p4)};
        return !s.count(0) && s.size() == 2;
    }
    int d(vector<int>& p1, vector<int>& p2) {
        return (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
    }
};

 

参考资料:

https://leetcode.com/problems/valid-square/

https://leetcode.com/problems/valid-square/discuss/103442/c-3-lines-unordered_set

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation