--
一个最简单的思路是从 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;
}
}
因为是 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;
}
}
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;
}
}
其实这题挺像 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 一下;
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;
}
}
挺高频的一道题，有点 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;
}
}
