普林斯顿大学算法Week3:CollinearPoints共线模式识别(99分)--总结及代码

总结

(代码有详细注释)

1. 本课讲了归并排序,作业应用是排序进行共线的模式识别,java1.8中的排序用的是tim排序,结合了归并排序与插入排序,属于稳定排序:排序之后相同元素的相对位置会不会改变
2. Point.java中有个非常重要的方法,compareTo(),它定义:纵坐标越小则点越小,如果纵坐标相同,那么横坐标越小则点越小.(如果作业中要求横坐标也是按顺序排列,那么排序后的点集映射到二维坐标系中是非递减的折线, 这样找共线只用一层循环即可,可惜作业没加上对x的限制)
3. 比较大小,一开始我用的是points[i-1] == point[i],尽管坐标相同但是points[i-1]不等于points[i]
   因为points[i-1]和points[i]表示引用,在堆中指向两个不同的地址,比较大小得用points[i-1].compareTo(points[i])
4. 在FastCollinearPoints.java中,一定要注意什么时候对共线点数变量count进行判断,有两种情况,一个是,相邻元素与参考点的斜率不同;另一个是循环到最后一个元素.这两种情况在代码注释中有解释
5. 唯一一处FAILED,扣了1分,没系统学过java,先跳过了

Test 7: check for dependence on either compareTo() or compare()returning { -1, +1, 0 } instead of { negative integer,positive integer, zero }* filename = equidistant.txt- number of entries in student   solution: 0- number of entries in reference solution: 4- 4 missing entries in student solution, including: '(30000, 0) -> (20000, 10000) -> (10000, 20000) -> (0, 30000)'
==> FAILED

1. week3课件中,递归调用的图示:
   这是包含两个递归调用的递归 (图示只画了一半)
   

代码

(如需提交,请删除中文注释)

一:Point.java

import java.util.Comparator;
import edu.princeton.cs.algs4.StdDraw;
public class Point implements Comparable<Point> {// x-coordinate of this pointprivate final int x;// y-coordinate of this pointprivate final int y;// constructs the point (x, y)public Point(int x, int y) {this.x = x;this.y = y;} // draws this pointpublic   void draw() {StdDraw.point(x,y);}// draws the line segment from this point to that pointpublic   void drawTo(Point that) {StdDraw.line(this.x, this.y, that.x, that.y);}// string representationpublic String toString() {return "(" + x + ", " + y + ")";}// compare two points by y-coordinates, breaking ties by x-coordinates  public  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;}   // the slope between this point and that pointpublic  double slopeTo(Point that) {if(x==that.x && y==that.y) return Double.NEGATIVE_INFINITY;if(x==that.x && y!=that.y) return Double.POSITIVE_INFINITY;     if(y==that.y) return +0.0;return (double)(y-that.y)/(x-that.x);}// compare two points by slopes they make with this pointpublic Comparator<Point> slopeOrder(){return new SlopeOrder();}//nested class//sort ruleprivate class SlopeOrder implements Comparator<Point>{public int compare(Point p,Point q) {//p点斜率大if(slopeTo(p)<slopeTo(q)) return -1;//p点斜率小else if(slopeTo(p)>slopeTo(q)) return 1;//p,q斜率相等else return 0;}}public static void main(String[] args) {Point p1 = new Point(0,0);Point p2 = new Point(1,1);Point p3 = new Point(2,2);Point p4 = new Point(2,1);Point p5 = new Point(4,1);System.out.println("p1.compareTo(p1) is "+p1.compareTo(p2));System.out.println("p2.compareTo(p1) is "+p2.compareTo(p1));System.out.println("p1.compareTo(p1) is "+p1.compareTo(p1)+"\n");System.out.println("p1.slopeTo(p2) is " +p1.slopeTo(p2));System.out.println("p1.slopeTo(p4) is "+p1.slopeTo(p4));System.out.println("p1.slopeTo(p1) is "+p1.slopeTo(p1));System.out.println("p3.slopeTo(p4) is "+p3.slopeTo(p4));System.out.println("p2.slopeTo(p5) is "+p2.slopeTo(p5));}
}

