Assignment 3

admin 管理员组

文章数量: 1086866

Assignment 3

得分：

Correctness:  41/41 tests passed
Memory:       1/1 tests passed
Timing:       41/41 tests passedAggregate score: 100.00%

问题要求：
给定平面中的n个不同点的集合，找到连接4个或更多点的子集的每个（最大）线段。

Points.java

需要实现的方法：

 public int compareTo(Point that)  // compare two points by y-coordinates, breaking ties by x-coordinatespublic double slopeTo(Point that)  // the slope between this point and that pointpublic Comparator<Point> slopeOrder() // compare two points by slopes they make with this point

注意：区分+0与-0；区分正无穷与负无穷。才能做到严谨。

代码：

import edu.princeton.cs.algs4.StdDraw;import java.util.Comparator;public class Point implements Comparable<Point> {private final int x;     // x-coordinate of this pointprivate final int y;     // y-coordinate of this point/*** Initializes a new point.** @param x the <em>x</em>-coordinate of the point* @param y the <em>y</em>-coordinate of the point*/public Point(int x, int y) {/* DO NOT MODIFY */this.x = x;this.y = y;}/*** Draws this point to standard draw.*/public void draw() {/* DO NOT MODIFY */StdDraw.point(x, y);}/*** Draws the line segment between this point and the specified point* to standard draw.** @param that the other point*/public void drawTo(Point that) {/* DO NOT MODIFY */StdDraw.line(this.x, this.y, that.x, that.y);}/*** Returns the slope between this point and the specified point.* Formally, if the two points are (x0, y0) and (x1, y1), then the slope* is (y1 - y0) / (x1 - x0). For completeness, the slope is defined to be* +0.0 if the line segment connecting the two points is horizontal;* Double.POSITIVE_INFINITY if the line segment is vertical;* and Double.NEGATIVE_INFINITY if (x0, y0) and (x1, y1) are equal.** @param that the other point* @return the slope between this point and the specified point*/public double slopeTo(Point that) {/* YOUR CODE HERE */if (this.x == that.x && this.y != that.y) {return Double.POSITIVE_INFINITY;} else if (this.x == that.x) {return Double.NEGATIVE_INFINITY;} else if (this.y == that.y) {return +0.0;} else {return (double) (this.y - that.y) / (this.x - that.x);}}/*** Compares two points by y-coordinate, breaking ties by x-coordinate.* Formally, the invoking point (x0, y0) is less than the argument point* (x1, y1) if and only if either y0 < y1 or if y0 = y1 and x0 < x1.** @param that the other point* @return the value <tt>0</tt> if this point is equal to the argument* point (x0 = x1 and y0 = y1);* a negative integer if this point is less than the argument* point; and a positive integer if this point is greater than the* argument point*/public int compareTo(Point that) {/* YOUR CODE HERE */if (that == null) {throw new NullPointerException();}if (this.x == that.x && this.y == that.y) {return 0;} else if (this.y < that.y || (this.y == that.y && this.x < that.x)) {return -1;} else {return 1;}}/*** Compares two points by the slope they make with this point.* The slope is defined as in the slopeTo() method.** @return the Comparator that defines this ordering on points*/public Comparator<Point> slopeOrder() {/* YOUR CODE HERE */return new SlopeComparator();}private class SlopeComparator implements Comparator<Point> {public int compare(Point a, Point b) {if (a == null || b == null) {throw new NullPointerException();}return Doublepare(slopeTo(a), slopeTo(b));}}/*** Returns a string representation of this point.* This method is provide for debugging;* your program should not rely on the format of the string representation.** @return a string representation of this point*/public String toString() {/* DO NOT MODIFY */return "(" + x + ", " + y + ")";}

BruteCollinearPoints.java

暴力方法解决四个点共线的问题。题目要求输入不会有五个点及其以上共线。要求时间n⁴

代码:

public class BruteCollinearPoints {private LineSegment[] temp;private int lineNum;// finds all line segments containing 4 pointspublic BruteCollinearPoints(Point[] points) {if (points == null) {throw new IllegalArgumentException();}// 得到points的copy 顺便检测空点Point[] pointsCopy = new Point[points.length];for (int i = 0; i < points.length; i++) {if (points[i] == null) {throw new IllegalArgumentException();}pointsCopy[i] = points[i];}temp = new LineSegment[8];// 检查有无重复点Arrays.sort(pointsCopy);for (int i = 0; i < pointsCopy.length - 1; i++) {if (pointsCopy[i].equals(pointsCopy[i + 1])) {throw new IllegalArgumentException();}}for (int p = 0; p <= pointsCopy.length - 4; p++) {for (int q = p + 1; q <= pointsCopy.length - 3; q++) {for (int r = q + 1; r <= pointsCopy.length - 2; r++) {for (int s = r + 1; s <= pointsCopy.length - 1; s++) {if (pointsCopy[p].slopeTo(pointsCopy[q])== pointsCopy[p].slopeTo(pointsCopy[r])&& pointsCopy[p].slopeTo(pointsCopy[q])== pointsCopy[p].slopeTo(pointsCopy[s])) {if (lineNum == temp.length) {resize(temp.length * 2);}temp[lineNum] = new LineSegment(pointsCopy[p], pointsCopy[s]);lineNum += 1;}}}}}}// 当暂存线段的数组不够用了的时候，可以resize扩大private void resize(int length) {LineSegment[] newLS = new LineSegment[length];System.arraycopy(temp, 0, newLS, 0, temp.length);temp = newLS;}// the number of line segmentspublic int numberOfSegments() {return lineNum;}// the line segmentspublic LineSegment[] segments() {LineSegment[] lines = new LineSegment[lineNum];for (int i = 0; i < lineNum; i++) {lines[i] = temp[i];}return lines;}
}

注意：

1. 我使用的暂存线段的工具是数组而不是链表。使用链表也可以。数组因为不需要操作指针等，总体花费读和写的时间可能会更快一些。将resize操作的时间均摊给每个操作，数组会更快。（此处不在乎resize操作的时间突然增长，如果是大量数据包传输等操作，不希望突然卡顿带来数据丢失的风险，用链表更好）
2. 需要先将输入的数组points复制给一个副本，这样就保护了该类输入变量。

FastCollinearPoints.java

找到4个及以上的共线点。要求时间为n²logn。
主要思路是：让每个点都做一次原点，然后按照其他点到原点的斜率排序。排序完之后，共线的点一定是挨着的。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;public class FastCollinearPoints {private LineSegment[] temp;private int lineNum;// finds all line segments containing 4 or more pointspublic FastCollinearPoints(Point[] points) {if (points == null) {throw new IllegalArgumentException();}// 得到points的copy 顺便检测空点Point[] pointsCopy = new Point[points.length];for (int i = 0; i < points.length; i++) {if (points[i] == null) {throw new IllegalArgumentException();}pointsCopy[i] = points[i];}temp = new LineSegment[8];lineNum = 0;// 找是否有重复点Arrays.sort(pointsCopy);for (int i = 0; i < pointsCopy.length - 1; i++) {if (pointsCopy[i].equals(pointsCopy[i + 1])) {throw new IllegalArgumentException();}}// 用于记录共线的点，目的是判断它们之前是否已经出现过ArrayList<Point> collinear = new ArrayList<>();// 第一层循环，让所有的点都做一次原点for (int k = 0; k < pointsCopy.length - 1; k++) {// 按照y排序Arrays.sort(pointsCopy);// k点为原点Comparator<Point> slopec = pointsCopy[k].slopeOrder();// 按照斜率排序，排完之后pointsCopy[0]是之前的pointsCopy[k]Arrays.sort(pointsCopy, slopec);// 第二层循环，找相同的斜率for (int i = 1; i <= pointsCopy.length - 3; i++) {// j指向的点是和 i 与 k 共线的点int j = i + 1;collinear.clear();collinear.add(pointsCopy[0]);collinear.add(pointsCopy[i]);while (j < pointsCopy.length&& pointsCopy[0].slopeTo(pointsCopy[i])== pointsCopy[0].slopeTo(pointsCopy[j])) {collinear.add(pointsCopy[j]);j += 1;}if (j - i >= 3) {// 下一次再移动i的时候，将i跳过本次找到的共线点再继续移动即可i = j - 1;// collinear链表中放的是这一条线上的共线点。要得到的线段，只需要// y最低的点和y最高的点。因此，如果collinear中最低的点是原点，// 说明这条线段还没有被得到，如果不是，说明之前已经得到过了Collections.sort(collinear);if (collinear.get(0).equals(pointsCopy[0])) {if (lineNum == temp.length) {resize(temp.length * 2);}temp[lineNum] = new LineSegment(pointsCopy[0], pointsCopy[j - 1]);lineNum += 1;}collinear.clear();if (j == pointsCopy.length - 1) {break;}}}}}private void resize(int length) {LineSegment[] newLS = new LineSegment[length];System.arraycopy(temp, 0, newLS, 0, temp.length);temp = newLS;}// the number of line segmentspublic int numberOfSegments() {return lineNum;}// the line segmentspublic LineSegment[] segments() {LineSegment[] lines = new LineSegment[lineNum];for (int i = 0; i < lineNum; i++) {lines[i] = temp[i];}return lines;}
}

可以使用链表和Collections.sort来判断线段是否重复。之前没有想到这个方法，使用多一层循环来判断，这样时间测试没有通过。

参考了Algorithm I assignment Collinear

其中有两点很有启发，设计时需要注意的：保护输入变量 和 解耦。解耦就是说在实现功能的时候尽可能不要依赖对象中独有的方法，而要使用对象所实现的接口的方法。这样即使对象类型变化了，该方法仍然很稳定。

本文标签： Assignment 3