[LeetCode] 356. Line Reflection 直线对称
LeetCode line 对称 直线 reflection
2023-09-11 14:21:37 时间
Given n points on a 2D plane, find if there is such a line parallel to y-axis that reflect the given points.
Example 1:
Input: [[1,1],[-1,1]]
Output: true
Example 2:
Input: [[1,1],[-1,-1]]
Output: false
Follow up:
Could you do better than O(n2) ?
Hint:
- Find the smallest and largest x-value for all points.
- If there is a line then it should be at y = (minX + maxX) / 2.
- For each point, make sure that it has a reflected point in the opposite side.
Credits:
Special thanks to @memoryless for adding this problem and creating all test cases.
这道题给了我们一堆点,问我们存不存在一条平行于y轴的直线,使得所有的点关于该直线对称。题目中的提示给的相当充分,我们只要按照提示的步骤来做就可以解题了。首先我们找到所有点的横坐标的最大值和最小值,那么二者的平均值就是中间直线的横坐标,然后我们遍历每个点,如果都能找到直线对称的另一个点,则返回true,反之返回false,参见代码如下:
解法一:
class Solution { public: bool isReflected(vector<pair<int, int>>& points) { unordered_map<int, set<int>> m; int mx = INT_MIN, mn = INT_MAX; for (auto a : points) { mx = max(mx, a.first); mn = min(mn, a.first); m[a.first].insert(a.second); } double y = (double)(mx + mn) / 2; for (auto a : points) { int t = 2 * y - a.first; if (!m.count(t) || !m[t].count(a.second)) { return false; } } return true; } };
下面这种解法没有求最大值和最小值,而是把所有的横坐标累加起来,然后求平均数,基本思路都相同,参见代码如下:
解法二:
class Solution { public: bool isReflected(vector<pair<int, int>>& points) { if (points.empty()) return true; set<pair<int, int>> pts; double y = 0; for (auto a : points) { pts.insert(a); y += a.first; } y /= points.size(); for (auto a : pts) { if (!pts.count({y * 2 - a.first, a.second})) { return false; } } return true; } };
类似题目:
参考资料:
https://leetcode.com/problems/line-reflection/description/
https://leetcode.com/discuss/107661/48-ms-short-c-solution
https://leetcode.com/discuss/107761/group-by-y-then-sort-by-x-17ms
相关文章
- LeetCode 的回溯算法题目用这个模板解题,一网打尽,so easy!!!
- Leetcode: Count The Repetitions
- Leetcode: Valid Word Square
- Leetcode: Wildcard Matching
- JS Leetcode 690. 员工的重要性 题解分析
- JS Leetcode 264. 丑数 II 题解分析,当暴力无法暴力,让我们弃武从文了解三指针
- [LeetCode] Implement strStr()
- LeetCode动态规划基础题-总结(超级长文)
- 119、【回溯算法】leetcode ——131. 分割回文串:分割问题(C++版本)
- 【LeetCode】32. Longest Valid Parentheses (2 solutions)
- 【LeetCode】41. First Missing Positive (3 solutions)
- 【LeetCode】92. Reverse Linked List II
- [LeetCode] 772. Basic Calculator III 基本计算器之三
- [LeetCode] Valid Triangle Number 合法的三角形个数
- [LeetCode] Longest Line of Consecutive One in Matrix 矩阵中最长的连续1
- [LeetCode] 325. Maximum Size Subarray Sum Equals k 最大子数组之和为k
- [LeetCode] 241. Different Ways to Add Parentheses 添加括号的不同方式
- [LeetCode] 148. Sort List 链表排序
- leetcode 221. Maximal Square 最大正方形(中等)