Pages

Sunday, September 21, 2014

Fun with LeetCode?

I got the link to Leetcode from my colleagues this Thursday and planned to give it a try this weekend. The listed problems are pretty fun to solve. Here are two examples(with the highest AC rate and the lowest AC rate) I tried today.

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