Leetcode 356. Line Reflection

ivyzhang 发布于2019-08-14 16:59 / 2370人阅读

摘要：题目解法这道题主要是判断个点是否沿某条线对称，可以从提示看出来所有的点应该要满足所以先把所有的点扫一遍存下来，找到和然后再扫一遍，判定是否点都是延直线对称的。时间复杂度空间复杂度代码

题目：
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:
Given points = [[1,1],[-1,1]], return true.

Example 2:
Given points = [[1,1],[-1,-1]], return 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.

解法：

这道题主要是判断N个点是否沿某条线对称，可以从提示看出来所有的点应该要满足 2Y = minX + maxX;所以先把所有的点扫一遍存下来，找到minX和minX. 然后再扫一遍，判定是否点都是延直线对称的。时间复杂度O(n),空间复杂度O(n).

代码：

public class Solution {
    public boolean isReflected(int[][] points) {
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        Set set = new HashSet();
        for (int[] p : points) {
            set.add(p[0] + "," + p[1]);
            min = Math.min(min, p[0]);
            max = Math.max(max, p[0]);
        }
        
        int sum = min + max;
        for (int[] p : points) {
            if (!set.contains((sum - p[0]) + "," + p[1])) {
                return false;
            }
        }
        return true;
    }
}

GPU云服务器云服务器 java报错356 Reflection 映射Reflection LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66358.html

356. Line Reflection

摘要：实际上这题的要求是所有点的关于一个轴对称，坐标左右全部对称，就是说就是对的，但是就不对，因为没有和它对称的点。也是对的，都是关于这个轴对称。看了里面直接用加上分隔符来表示点，这样不用自己定义简单点。 356. Line Reflection 题目链接：https://leetcode.com/problems... 这题给的例子太神了根本看不懂。实际上这题的要求是所有点的关于一个y轴对...

fireflow 2019-08-14 17:28 评论0 收藏0
356. Line Reflection

摘要：问题解答这个解法是看的里的，看着简单，但想到很难。我们要求是不是对称，就是要求每一个点是不是有个点跟它对应。因为可以一个点重复出现，决定我们用来做。记录每一个出现的点，然后再用来找其对应的点。问题：Given n points on a 2D plane, find if there is such a line parallel to y-axis that reflect the...

ranwu 2019-08-14 14:12 评论0 收藏0
Laravel学习笔记之PHP反射(Reflection) (上)

摘要：说明中经常使用的反射特性来设计代码，本文主要学习的反射特性，来提高写代码时的设计质量。提供一套检测的两个工具包和，类似于探针一样的东西来探测这些一等公民。限于篇幅，下篇再聊下反射。说明：Laravel中经常使用PHP的反射特性来设计代码，本文主要学习PHP的反射特性，来提高写代码时的设计质量。PHP提供一套检测class, interface, trait, property, me...

JessYanCoding 2019-07-01 12:19 评论0 收藏0
[LeetCode] 694. Number of Distinct Islands

Problem Given a non-empty 2D array grid of 0s and 1s, an island is a group of 1s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are s...

SunZhaopeng 2019-08-16 13:50 评论0 收藏0