二:BruteCollinearPoints.java

import java.util.ArrayList;
import java.util.Arrays;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Insertion;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdDraw;public class BruteCollinearPoints {//to store line segmentsprivate ArrayList<LineSegment> LineSegmentList;//to store the given pointsprivate Point[] points;//在构造函数中找出由4点构成的线段(作业说了:没有5点及更多点共线的情况)// finds all line segments containing 4 pointpublic BruteCollinearPoints(Point[] pointsIn) { //三种异常//一:if the argument to the constructor is nullSystem.out.println(" a ");if(pointsIn == null) throw new IllegalArgumentException("there is no point");//二:if any point in the array is nullint N = pointsIn.length;for(int i=0;i<N;i++) if(pointsIn[i]==null) throw new IllegalArgumentException("exist null point");//三:if the argument to the constructor contains a repeated point//检查是否有重复的点,先排序,再查重会方便,作业允许这样: For example, you may use Arrays.sort()points = new Point[N];for(int i=0;i<N;i++) points[i] = pointsIn[i];Arrays.sort(points);for(int i=1;i<N;i++) if(points[i-1].compareTo(points[i])==0) throw new IllegalArgumentException("exist repeated point"); //to save every required line segmentLineSegmentList = new ArrayList<LineSegment>();//find line segmentfor(int dot1=0;dot1<=N-4;dot1++) {for(int dot2=dot1+1;dot2<=N-3;dot2++) {//k12:the slope between point[dot2] and point[dot1]double k12 = points[dot2].slopeTo(points[dot1]);for(int dot3=dot2+1;dot3<=N-2;dot3++) {//k13:the slope between point[dot3] and point[dot1]double k13 = points[dot3].slopeTo(points[dot1]);if(k13 != k12) continue;for(int dot4=dot3+1;dot4<=N-1;dot4++) {//k14:the slope between point[dot4] and point[dot1]double k14 = points[dot4].slopeTo(points[dot1]);if(k14 != k12) continue;//find a line segmentLineSegment linesegment = new LineSegment(points[dot1],points[dot4]);LineSegmentList.add(linesegment);}}}}}// the number of line segmentspublic int numberOfSegments() {return LineSegmentList.size();}// the line segmentspublic LineSegment[] segments() {LineSegment[] segments = new LineSegment[LineSegmentList.size()];int index=0;for(LineSegment Line : LineSegmentList) {segments[index++] = Line;}return segments;}    //mainpublic static void main(String[] args) {In in = new In("src/week3/input8.txt"); int n = in.readInt();StdOut.println("total "+n+" points");Point[] points = new Point[n];for (int i = 0; i < n; i++) {int x = in.readInt();int y = in.readInt();StdOut.println("("+x+","+y+")"); points[i] = new Point(x,y);}       //draw the pointsStdDraw.enableDoubleBuffering();StdDraw.setXscale(0, 32768);StdDraw.setYscale(0, 32768);StdDraw.setPenColor(StdDraw.RED);StdDraw.setPenRadius(0.01);for (Point p : points) {p.draw();}StdDraw.show();              // print and draw the line segmentsBruteCollinearPoints collinear = new BruteCollinearPoints(points);StdOut.println(collinear.numberOfSegments());for (LineSegment segment : collinear.segments()) {StdOut.println(segment);segment.draw();}StdDraw.show();          }
}

三:FastCollinearPoints.java

