這本來應(yīng)該是第三周的作業(yè)，但是由于其他作業(yè)逼近deadline，暫時(shí)推后了一周完成。

這周的assignment大大提高了我對(duì)這門課的看法，不得不說，Algorithms這門課的assignment部分設(shè)計(jì)得很好。為什么好？個(gè)人認(rèn)為有以下幾點(diǎn)：

程序要求解耦

循序漸進(jìn)，這周的作業(yè)不允許使用hashcode()

輸入變量不允許被程序改變

能做到1、3兩點(diǎn)，在工程中也是高質(zhì)量代碼的體現(xiàn)

---

?

題目很簡(jiǎn)單，即給出一個(gè)點(diǎn)集，找所有出任意四點(diǎn)或以上共線的線段，將該線段的端點(diǎn)new 一個(gè)segment()對(duì)象存起來。看起來很簡(jiǎn)單，實(shí)際上到處都是坑TAT

第一部分是用brute force的方法做，由于4個(gè)及以上的點(diǎn)才是共線，這里要求中提出為了簡(jiǎn)化，brute方法不考慮5個(gè)及以上的點(diǎn)。所以既是對(duì)點(diǎn)集進(jìn)行4層循環(huán)即可，時(shí)間復(fù)雜度是O(n4)。

但是這里需要注意的是，輸入的點(diǎn)集，不能被直接操作，必須被賦值為拷貝才行，否則，外界如果更改了點(diǎn)集中的點(diǎn)，則會(huì)影響結(jié)果。這一點(diǎn)還說明了，java都是值傳遞，傳進(jìn)來的是一個(gè)數(shù)組引用的copy。

另外辯解條件必須要注意，其實(shí)挺容易出錯(cuò)的。

