[HomeWork] Algorithms, Part I (week 3)

没看到有人post，就自开一贴，一起跟课的朋友们加油！
Fast里面的subsegment真的很trick，看了forum里的讨论才搞定。
高能搬运，相当剧透：

draw the segment only if current point is lower than all the others collinear points

debug 好久，还是应该先想好，再弄，唯一不过的是Fast timing 问题，难道要自己写一个mergesort么？

Fast里面，我用一个ArrayList <Point>[]  lines 存储当前的找到的直线的全部point(用于输出)，用另一个ArrayList<Point>[]  storeLines 存储已经找到的直线的min point 和 max point.  然后通过新找到的直线的min point 和 已经找到的直线的端点比较，
if (新直线和已经存储直线斜率相同 && (新直线minpoint. slopeTo(已存储直线minpoint) == 已存储直线minpoint.slopeTo(已存储直线maxpoint)) )
        sameline = true;

求版主多加分~  o(*￣▽￣*)ゞ

自己写的一直有问题 大家能否帮我看一下。 Brute解法我的答案如下：

1. import edu.princeton.cs.algs4.*;
   
2. import java.util.Arrays;
   
3. 
   
4. public class BruteCollinearPoints{
   
5. 
   
6.         private int SegNum = 0;
   
7.         private LineSegment[] res = new LineSegment[1];
   
8. 
   
9.         public BruteCollinearPoints(Point[] points){
   
10. 
    
11.                 if (points == null) {
    
12.                         throw new java.lang.NullPointerException();
    
13.                 } //argument is null
    
14. 
    
15.                 for (Point point : points) {
    
16.                         if(point == null) throw new java.lang.NullPointerException();
    
17.                 } //point is null
    
18. 
    
19.                 for (int i = 0; i < points.length; i++) {
    
20.                         for (int j = i+1; j < points.length; j++) {
    
21.                                 if(points[i].compareTo(points[j]) == 0) throw new java.lang.IllegalArgumentException();
    
22.                         }
    
23.                 } //repeated point
    
24. 
    
25.                 for (int i = 0; i < points.length; i++) {
    
26.                         Point p = points[i];
    
27.                         for (int j = i+1; j < points.length; j++) {
    
28.                                 Point q = points[j];
    
29.                                 for (int k = j+1; j < points.length; k++) {
    
30.                                         Point r = points[k];
    
31.                                         if(p.slopeTo(q) != q.slopeTo(r)) continue;
    
32.                                         for (int l = k+1; l < points.length; l++) {
    
33.                                                 Point s = points[l];
    
34.                                                 if(q.slopeTo(r) == r.slopeTo(s)){
    
35.                                                         Point[] resPoint = new Point[]{p, q, r, s};
    
36.                                                         Arrays.sort(resPoint);
    
37.                                                         LineSegment LS = new LineSegment(resPoint[0], resPoint[3]);
    
38.                                                         res[SegNum++] = LS;
    
39.                                                         if(SegNum == res.length) resize(2 * res.length);
    
40.                                                 }
    
41.                                         }
    
42.                                        
    
43.                                 }
    
44.                         }
    
45.                 }
    
46.         }
    
47. 
    
48.         private void resize(int capacity){
    
49.                 LineSegment[] temp = new LineSegment[capacity];
    
50.                 for (int i = 0; i < SegNum; i++) {
    
51.                         temp[i] = res[i];
    
52.                 }
    
53.                 res = temp;
    
54.         }
    
55. 
    
56.         public int numberOfSegments(){
    
57.                 return SegNum;
    
58.         }
    
59. 
    
60.         public LineSegment[] segments(){
    
61.                 return res;
    
62.         }
    
63. 
    
64. }         

复制代码

但是用他给的sample client一直有问题 总是出现 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 56
        at BruteCollinearPoints.<init>(BruteCollinearPoints.java:33) ...转专业还是太弱了

的确啊！！那个subsegment弄了超久！！

这周的作业很费时间啊。

求问-  wrong order: slope-ascending, y-ascending, x-ascending (but should not depend on x, y)这个问题怎么解决啊？
我Fast是定义了一个hashmap，每次保存一个斜率的数值和这条线上的最后一个点来避免重复，但是time test里的最后一个test老是通不过，求指教。谢谢！

letsdoit666 发表于 2015-2-15 14:18
求问-  wrong order: slope-ascending, y-ascending, x-ascending (but should not depend on x, y)这个问 ...

不好意思，没有出现过这个wrong order这个问题，也没有使用hashmap（貌似课程要求没学过的数据结构都不能用）。
我解决permutation是靠最开始的sort by position。解决subsegement也是靠加一句判断point position，就是只有当你现在check的这个点比所有其他共线的点的position都小的时候才画线。

交作业了

vancexu 发表于 2015-2-15 16:33
不好意思，没有出现过这个wrong order这个问题，也没有使用hashmap（貌似课程要求没学过的数据结构都不能 ...

有一个问题哎，我个人觉得之前不需要排序，但是这样出来的report里出现了莫名奇妙的很多错误。意思是之前必须得Arrays.sort一下，但是我觉得没必要，不懂层主怎么看？

letsdoit666 发表于 2015-2-16 00:17
有一个问题哎，我个人觉得之前不需要排序，但是这样出来的report里出现了莫名奇妙的很多错误。意思是之前 ...

题目中要求输出segment要有序的，所以我很自然的想到要在之前sort一下。你是怎么想的，为什么觉得没必要先sort？

这次作业中的好多东西都是看了网上的才知道的。惭愧。
比如，怎么解决重复画线的问题，我自己所能想到的就是遍历一下之前的点，如果有相等的就不画。然后网上给的做法真的很奇妙。我想不到。当然这种做法有一个很细节的注意点，我们需要提前定义一个pSlope，然后用来暂存i之前的斜率，这个pSlope不能随意初始化，只能初始化为，负无穷，即同一个点。否则就是Bug。因为在再赋值之前，系统会把这个初始值当作是 i 前的斜率，如果和 i 后的斜率正好相等，那么系统就会误解成，i 后的这个斜率在之前已经存在了，就把这条线给遗漏了。我是调试之后才发现的这个问题。所以必须把pSlope设置为一个i 后的斜率不可能到达值，但很明显，斜率的范围涵盖了所有值。所以只能把pSlope设置为即使可以到达，即使i 后面的斜率与这个初始值相等，系统也没有误判。那只可能是 负无穷，即 i后的多个点与 i 点其实是一点，那么他们是不可以画线的。
还有一开始的一个误区，我总以为，一个起点，只能最多有一条线段。所以进入那个画线的分支后就直接break，没进入则，head++,tail++. 脑子犯浑了。
还有之前java基本零基础。提示说 用 Arrays.sort() 来进行排序，一开始真的不懂。
这次作业最大的帮助可能是知道 Comparator怎么用了。然后思考问题的方法。一些很细节的东西只有Debug的时候才能发现。

交作业啦。