Max Points on a Line:
package my_java;
public class MaxNumPoint {
public int maxPoints(Point[] points) {
int maxnum = 0;
int n = points.length;
int n2 = n*(n-1)/2;
double[] theta = new double[n2];
double[] alpha = new double[n2];
int k = 0;
for (int i=0; i<n; i++) {
for(int j=i+1; j<n; j++) {
Point pt1 = points[i];
Point pt2 = points[j];
if (pt1.x != pt2.x) {
theta[k] = 1.0*(pt2.y - pt1.y)/(pt2.x - pt1.x);
alpha[k] = pt1.y - pt1.x*theta[k];
} else {
theta[k] = Double.MAX_VALUE;
alpha[k] = pt1.x;
}
k++;
}
}
for (int i = 0; i < n2; i++) {
k = 0;
if (theta[i] == Double.MAX_VALUE) {
for (int j = 0 ; j < n; j++) {
if (Math.abs(points[j].x - alpha[i]) < 0.01) {
k++;
if (k > maxnum) {
maxnum = k;
}
}
}
} else {
for (int j = 0 ; j < n; j++) {
double y = alpha[i] + theta[i]*points[j].x;
if (Math.abs(y - points[j].y) < 0.01) {
k++;
if (k > maxnum) {
maxnum = k;
}
}
}
} // end if
}
if (maxnum == 0 && points != null && points.length == 1) {
maxnum = 1;
}
return maxnum;
}
public static void main(String[] args) {
Point[] points = new Point[4];
points[0] = new Point(0, 2);
points[1] = new Point(0, 2);
points[2] = new Point(3, 10);
points[3] = new Point(3, 10);
int k = new MaxNumPoint().maxPoints(points);
System.out.println(k);
}
}
/**
Definition for a point.
*/
class Point {
int x;
int y;
Point() { x = 0; y = 0; }
Point(int a, int b) { x = a; y = b; }
}
The following is what I submitted for Single Number (This is my first submission @LeetCode. It had the highest AC rate, then I thought it's somewhat harder at least, but it's just opposite!
So I find a lowest AC rate, which is Max Points on a Line:).
public class Solution {
public int singleNumber(int[] A) {
int r = 0;
for (int i = 0; i < A.length; i++) {
r ^= A[i];
}
return r;
}
}
No comments:
Post a Comment