普林斯頓大學(xué)算法Week3:CollinearPoints共線模式識(shí)別(99分)--總結(jié)及代碼

Welcome To My Blog

總結(jié)

(代碼有詳細(xì)注釋)
  1. 本課講了歸并排序,作業(yè)應(yīng)用是排序進(jìn)行共線的模式識(shí)別,java1.8中的排序用的是tim排序,結(jié)合了歸并排序與插入排序,屬于穩(wěn)定排序:排序之后相同元素的相對(duì)位置會(huì)不會(huì)改變
  2. Point.java中有個(gè)非常重要的方法,compareTo(),它定義:縱坐標(biāo)越小則點(diǎn)越小,如果縱坐標(biāo)相同,那么橫坐標(biāo)越小則點(diǎn)越小.(如果作業(yè)中要求橫坐標(biāo)也是按順序排列,那么排序后的點(diǎn)集映射到二維坐標(biāo)系中是非遞減的折線, 這樣找共線只用一層循環(huán)即可,可惜作業(yè)沒加上對(duì)x的限制)
  3. 比較大小,一開始我用的是points[i-1] == point[i],盡管坐標(biāo)相同但是points[i-1]不等于points[i]
    因?yàn)閜oints[i-1]和points[i]表示引用,在堆中指向兩個(gè)不同的地址,比較大小得用points[i-1].compareTo(points[i])
  4. 在FastCollinearPoints.java中,一定要注意什么時(shí)候?qū)簿€點(diǎn)數(shù)變量count進(jìn)行判斷,有兩種情況,一個(gè)是,相鄰元素與參考點(diǎn)的斜率不同;另一個(gè)是循環(huán)到最后一個(gè)元素.這兩種情況在代碼注釋中有解釋
  5. 唯一一處FAILED,扣了1分,沒系統(tǒng)學(xué)過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課件中,遞歸調(diào)用的圖示:
    這是包含兩個(gè)遞歸調(diào)用的遞歸 (圖示只畫了一半)


    Merge.jpg

代碼

(如需提交,請(qǐng)刪除中文注釋)

一:Point.java

