[HomeWork] Algorithms, Part I (week 3)

fast中的避免subsegment花费了些时间思考。最后采用的方法是每找到一条直线，遍历已查过的点，判断其与当前点的slope是否等于本次检测到的直线斜率，相等则表明是subsegment需要舍弃。
最后的一个timing测试没通过，可能需要修改逻辑来优化，就先这样吧 = =

先贴作业：

感觉这次作业主要有3个点需要解决：
1. permutation
这个问题我真的是疯狂地在想....前前后后断断续续想了一个多星期才想出来....
比如一个p->q->r->s的 segment；一共有4!个permutation
但basePoint（slopeTo()的invoking point）只有4种可能: p, q, r, s
Sort by SLOPE_ORDER 导致basePoint一定是第1个(slope = NEGATIVE_INFINITY)
在SLOPE_ORDER之前，先sort by natural order，那么basePoint之后的3个点一定会按natural order排列
   Why？Java Arrays.sort()对object采用merge sort，是stable的，所以SLOPE_ORDER相等的在一起的几个点一定符合前一次的natural order;
    唯一的例外是basePoint，理论上他应该和这3个点在一起的；但他被强制定义成了NEGATIVE_INFINITY，导致一定是最小的那个
那么4!种permutation就只剩4种了.
再考虑这4个点的natural order，其中只有1种是4个点均符合natural order的，也就是natural order最小的点作为basePoint；不妨就只输出这一种。
basePoint在第一个是invariant，后面3个符合natural order也是invariant，那要保证4个点符合natural order，只需保证basePoint比它后一个点小(natural order)
若一共不止4个点，同理。

2. subsegment
这个就是考虑segment with 5 or more points了；
不能输出subsegment，就是要摒弃那种i, i + 1, i + 2到basePoint的斜率相等的方法了。
我的方法比较复杂了:
选定basePoint，sort(by natural order then by SLOPE_ORDER)之后:
scan第1遍: 把segment的front和end标注出来（front的特征是和后一个相等，和前一个不相等；end反之）；
scan第2遍：设置一个distance变量；遇到第1遍marked的frontdistance开始递增；如果遇到end且distance ≥ 3, 就输出这个线段，然后distance归零
然后我看到楼主在discussion forum上找的方法，私以为楼主表述有误：
LZ找的那个方法是解决permutation，而不是subsegment的...(原理和1.应该一样)

3. “bonus point” －degenerate line
这次的作业没有bonus point，但我觉得这个corner case挺有挑战的，可以作为bonus point；test 文件也很好编；
如果两个点重合，那么line segment degenerate to a point; slopeTo()输出NEGATIVE_INFINITY
作业唯一用到这个是sort by SLOPE_ORDER，第一个点一定是自身；
checklist第一条也说了“You may assume the input to Brute and Fast are N distinct points”；
假设作业难一点，考虑存在一些相同的点，那么1.中解决permutation的方法就失效了，因为所有n! (n: # of points of the segment) permutation均是符合natural order的(因为全部重合);
－a. 如果认为n个重合的点也算共线，那么方法就是提前把basePoint sort by natrual order，这样相同的basePoint一定在一起，只让第一个basePoint进来，就可以保证每组相同的basePoint进来只有一次，再就是front和end的mark也要注遇到一组相同的目标点的情况。
   如果≥3个的点重合，那么这个重合和其他所有点都有连线，图形会非常乱，所以我认为b.更intuitive一点.
－b. 如果认为n个重合的点不算共线，只留一个点考虑，其他剔除，我还没有想出来解决办法。

不小心把含有原点的那个Array排序了，调了好久才发现……

自己写的一直有问题 大家能否帮我看一下。 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) ...转专业还是太弱了

FFFelix 发表于 2016-3-1 11:23
自己写的一直有问题 大家能否帮我看一下。 Brute解法我的答案如下：

你的数组LineSegment长度才是1，怎么能放两个元素呢？
应该是：
private LineSegment[] res = new LineSegment[2];
吧？
手误了吧？

google了诸位大神的代码调通后才发现这次的api改了，必须用它写的LineSegment类里的方法，晕死，还得改……

愚蠢如我╰(￣▽￣)╭

总结下这次作业中遇到的问题：

FastCollinearPoints类

1.      ★ Subsegment的问题，没看坛子的时候用了一个cost比较重的方法，对每组符合条件的点，用compareTo()找出最大，最小的Point作为endPoints存下来（因为LineSegment的Point p q invisible）。每次遍历已经找出的LineSegment Array找重复。

LZ搬运的方法棒棒哒~所以就检讨下之前的方法存在的问题~

Timing里CompareTo()会挂掉，而且在LineSegment灰常灰常多的时候，size很大，这个Loop的代价就不能忽略不计了~

2.      之前总是Initialize 存储LineSegment的矩阵= new LineSegment[points.length()]，分分钟Indexbound！加了一个reShape()就好了，大家有没有什么更好的办法吖~

编程小白总会觉得用LinkedList的话，Timing 代价很大的样子~new Node()和reshape()不知道哪个比较好~虽然这道题LineSegment的矩阵不涉及按索引查找，应该是可以用LinkedList的~

3.      不用Arrays.Sort() Timing里compare()也要挂，渣一样的英语╰(￣▽￣)╭还以为题目说的是不能用Arrays.Sort()，于是自己写了一个3-way QuickSort()，话说 3-way QuickSort在N个不同item的时候复杂度不是NlogN么，为啥也会过不了Timing 。Arrays.Sort()为什么就可以！ -。

2个问题求大神解答~

Q1: Point类里，slopeTo()如果不判段y0 = y1的情况，为什么算出来的slope默认为 -0.0

Q2: compareTo() 里，我用-1表示returnnegative integer，1表示positive integer，report里面说我的compareTo返回1而不是positive integer，要怎么返回一个positive integer？