Week1: Percolation
主要思路
- 想要达到Percolation的状态,则要一个正方形的矩阵块中,从顶到底,一个小块能通过与其前后左右的方块连通,并由此传递到底部的方块。
- 采用WeightedQuickUnionFind将已经open的方块union起来,可以形成一串已经open的方块,之后每次新open一个方块,用find方法,来判断parent方块是否与顶或者底连通。
- 如果一个方块,与顶和底都能连通,此时整个矩阵块达到Percolation的状态。
一些注意点
- 将二维矩阵转化为一位,通过xyTo1D方法来实现,转化以后的数组用来记录某个方块是否open,是否与顶和底连通都状态信息。
- 当open了一个方块后,要将它与前后左右四块方块中已经open的连通起来,并且判断他们的parent是否与顶或者底连通。
- 注意边界问题,行和列的取值大于等于1,小于等于n;并且,如果第一行或者第n行的方块open了,那此方块的parent方块与顶或者底也就连通了。
- (double)percolation.numberOfOpenSites()/(range*range)前面要用double进行强转,因为分母大于分子,并且都是int型,如果不进行强转,相除之后的值为0。
Week2: Queue
主要思路
- Deque使用的数据结构是定义一个内部类Node,其中一个node里有:
- 泛型 Item – 当前节点
- Node prev – 前节点
- Node next – 后节点
- RandomizedQueue则采用可变长度的数组:
- 当元素个数增加到当前数组最大长度时,则将数组容量翻倍。
- 当元素个数减少到当前数组最大长度的1/4时,则将数组容量缩小到一半。
###一些注意点
- Deque的四个方法:addFirst/addLast/removeFirst/removeLast的主要目的就是建立相邻两个节点之间的双向连接,增加和删除首尾节点时,新节点与前节点或者后节点的连接该变动的变动。拿addFirst举例:
- 在头节点前增加新节点,则原来的first节点变成oldFirst。
- 此时要新建一个节点first = new Node(),并且赋值:first.item = item + first.next = oldFirst。
- 判断极限情况:如果当前Deque为空,则first和last节点相同;如果不为空,则oldFirst.prev = first,将旧first节点的前节点链接到当前的first节点。
- RandomizedQueue最主要的一个特点就是每次调用iterator或者dequeue方法,都是取一个n范围内的随机数。例如迭代器的next方法里,用StdRandom.uniform(n)生成随机数,然后取出该值,并且将temp[index] = temp[i - 1],然后将temp[i - 1] = null,释放存储空间。
Week3: Collinear
主要思路
Brute类型算法
由于这个算法只要求找到4点共线,那就采用暴力枚举的方法,用4个循环,找4个点,分别计算后三点与第一个点的斜率,然后再比较斜率,如果三个斜率分别相等,再将4个点进行排序,线段就由最小点和最大点组成。
Fast类型算法
- 每个点都作为起始点,用slopeOrder()这个比较器来对Points数组进行排序。
- 接着比较斜率的大小,只要斜率一直相同,记录相同斜率线条的参数就一直自增,但只要一出现斜率不同,所有初始参数重置,不管此时是否达到要求有4点或以上的点共线。
- 为了避免重复计算的情况出现,只计算min点和tempPoints[0]点是同一个点的线段,因为每个循环都是想找以当前标准点为起始点的共线线段。
- 极限情况,如果最后一条斜率刚刚满足到dotCounts >= 2,那把这条线段也要包括进来。
一些注意点
- java程序的输入还是输出的array,一定要在程序内做个copy,不是仅仅copy reference,是把reference所指向的object也copy了。这样,当程序外面的array有变化的时候,不会影响程序内的数据,就是immutable的了!BruteCollinearPoints.java解释了为什么计算共线点的代码要写在构造函数里的原因:保证segments方法返回的value是不变的, 如果写在segments方法里面,可能会造成lineSegments对象还在改变的时候, 就返回了value。
- 尽量不要改变传入参数的数据结构,如果非要改变,则先copy到另外一个参数里去,在另外一个参数里去改变。
- Point.java里的slopeComparator内部类,compare方法在比较斜率的时候,刚开始用了判断slope1 - slope2 == 0的方式,显然是错误的,因为斜率是double类型,而0是int型,真是低级的错误!
Week4: 8puzzle
主要思路
- 8puzzle是一个九宫格,只有8个位置上有数字,想要把每个数字都按照从左到右从上到下顺序移动到各自的位置所需要的最优步数。
- 它有一个重要特性是:随意交换两个不为零的位置的数字,如果新的board可以最终移动到目标位置的话,那原来的board肯定是没有解的。
- 有两个距离:
- hamming:不在正确位置上的数字的个数
- manhattan: 在错误位置上的数字离目标位置的距离(横向和竖向距离的和)
- neighbors定义:空位置与上下左右非空位置调换后的board,一个board最多会有四个neighbor,最少会有两个(在四个角上的情况)。
- 程序里面的MinPQ是一个priority queue,每次调用delMin方法,都会返回当前队列里面预计需要步数(priority = manhattan + current moves)最小的节点(node),这里把每移动一步都当做一个节点,直到先达到目标位置为止。
- 为了避免重复移动,如果上一步节点的board位置与当前board位置相同,则不用将此board当做一个节点加入MinPQ,代码中即是node.prev != null && cur.prev.board.equals(board)。
- 等到所有位置都到目标位置之后,判断当前节点是否是twin节点,如果不是,则说明有解,则利用node.prev把刚才一步步都装进stack里,作为解的步骤;如果是,则说明原board无解。
一些注意点
- 遇到二维数组,慎用clone方法,因为复制了二维数组以后,每行的引用对象相同,复制的二维数组的变化会导致原数组也产生变化。
- 将原board和twin board放在一个MinPQ里最重要的原因是性能的考虑,而且由于这两者互斥,只要一个有解,另一个就是无解的,此时可以跳出while循环,进行下面的程序。
Week5: KdTree
主要思路
- 作业题目的要求是给定平面内的一个矩形,找到离矩形内已知一点距离最近的点。
- KdTree.java采用红黑二叉树算法和递归方式,逐步逼近离已知点最近的点;PointSET.java采用暴力枚举的方法,找到最近点以及矩形范围内包含的所有点的stack队列。
- 2d-tree在奇数层和偶数层的时候,对于矩形的分割是不同的,注意区分。
- 其他注意点请参照代码里的标注。