import java.util.ArrayList;
import java.util.Arrays;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdOut;//much faster than the brute-force solution
public class FastCollinearPoints {//to store line segmentsprivate ArrayList<LineSegment> LineSegmentList;//to store the given pointsprivate Point[] points;// finds all line segments containing 4 or more pointspublic FastCollinearPoints(Point[] pointsIn) {//三种异常//一:if the argument to the constructor is nullif(pointsIn == null) throw new IllegalArgumentException("there is no point");//number of pointsint N=pointsIn.length;//二:if any point in the array is nullfor(int i=0;i<N;i++) if(pointsIn[i]==null) throw new IllegalArgumentException("exist null point");//三:if the argument to the constructor contains a repeated point//检查是否有重复的点,先排序,再查重会方便,作业允许这样: For example, you may use        Arrays.sort()//同时有利于后面排除重复线段points = new Point[N];for(int i=0;i<N;i++) points[i] = pointsIn[i];//用的是结合了归并和插入的tim排序,稳定排序Arrays.sort(points);for(int i=1;i<N;i++) if(points[i-1].compareTo(points[i])==0) throw new IllegalArgumentException("exist repeated point");//to save every required line segmentLineSegmentList = new ArrayList<LineSegment>();//当前的参考点Point currentCheck;//对照点重新存储,不包括参考点,共N-1个Point[] otherPoints = new Point[N-1];//开始比较斜率,一个一个来for (int i=0;i<N;i++) {currentCheck = points[i];// copy points without Point currentCheck to otherPointsfor(int j=0;j<N;j++) {if(j<i) otherPoints[j] = points[j];if(j>i) otherPoints[j-1] = points[j];}//根据斜率对点排序//用的是结合了归并和插入的tim排序,稳定排序Arrays.sort(otherPoints,currentCheck.slopeOrder());//遍历已经排序的otherPoints找线段//注意,归并和插入排序都是稳定的,所以tim排序是稳定的,这非常重要//配合Point的compareTo方法,可以直接过滤掉重复线段//一开始没太注意compareTo方法,后来发现这个方法能固定住点之间的相对位置,所以可以过滤重复线段//两点共线int count=2;for(int k=1;k<N-1;k++) {double k1 = otherPoints[k-1].slopeTo(currentCheck);double k2 = otherPoints[k].slopeTo(currentCheck);if(k1==k2) {count++;//当循环到最后一个点,同时这个点和前面的点共线if(k==N-2) {//如果4点及以上共线,并且otherPoints中与参考点共线且排在最左边的点比参考点大的话,注意此处是遍历到头,所以索引是k-count+2if(count>=4 && currentCheck.compareTo(otherPoints[k-count+2])==-1) { //线段起点Point start = currentCheck;//线段终点Point end = otherPoints[k];LineSegment linesegment = new LineSegment(start,end);LineSegmentList.add(linesegment);}}}else{//如果4点及以上共线,并且otherPoints中与参考点共线且排在最左边的点比参考点大的话,索引是k-count+1if(count>=4 && currentCheck.compareTo(otherPoints[k-count+1])==-1) {Point start = currentCheck;Point end = otherPoints[k-1];LineSegment linesegment = new LineSegment(start,end);LineSegmentList.add(linesegment);}count=2;}}}}// the number of line segmentspublic  int numberOfSegments() {return LineSegmentList.size();}// the line segmentspublic LineSegment[] segments() {LineSegment[] segments = new LineSegment[LineSegmentList.size()];int index=0;for(LineSegment Line : LineSegmentList) {segments[index++] = Line;}return segments;}//mainpublic static void main(String[] args) {In in = new In("src/week3/input9.txt"); int n = in.readInt();StdOut.println("total "+n+" points");Point[] points = new Point[n];for (int i = 0; i < n; i++) {int x = in.readInt();int y = in.readInt();StdOut.println("("+x+","+y+")"); points[i] = new Point(x,y);}//draw the pointsStdDraw.enableDoubleBuffering();StdDraw.setXscale(0, 32768);StdDraw.setYscale(0, 32768);StdDraw.setPenColor(StdDraw.RED);StdDraw.setPenRadius(0.01);for (Point p : points) {p.draw();}StdDraw.show();//print and draw the line segmentsFastCollinearPoints collinear = new FastCollinearPoints(points);StdOut.println(collinear.numberOfSegments());for (LineSegment segment : collinear.segments()) {StdOut.println(segment);segment.draw();}StdDraw.show();          }
}

WelcomeToMyBlog