坐标系 & 数值计算类

--

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;
        final double eps = 0.1;
        double x_n = num / 2;
        double x_prev = 0;
        while(Math.abs(x_n - x_prev) > eps){
            x_prev = x_n;
            x_n = (x_n + num / x_n) / 2;
        }

        return (int)x_n * (int)x_n == 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. 有一个特别奇葩的 case，N = Integer.MIN_VALUE... 手动设置一下好了。

public class Solution {
    public double myPow(double x, int n) {
        if(n == -1) return 1/x;
        if(n == 0) return 1;
        if(n == 1) return x;
        if(n == -2147483648) return (double) 1 / (x * myPow(x, 2147483647));

        boolean isNeg = false;
        if(n < 0){
            isNeg = true;
            n = -n;
        }

        double rst;
        if(n % 2 == 0){
            double half = myPow(x, n / 2);
            rst = half * half;
        } else {
            double half = myPow(x, n / 2);
            rst = half * half * x;
        }
        return (isNeg) ? 1/rst: rst;
    }
}

Line Reflection

其实这题挺像 Two Sum.

自己写的第一版，追着 bug 改了好多次。。一定有更好的写法。。 但是这种写法速度很快，也不是全无可取之处。 7ms(这种) vs 22ms(HashSet)

不建议真这么写，提一下就行了。

（排序麻烦版）基本步骤：

• 把所有点按照 x 坐标升序排序，x 相同按 y 值升序排序

• 从后面到中点，把 x 值相同 y 值不同的序列翻转，保证对称

• 初始化中点；

• Two pointer 开扫：

  • 如果 P[left] 和 P[right] 的中点不对，false;

  • 如果 P[left] 和 P[right] 的 X 值不一致，但是 Y 不同，false;

  • left / right 向里移动，但是跳过完全一样的点；

  • 左右重合于最后一个元素时，再和 mid check 一下;

• 若以上条件都满足，返回 true;

public class Solution {
    private class PointComparator implements Comparator<int[]>{
        public int compare(int[] a, int[] b){
            if(a[0] != b[0]) return a[0] - b[0];
            else return a[1] - b[1];
        }
    }
    public boolean isReflected(int[][] points) {
        if(points == null || points.length <= 1) return true;

        Arrays.sort(points, new PointComparator());
        int N = points.length;

        for(int i = N - 1; i >= N / 2; i--){
            int end = i;
            int start = i;
            while(i >= N / 2 && points[i][0] == points[i - 1][0]){
                i --;
                start --;
            }
            reverse(points, start, end);
        }


        int left = 0;
        int right = points.length - 1;
        double mid = (double)(points[left][0] + points[right][0]) / 2;
        while(left < right){
            double curMid = (double)(points[left][0] + points[right][0]) / 2;
            if(curMid != mid) return false;

            if(points[left][0] != points[right][0] && points[left][1] != points[right][1]) return false;

            while(left < right && points[left][0] == points[left + 1][0] && points[left][1] == points[left + 1][1]) left ++;
            while(left < right && points[right][0] == points[right - 1][0] && points[right][1] == points[right - 1][1]) right --;

            left ++;
            right --;
        }

        if(left == right && points[left][0] != mid) return false;

        return true;
    }

    private void reverse(int[][] points, int start, int end){
        while(start < end){
            int[] temp = points[start];
            points[start] = points[end];
            points[end] = temp;
            start ++;
            end --;
        }
    }
}

另一种靠 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;
    }
}

Max Points on a Line

挺高频的一道题，有点 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 max = 0;
        for(int i = 0; i < points.length; i++){
            Point p1 = points[i];
            int samePoint = 1;
            int localMax = 0;
            HashMap<Double, Integer> map = new HashMap<Double, Integer>();

            for(int j = i - 1; j >= 0; j--){
                Point p2 = points[j];
                double slope = 0.0;

                if(p1.y == p2.y && p1.x == p2.x) {
                    samePoint++;
                    continue;
                } else if(p1.x == p2.x) {
                    slope = Double.MAX_VALUE;
                } else {
                    slope = (double)(p1.y - p2.y) / (p1.x - p2.x);
                }

                if(map.containsKey(slope)){
                    int count = map.get(slope);
                    map.put(slope, count + 1);
                    localMax = Math.max(localMax, count + 1);
                } else {
                    map.put(slope, 1);
                    localMax = Math.max(localMax, 1);
                }
            }

            max = Math.max(max, localMax + samePoint);
        }

        return max;
    }
}