1 public class BruteCollinearPoints { 2 // finds all line segments containing 4 points 3 private int N; 4 private ArrayList<LineSegment> segment = new ArrayList<LineSegment>(); 5 6 public BruteCollinearPoints(Point[] points) { 7 if (points == null) 8 throw new java.lang.NullPointerException(); 9 N = 0; 10 Point[] copy = new Point[points.length]; 11 for (int i = 0; i < points.length; i++) { 12 copy[i] = points[i]; 13 } 14 Arrays.sort(copy); 15 for (int i = 0; i < copy.length - 1; i++) { 16 if (copy[i].compareTo(copy[i + 1]) == 0) { 17 throw new java.lang.IllegalArgumentException(); 18 } 19 } 20 for (int i = 0; i < copy.length - 3; i++) { 21 for (int j = i + 1; j < copy.length - 2; j++) { 22 double slope1 = copy[i].slopeTo(copy[j]); 23 for (int k = j + 1; k < copy.length - 1; k++) { 24 double slope2 = copy[i].slopeTo(copy[k]); 25 if (slope1 != slope2) 26 continue; 27 int temp = 0; 28 for (int l = k + 1; l < copy.length; l++) { 29 double slope3 = copy[i].slopeTo(copy[l]); 30 if (slope1 == slope3) 31 temp = l; 32 if ((l == copy.length - 1) && (temp != 0)) { 33 N++; 34 segment.add(new LineSegment(copy[i], copy[temp])); 35 } 36 } 37 } 38 } 39 } 40 } 41 42 // the number of line segments 43 public int numberOfSegments() { 44 return N; 45 } 46 47 // the line segments 48 public LineSegment[] segments() { 49 LineSegment[] results = new LineSegment[N]; 50 for (int i = 0; i < N; i++) { 51 results[i] = segment.get(i); 52 } 53 return results; 54 } 55 56 public static void main(String[] args) { 57 58 // read the N points from a file 59 // In in = new In(args[0]); 60 In in = new In("./collinear/rs1423.txt"); 61 int N = in.readInt(); 62 System.out.println(N); 63 Point[] points = new Point[N]; 64 for (int i = 0; i < N; i++) { 65 int x = in.readInt(); 66 int y = in.readInt(); 67 System.out.println("x:" + x + " y:" + y); 68 points[i] = new Point(x, y); 69 } 70 71 // draw the points 72 StdDraw.show(0); 73 StdDraw.setXscale(0, 32768); 74 StdDraw.setYscale(0, 32768); 75 for (Point p : points) { 76 p.draw(); 77 } 78 StdDraw.show(); 79 80 // print and draw the line segments 81 BruteCollinearPoints collinear = new BruteCollinearPoints(points); 82 for (LineSegment segment : collinear.segments()) { 83 StdOut.println(segment); 84 segment.draw(); 85 } 86 } 87 } BruteCollinearPoints

由于這個(gè)方法時(shí)間復(fù)雜度太高，于是提出一種N²?log?N?的方法，核心思路就是，通過實(shí)現(xiàn)一個(gè)排序方法，使點(diǎn)始終保持有序性來提高效率。看到N*NlogN,就想到了遍歷點(diǎn)后排序，orz。下面是官方給出的算法描述：

• Think of?p?as the origin.
• For each other point?q, determine the slope it makes with?p.
• Sort the points according to the slopes they makes with?p.
• Check if any 3 (or more) adjacent points in the sorted order have equal slopes with respect to?p. If so, these points, together with?p, are collinear.

實(shí)現(xiàn)的思路就是：

對(duì)所有點(diǎn)排序，越靠近左下角的點(diǎn)越小

遍歷每一個(gè)點(diǎn)，遍歷點(diǎn)P過程中，先將其他點(diǎn)根據(jù)與P的斜率進(jìn)行排序

對(duì)排序后的其他點(diǎn)進(jìn)行遍歷，若有斜率相同超過4個(gè)以上的點(diǎn)，即是要找的線段

按照這個(gè)思路，很快就實(shí)現(xiàn)除了代碼，需要注意的除了邊界等細(xì)節(jié)問題，再有就是，如何避免子線段和重復(fù)線段。這兩個(gè)問題把我卡住很久。

先說如何解決子線，所謂子線段就是原本線段：a->b->c->d->e是符合條件的，我將其取出，但是我又把b->c->d->e也當(dāng)作新的線段取出來了。一開始的思路是，每次遍歷一個(gè)點(diǎn)，都將其所有在一條線段上的點(diǎn)找出來，然后將這些點(diǎn)集sort一下，取最大最小。即在搜尋b的時(shí)候，將a,c,d,e和其本身b進(jìn)行排序，取最小a和最大e。這樣問題就解決了，但是同樣還有一個(gè)問題是，由于每個(gè)點(diǎn)都進(jìn)行了這樣的操作，會(huì)導(dǎo)致有很多重復(fù)的線段。通過a得到線段(a,e),通過b又得到一邊(a,e)，所以結(jié)果是需要去重的。非常自然的想到了hashset，保證了時(shí)間復(fù)雜度不高。

然而使用hashcode的思路都無法實(shí)現(xiàn)...原因是poin和segment兩個(gè)class都繼承了Object的hashcode()方法，但是僅僅是在調(diào)用時(shí)拋出異常...至于為何會(huì)這樣，原因是第三周還沒有講到hashtable這個(gè)數(shù)據(jù)結(jié)構(gòu)orz

這條路不行，退一步，用toString()方法，將其toString后，存入hashset，來檢查是否有重復(fù)的線段。我太機(jī)智了。不過這樣依然是不是100%的通過，看了下testcase，竟然有一條fail是說我不應(yīng)該依賴于toString()方法...

?

為什么不讓？我陷入了沉思，comment中提到，這個(gè)方法僅供debug用，不要用于實(shí)現(xiàn)算法...不過細(xì)想其實(shí)是非常有道理的。我的算法本身實(shí)際上是依賴于comparable接口以及camparator的實(shí)現(xiàn)。而不是依賴于point和segment這兩個(gè)具體的類。所以本身我就不應(yīng)該去依賴于這兩個(gè)類其他的方法，用了toString()只能說是非常tricky的方法。這樣的做法，做到了解耦。看到這個(gè)testcase，感覺自己和名校的學(xué)生差距就是在這些細(xì)節(jié)上拉開的。不做這樣的題，意識(shí)不到interface到底有啥用，不就是定義了幾個(gè)未實(shí)現(xiàn)的方法嗎？可是正是通過約定好的接口，做到了解耦。以后如果有人要修改point toString()，依然不會(huì)影響到我的程序的正確性。這就無形中提高了效率。

?

好了，回來說說我是怎么解決這個(gè)問題的。注意到，我在遍歷之前，就先sort了點(diǎn)，這個(gè)sort有啥用呢？這個(gè)sort意味著，等會(huì)對(duì)于每個(gè)點(diǎn)找共線線段時(shí)，是按照從左下往右上的順序來的，看圖說話：

排過序的點(diǎn)是按照1，2，3，4，5的順序來遍歷的。當(dāng)選取點(diǎn)1時(shí)，找到共線的5個(gè)點(diǎn){1,2,3,4,5}，因此我們選擇最大最小作為線段(1,5)。

當(dāng)選取點(diǎn)2時(shí)，找到了共線的5個(gè)點(diǎn){1,2,3,4,5}，這里也這里發(fā)現(xiàn)2＜1，由于有序性，我們可以確認(rèn)在此之前就有(1,5)被選取過了，所以這次的選擇可以直接跳過。

這意味著，只要是當(dāng)前遍歷的點(diǎn)P不是共線點(diǎn)集中最小的點(diǎn)，我們都可以直接拋棄。這樣就完美避免了重復(fù)的線段。

至此，根據(jù)這個(gè)方案，這個(gè)assignment圓滿解決了。

一下是fast方法的實(shí)現(xiàn)，其他的代碼就不貼了。

package collinear;import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashMap; import java.util.HashSet;import edu.princeton.cs.algs4.In; import edu.princeton.cs.algs4.StdDraw; import edu.princeton.cs.algs4.StdOut;public class FastCollinearPoints {private int N;private ArrayList<LineSegment> segment = new ArrayList<LineSegment>();private Point[] points;public FastCollinearPoints(Point[] points) {if (points == null)throw new java.lang.NullPointerException();this.points = new Point[points.length];for (int i = 0; i < points.length; i++) {this.points[i] = points[i];}N = 0;Arrays.sort(this.points);// remove repeat pointsfor (int i = 0; i < this.points.length - 1; i++) {if (this.points[i].compareTo(this.points[i + 1]) == 0) {throw new java.lang.IllegalArgumentException();}}Point[] temp = new Point[this.points.length];Point[] copy = new Point[this.points.length];ArrayList<ArrayList<Point>> end_sets = new ArrayList<>();// use a copy to sortfor (int i = 0; i < this.points.length; i++) {temp[i] = copy[i] = this.points[i];end_sets.add(new ArrayList<Point>());}Arrays.sort(copy);// to sort by slopefor (int i = 0; i < copy.length - 1; i++) {Arrays.sort(temp, copy[i].slopeOrder());// find same slope copy then save them as segment in segment// ArrayListint count = 1;double slope0 = copy[i].slopeTo(temp[0]);ArrayList<Point> set = new ArrayList<>();for (int j = 0; j < temp.length; j++) {// record max pointdouble slope1 = copy[i].slopeTo(temp[j]);if (slope1 == slope0) {set.add(temp[j]);count++;if (count > 2 && j == temp.length - 1) {set.add(copy[i]);Collections.sort(set);// System.out.println(set);if (set.get(0).compareTo(copy[i]) < 0) {} else {// no key, no setsegment.add(new LineSegment(set.get(0), set.get(set.size() - 1)));N++;} count = 1;}} else {if (count > 2) {set.add(copy[i]);Collections.sort(set);// System.out.println(set);if (set.get(0).compareTo(copy[i]) < 0) {} else {// no key, no setsegment.add(new LineSegment(set.get(0), set.get(set.size() - 1)));N++;}}set = new ArrayList<>();set.add(temp[j]);count = 1;}slope0 = slope1;}}}// the number of line segmentspublic int numberOfSegments() {return N;}// the line segmentspublic LineSegment[] segments() {LineSegment[] results = new LineSegment[N];for (int i = 0; i < N; i++) {results[i] = segment.get(i);}return results;}public static void main(String[] args) {// read the N points from a file// In in = new In(args[0]);In in = new In("./collinear/rs1423.txt");int N = in.readInt();// System.out.println(N);Point[] points = new Point[N];for (int i = 0; i < N; i++) {int x = in.readInt();int y = in.readInt();// System.out.println("x:" + x + " y:" + y);points[i] = new Point(x, y);}// draw the pointsStdDraw.show(0);StdDraw.setXscale(0, 32768);StdDraw.setYscale(0, 32768);for (Point p : points) {p.draw();}StdDraw.show();// // print and draw the line segmentsFastCollinearPoints collinear = new FastCollinearPoints(points);for (LineSegment segment : collinear.segments()) {StdOut.println(segment);segment.draw();}} } FastCollinearPoints

老規(guī)矩，亮下分?jǐn)?shù)：

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/yilujuechen/articles/4856540.html

總結(jié)

以上是生活随笔為你收集整理的Algorithm I assignment Collinear的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。