本文主要是介绍Coursera普林斯顿算法课第三次作业，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Point: 重点是Comparable和Comparator接口的区别和实现。另外需要特别注意点的坐标是整数类型而斜率是浮点数，所以在计算斜率时可以乘以1.0。其次要注意Java中正负零不相等的问题，即0/5与0/(-5)不相同。
import java.util.Comparator;
import edu.princeton.cs.algs4.StdDraw;public class Point implements Comparable<Point>{private int x;private int y;public Point(int x, int y){this.x = x;this.y = y;}// x and y are between 0 and 32767public void draw(){StdDraw.point(x, y);}// StdDraw with input between 0 and 1public void drawTo(Point that){StdDraw.line(x, y, that.x, that.y);}public String toString() {return "Point [x=" + x + ", y=" + y + "]";}// implementation for Comparablepublic int compareTo(Point that) {if(y < that.y || (y == that.y && x < that.x)){return -1;}else if(y == that.y && x == that.x){return 0;}else{return 1;} }public double slopeTo(Point that){if(this.compareTo(that) == 0){return Double.NEGATIVE_INFINITY;}else if(this.x == that.x){return Double.POSITIVE_INFINITY;}else if(this.y == that.y){return +0; // negative zero != positive zero}else{return (that.y - y) * 1.0 /(that.x - x); // integer to double}}public Comparator<Point> slopeOrder(){return new BySlope();}// implementation for Comparatorprivate class BySlope implements Comparator<Point>{public int compare(Point o1, Point o2) {if(slopeTo(o1) < slopeTo(o2)) return -1;if(slopeTo(o1) > slopeTo(o2)) return 1;return 0;} }}LineSegment：不做要求，测试时会提供。注意StdDraw的使用。
import edu.princeton.cs.algs4.StdDraw;public class LineSegment {private Point p_top;private Point p_bot;public LineSegment(Point p, Point q){p_top = p;p_bot = q;}public void draw(){p_top.drawTo(p_bot);}public String toString() {return "LineSegment [p1=" + p_top + ", p2=" + p_bot + "]";}public static void main(String[] args){Point p1 = new Point(15000,18000);Point p2 = new Point(8000,22000);Point p3 = new Point(600,9000);Point p4 = new Point(9000,5000);Point p5 = new Point(12000,10000);StdDraw.enableDoubleBuffering();StdDraw.setXscale(0, 32768);StdDraw.setYscale(0, 32768);StdDraw.setPenRadius(0.01);StdDraw.setPenColor(StdDraw.BLUE);p1.draw();p2.draw();p3.draw();p4.draw();p5.draw();StdDraw.show();StdDraw.setPenColor(StdDraw.MAGENTA);p1.drawTo(p5);p2.drawTo(p4);StdDraw.setPenColor(StdDraw.RED);p3.drawTo(p2);StdDraw.show();}
}BruteCollinearPoints：使用了ArrayList及其自带的toArray方法。时间复杂度控制在N^4以内。注意不能直接对构造方法输入参数points进行排序，需要进行深度复制。
import java.util.ArrayList;
import edu.princeton.cs.algs4.Merge;public class BruteCollinearPoints {private Point[] pts;private ArrayList<LineSegment> lines;public BruteCollinearPoints(Point[] points){// deep copy to avoid mutating the constructor argumentcheckNullArgument(points);this.pts = new Point[points.length]; for(int k = 0; k < points.length; k++){pts[k] = points[k];}checkDuplicatedElement(pts); // mergesortlines = new ArrayList<LineSegment>(); // to avoid NullPointerExceptionfor(int k1 = 0; k1 < pts.length; k1++){for(int k2 = k1 + 1; k2 < pts.length; k2++){for(int k3 = k2 + 1; k3 < pts.length; k3++){if(pts[k1].slopeTo(pts[k2]) == pts[k1].slopeTo(pts[k3])){for(int k4 = k3 + 1; k4 < pts.length; k4++){if(pts[k1].slopeTo(pts[k2]) == pts[k1].slopeTo(pts[k4])){// k1, k2, k3, k4 are already sortedlines.add(new LineSegment(pts[k1], pts[k4]));}}}}}}}public int numberOfSegments(){return lines.size();}// line segment will contain at most 4 collinear pointspublic LineSegment[] segments(){return lines.toArray(new LineSegment[numberOfSegments()]);}private void checkDuplicatedElement(Point[] points){// sort input array by natural orderMerge.sort(points);// duplicated elementfor(int i=1; i<points.length; i++){if(points[i].slopeTo(points[i-1]) == Double.NEGATIVE_INFINITY){throw new IllegalArgumentException("Input contains repeated element!\n");}}}private void checkNullArgument(Point[] points){// null arrayif(points == null){throw new IllegalArgumentException("Input cannot be null!\n");}// null elementfor(int i = 0; i < points.length; i++){if(points[i] == null){throw new IllegalArgumentException("Input contains null element!\n");} }}}
FastCollinearPoints：难点在于如何确认找到的segment是不是之前找到过的线段的subsegment，同时要保证时间复杂度在N*N*lg(N)以内。以下代码通过使用复杂度为lg(N)的BinarySearch成功地完成了任务。
import java.util.ArrayList;
import java.util.Arrays;import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Merge;
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdOut;public class FastCollinearPoints {private Point[] pts;private ArrayList<LineSegment> lines;/*** constructor ~ n*nlg(n)* @param points*/public FastCollinearPoints(Point[] points){checkNullArgument(points);this.pts = new Point[points.length]; for(int k = 0; k < points.length; k++){pts[k] = points[k];}checkDuplicatedElement(pts); // mergesort ~ nlg(n)lines = new ArrayList<LineSegment>(); // to avoid NullPointerException// IndexOutOfBoundsException for i < pts.lengthfor(int i = 0; i < pts.length - 1; i++){Double[] slopesB4 = new Double[i]; // slopes with points upstreamPoint[] pointsAf = new Point[pts.length - i - 1]; // points downstreamfor(int k = 0; k < i; k++) {slopesB4[k] = pts[i].slopeTo(pts[k]);}for(int j = 0; j < pts.length - i - 1; j++) { pointsAf[j] = pts[j + i + 1]; }// sort upstream slopes by natural order ~ nlg(n)Merge.sort(slopesB4); // sort downstream points by slope order to pts[i] ~ nlg(n)Arrays.sort(pointsAf, pts[i].slopeOrder()); addSegment(slopesB4, pts[i], pointsAf); // ~ nlg(n)}}/*** add appropriate line segment ~ nlg(n)* @param slopesB4: slopes of upstream points to point p* @param p: the origin point* @param pointsAf: downstream points*/private void addSegment(Double[] slopesB4, Point p, Point[] pointsAf){int count = 1;double lastSlope = p.slopeTo(pointsAf[0]);for(int i = 1; i < pointsAf.length; i++){double slope = p.slopeTo(pointsAf[i]);if(slope != lastSlope){if(count >= 3 && !subSegment(lastSlope, slopesB4)){lines.add(new LineSegment(p, pointsAf[i - 1]));} count = 1;}else{count++; // the loop terminates with the last possible segment unchecked}lastSlope = slope;}// check the last pointif(count >= 3 && !subSegment(lastSlope, slopesB4)){lines.add(new LineSegment(p, pointsAf[pointsAf.length - 1]));}}/*** binary search the given slope in slopsB4 ~ lg(n)* @param s: the given slope* @param slopes: of upstream points to the origin point* @return */private boolean subSegment(double s, Double[] slopes){int lo = 0;int hi = slopes.length - 1;while(lo <= hi){int mid = lo + (hi - lo) / 2;if(s < slopes[mid]) hi = mid - 1;else if(s > slopes[mid]) lo = mid + 1; else return true;}return false;}public int numberOfSegments(){return lines.size();}public LineSegment[] segments(){return lines.toArray(new LineSegment[numberOfSegments()]);}private void checkDuplicatedElement(Point[] points){// sort input array by natural orderMerge.sort(points);// duplicated elementfor(int i=1; i<points.length; i++){if(points[i].slopeTo(points[i-1]) == Double.NEGATIVE_INFINITY){throw new IllegalArgumentException("Input contains repeated element!\n");}}}private void checkNullArgument(Point[] points){// null arrayif(points == null){throw new IllegalArgumentException("Input cannot be null!\n");}// null elementfor(int i = 0; i < points.length; i++){if(points[i] == null){throw new IllegalArgumentException("Input contains null element!\n");} }}public static void main(String[] args){// read n points from a fileIn in = new In(args[0]);int n = in.readInt();Point[] points = new Point[n];for(int i = 0; i < n; i++){int x = in.readInt();int y = in.readInt();points[i] = new Point(x, y);}// draw pointsStdDraw.enableDoubleBuffering();StdDraw.setXscale(0, 32768);StdDraw.setYscale(0, 32768);for(Point p : points){p.draw();}StdDraw.show();FastCollinearPoints collinear = new FastCollinearPoints(points);for(LineSegment sg : collinear.segments()){StdOut.println(sg);sg.draw();}StdDraw.show();}}
这篇关于Coursera普林斯顿算法课第三次作业的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
