Hash Table

Number of Boomerangs

for i - points.length，以每一个点为中心，cache住不同的distance和多少个点到一个中心点的距离一样。结果是count += value * (value - 1)，因为中心点已经确认了，左边的点有value个点能放，右边的点有(value - 1)个点能放。

public class Solution {
    public int numberOfBoomerangs(int[][] points) {
        if (points == null || points.length <= 2) {
            return 0;
        }

        Map<Long, Integer> map = new HashMap<Long, Integer>();
        int count = 0;

        for (int i = 0; i < points.length; i++) {
            map.clear();
            int x1 = points[i][0], y1 = points[i][1];
            for (int j = 0; j < points.length; j++) {
                if (i == j) {
                    continue;
                }
                int x2 = points[j][0], y2 =points[j][1];
                long distanceSqr = helper(x1, x2, y1, y2);
                if (!map.containsKey(distanceSqr)) {
                    map.put(distanceSqr, 1);
                } else {
                    map.put(distanceSqr, map.get(distanceSqr) + 1);
                }
            }
            for (int value: map.values()) {
                count += value * (value - 1);
            }
        }
        return count;
    }

    private long helper(int x1, int x2, int y1, int y2) {
        int dx = x1 - x2;
        int dy = y1 - y2;
        return dx * dx + dy * dy;
    }
}

Max Points on a Line

跟上一题一样，只不过这题是统计以每一个为中心点时的斜率。2个corner case，一个是出现same point，另一个是x1 == x2时的情况，因为计算斜率时分母不能为0。

另一点，java里的double类型，0除以正数是0.0，0除以负数是-0.0，这个case也要处理。

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) {
        if (points == null || points.length == 0) {
            return 0;
        }

        Map<Double, Integer> map = new HashMap<Double, Integer>();
        int max = 0;
        for (int i = 0; i < points.length; i++) {
            map.clear();
            int samePoint = 1;
            int x1 = points[i].x, y1 = points[i].y;
            for (int j = 0; j < points.length; j++) {
                if (i == j) {
                    continue;
                }
                int x2 = points[j].x, y2 = points[j].y;
                if (x1 == x2 && y1 == y2) {
                    samePoint++;
                    continue;
                } 

                double slope = x1 == x2 ? Long.MIN_VALUE : 0.0 + (double)(y1 - y2) / (x1 - x2);
                if (!map.containsKey(slope)) {
                    map.put(slope, 1);
                } else {
                    map.put(slope, map.get(slope) + 1);
                }
            }

            int temp = 0;
            for (int value: map.values()) {
                temp = Math.max(temp, value);
            }
            temp += samePoint;
            max = Math.max(max, temp);
        }
        return max;
    }
}

Line Reflection

First pass的时候，找到minX和maxX，并且用Hash Table保存下xin信息。通过minX和maxX的值，我们也就能得到如果存在一条中轴线，那这条中轴线所处的位置。在Second pass的时候，每遇到一个点，就通过Hash Table里保存下来的信息去check是否存在改点对应于中轴线另一边的那个点。

public class Solution {
    public boolean isReflected(int[][] points) {
        Set<String> set = new HashSet<String>();
        int minX = Integer.MAX_VALUE, maxX = Integer.MIN_VALUE;
        for (int[] p: points) {
            int x = p[0], y = p[1];
            minX = Math.min(minX, x);
            maxX = Math.max(maxX, x);
            String s = x + "a" + y;
            set.add(s);
        }

        long sum = minX + maxX;
        for (int[] p: points) {
            int x = p[0], y = p[1];
            long x2 = sum - x;
            String s = x2 + "a" + y;
            if (!set.contains(s)) {
                return false;
            }
        }
        return true;
    }
}