import java.util.Comparator;
import edu.princeton.cs.algs4.StdDraw;
public class Point implements Comparable<Point> {
    // x-coordinate of this point
    private final int x;
    // y-coordinate of this point
    private final int y;
    // constructs the point (x, y)
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    } 
    // draws this point
    public   void draw() {
        StdDraw.point(x,y);
    }
    // draws the line segment from this point to that point
    public   void drawTo(Point that) {
        StdDraw.line(this.x, this.y, that.x, that.y);
    }
    // string representation
    public 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 point
    public  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 point
    public Comparator<Point> slopeOrder(){
        return new SlopeOrder();
    }
    //nested class
    //sort rule
    private class SlopeOrder implements Comparator<Point>{
        public int compare(Point p,Point q) {
            //p點(diǎn)斜率大
            if(slopeTo(p)<slopeTo(q)) return -1;
            //p點(diǎn)斜率小
            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 segments
     private ArrayList<LineSegment> LineSegmentList;
     //to store the given points
     private Point[] points;
    
     //在構(gòu)造函數(shù)中找出由4點(diǎn)構(gòu)成的線段(作業(yè)說了:沒有5點(diǎn)及更多點(diǎn)共線的情況)
     // finds all line segments containing 4 point
     public BruteCollinearPoints(Point[] pointsIn) { 
         //三種異常
         //一:if the argument to the constructor is null
         System.out.println(" a ");
         if(pointsIn == null) throw new IllegalArgumentException("there is no point");
         //二:if any point in the array is null
         int 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
         //檢查是否有重復(fù)的點(diǎn),先排序,再查重會(huì)方便,作業(yè)允許這樣: 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 segment
         LineSegmentList = new ArrayList<LineSegment>();
             
         //find line segment
         for(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 segment
                         LineSegment linesegment = new LineSegment(points[dot1],points[dot4]);
                         LineSegmentList.add(linesegment);
                     }
                 }
             }
         }
     }
     // the number of line segments
     public int numberOfSegments() {
         return LineSegmentList.size();
     }
     // the line segments
     public LineSegment[] segments() {
         LineSegment[] segments = new LineSegment[LineSegmentList.size()];
         int index=0;
         for(LineSegment Line : LineSegmentList) {
             segments[index++] = Line;
         }
         return segments;
     }    
     //main
     public 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 points
            StdDraw.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 segments
            BruteCollinearPoints 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 segments
    private ArrayList<LineSegment> LineSegmentList;
    //to store the given points
    private Point[] points;
    
    // finds all line segments containing 4 or more points
    public FastCollinearPoints(Point[] pointsIn) {
         //三種異常
         //一:if the argument to the constructor is null
         if(pointsIn == null) throw new IllegalArgumentException("there is no point");
        //number of points
         int N=pointsIn.length;
         //二:if any point in the array is null
         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
         //檢查是否有重復(fù)的點(diǎn),先排序,再查重會(huì)方便,作業(yè)允許這樣: For example, you may use        Arrays.sort()
         //同時(shí)有利于后面排除重復(fù)線段
         points = new Point[N];
         for(int i=0;i<N;i++) points[i] = pointsIn[i];
         //用的是結(jié)合了歸并和插入的tim排序,穩(wěn)定排序
         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 segment
         LineSegmentList = new ArrayList<LineSegment>();
             
         
         //當(dāng)前的參考點(diǎn)
         Point currentCheck;
         //對(duì)照點(diǎn)重新存儲(chǔ),不包括參考點(diǎn),共N-1個(gè)
         Point[] otherPoints = new Point[N-1];
         //開始比較斜率,一個(gè)一個(gè)來
         for (int i=0;i<N;i++) {
             currentCheck = points[i];
             // copy points without Point currentCheck to otherPoints
             for(int j=0;j<N;j++) {
                 if(j<i) otherPoints[j] = points[j];
                 if(j>i) otherPoints[j-1] = points[j];
             }
             
             //根據(jù)斜率對(duì)點(diǎn)排序
             //用的是結(jié)合了歸并和插入的tim排序,穩(wěn)定排序
             Arrays.sort(otherPoints,currentCheck.slopeOrder());
             //遍歷已經(jīng)排序的otherPoints找線段
             //注意,歸并和插入排序都是穩(wěn)定的,所以tim排序是穩(wěn)定的,這非常重要
             //配合Point的compareTo方法,可以直接過濾掉重復(fù)線段
             //一開始沒太注意compareTo方法,后來發(fā)現(xiàn)這個(gè)方法能固定住點(diǎn)之間的相對(duì)位置,所以可以過濾重復(fù)線段
             //兩點(diǎn)共線
             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++;
                     //當(dāng)循環(huán)到最后一個(gè)點(diǎn),同時(shí)這個(gè)點(diǎn)和前面的點(diǎn)共線
                     if(k==N-2) {
                         //如果4點(diǎn)及以上共線,并且otherPoints中與參考點(diǎn)共線且排在最左邊的點(diǎn)比參考點(diǎn)大的話,注意此處是遍歷到頭,所以索引是k-count+2
                         if(count>=4 && currentCheck.compareTo(otherPoints[k-count+2])==-1) { 
                             //線段起點(diǎn)
                             Point start = currentCheck;
                             //線段終點(diǎn)
                             Point end = otherPoints[k];
                             LineSegment linesegment = new LineSegment(start,end);
                             LineSegmentList.add(linesegment);
                         }
                     }
                 }
                 else{
                    //如果4點(diǎn)及以上共線,并且otherPoints中與參考點(diǎn)共線且排在最左邊的點(diǎn)比參考點(diǎn)大的話,索引是k-count+1
                     if(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 segments
    public  int numberOfSegments() {
        return LineSegmentList.size();
    }
    // the line segments
    public LineSegment[] segments() {
        LineSegment[] segments = new LineSegment[LineSegmentList.size()];
         int index=0;
         for(LineSegment Line : LineSegmentList) {
             segments[index++] = Line;
         }
         return segments;
    }
    
         //main
         public 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 points
                StdDraw.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 segments
                FastCollinearPoints collinear = new FastCollinearPoints(points);
                StdOut.println(collinear.numberOfSegments());
                for (LineSegment segment : collinear.segments()) {
                    StdOut.println(segment);
                    segment.draw();
                }
                StdDraw.show();          
         }
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 貪心算法 貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上...
    fredal閱讀 9,422評(píng)論 3贊 52
  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問題, 分享了一些自己做題目的經(jīng)驗(yàn)。 張土汪：刷leetcod...
    土汪閱讀 12,921評(píng)論 0贊 33
  • 一. 寫在前面 要學(xué)習(xí)算法，“排序”是一個(gè)回避不了的重要話題，在分析完并查集算法和常用數(shù)據(jù)結(jié)構(gòu)之后，今天我們終于可...
    Leesper閱讀 2,640評(píng)論 0贊 40
  • 我為痛苦生活開出的第二味藥是，盡可能從你們自身的經(jīng)驗(yàn)獲得知識(shí)，盡量別從其他人成功或失敗的經(jīng)驗(yàn)中廣泛吸取教訓(xùn)，不管他...
    給小老板讀商業(yè)書閱讀 361評(píng)論 0贊 0
  • 劉老師，本周末由于我沒有趕去休寧，但有通過微信了解到他的學(xué)習(xí)和作業(yè)，以下是我對(duì)他本周作業(yè)的評(píng)價(jià)，由于我媽媽可能寫字...
    劉麗賞閱讀 755評(píng)論 0贊 1

友情鏈接更多精彩內(nèi)容