坐标系 & 数值计算类

--

Valid Perfect Square

一个最简单的思路是从 left = 1, right = num / 2 开始做 binary search，可以在 log(n) 时间内解决，然而在 num = Integer.MAX_VALUE 的情况下， OJ 觉得速度还是太慢了。

在 numerical analysis 里的多项式求近似值，binary search 又称 bisection method，收敛速度为 liner convergence; 而 newton's method 是 quadratic convergence，收敛速度要快很多。

用 newton's method 起始 x_n 值取的好可以收敛的快一点，不过也要注意 corner case，比如 num = 0, 1 ..

public class Solution {
    public boolean isPerfectSquare(int num) {
        if(num==1 || num==0) return true;
        double ebs = 0.1;
        double xn = num/2;
        double xprev = 0;
        while(Math.abs(xn-xprev)>ebs){
            xprev = xn;
            xn = (xn+num/xn)/2; 
        }
        return (int)xn*(int)xn==num;
    }
}

Sqrt(x)

因为是 double ，epsilon 的精度要高一些。

public class Solution {
    public int mySqrt(int x) {
        final double eps = 0.000001;
        double x_n = x;
        double x_prev = 0;
        while(Math.abs(x_n - x_prev) > eps){
            x_prev = x_n;
            x_n = (x_n + x / x_n) / 2;
        }
        return (int) x_n;
    }
}

Pow(x, n)

log(N) 的解法就是简单的 divide & conquer.

public class Solution {
    public double myPow(double x, int n) {
        if(n==0)
            return 1;
        if(n<0)
            return 1.0/power(x,-n);
        else
            return power(x,n);
    }
    HashMap<Integer, Double> map = new HashMap<Integer, Double>();
    public double power(double x, int n){
        if(map.containsKey(n)) return map.get(n);
        if(n==0)
            return 1;
        double v = power(x,n/2);
        map.put(n/2, v);
        if(n%2==0){
            return v*v;
        }
        else
            return x*v*v;
    }
}

Line Reflection

其实这题挺像 Two Sum.

另一种靠 HashSet 的写法就简洁有效多了，扫描左右，记录中点再做检测就是。

记录中点时候最好先推算一下，尽量不要存一个 /2 之后的 double 类，而可以经过计算保证所有的变量都是 int 类。

用 Set 很好的处理了“多个点视为同一个点”的问题，唯一的问题是，我知道另外一个点的坐标是什么，但是 hashset 不能直接搜 new int[]{newX, newY}，得靠 hashcode.

最简单的做法就是，自己定义 String 做 hashcode. "x | y" 代表 point(x, y) 就可以了。这种做法值得学习一个~

public class Solution {
    public boolean isReflected(int[][] points) {
        HashSet<String> set = new HashSet<String>();
        int minX = Integer.MAX_VALUE;
        int maxX = Integer.MIN_VALUE;

        for(int[] point : points){
            minX = Math.min(minX, point[0]);
            maxX = Math.max(maxX, point[0]);
            set.add(point[0] + "|" + point[1]);
        }

        int targetMid = minX + maxX;

        for(int[] point : points){
            int reflectedX = targetMid - point[0];
            int reflectedY = point[1];
            if(!set.contains(reflectedX + "|" + reflectedY)) return false;
        }

        return true;
    }
}

挺高频的一道题，有点 tricky，我自己写的时候改了好多次都没能处理好多个重复点的情况。。因为和上一题不一样，这题多个点要单独算了。好消息是，这类 Math 题见过了就是见过了，也不用太纠结因为参考了别人解法没掌握题型知识的问题。

注意要点和流程：

• 对于每一个新的点，要单独建 HashMap 用于检查斜率。对于每一个点都要新建，是因为检查多点共线要以每个点自己为准，之前点的 HashMap 对新的点没有什么卵用。

• 以 point[i] 为外循环，内循环里有可能会出现 point[j] 与 point[i] 一模一样的问题。要存一个变量记录下到底有多少个和 point[i] 一样的点，默认为 1， 清算完毕后加上去。

• 如果两个点 x 值相等，定义斜率为 Double.MAX_VALUE;

• 对于 point[i] 清算完毕后，要把最大的 localMax (和 i 同一直线的点 maxCount) 加上与 point[i] 重复的点的个数，因为这里面每一个点都和 localMax 中的点共线。

O(n^2)，速度还不错

public class Solution {
    public int maxPoints(Point[] points) {
        if(points == null) return 0;
        if(points.length<=2) return points.length;
        int maxNum = 0; 
        for(int i=0;i<points.length;i++){
            int samePoint = 1; int localMax = 0;
            HashMap<Double, Integer> map = new HashMap<Double, Integer>();
            for(int j=i-1;j>=0;j--){
                double slope=0.0;
                if(points[i].x==points[j].x && points[i].y==points[j].y) {samePoint++;continue;}
                else if(points[i].x==points[j].x) slope = Double.MAX_VALUE;
                else{
                    slope = (double)(points[i].y-points[j].y)/(points[i].x-points[j].x);
                }
                map.put(slope, map.getOrDefault(slope, 0)+1);
                localMax = Math.max(localMax, map.get(slope));
            }
            maxNum = Math.max(maxNum, localMax+samePoint);
        }
        return maxNum;
    }
}