0%

总结

(代码有详细注释)

  1. 本课讲了归并排序,作业应用是排序进行共线的模式识别,java1.8中的排序用的是tim排序,结合了归并排序与插入排序,属于稳定排序:排序之后相同元素的相对位置会不会改变
  2. Point.java中有个非常重要的方法,compareTo(),它定义:纵坐标越小则点越小,如果纵坐标相同,那么横坐标越小则点越小.(如果作业中要求横坐标也是按顺序排列,那么排序后的点集映射到二维坐标系中是非递减的折线, 这样找共线只用一层循环即可,可惜作业没加上对x的限制)
  3. 比较大小,一开始我用的是points[i-1] == point[i],尽管坐标相同但是points[i-1]不等于points[i]
    因为points[i-1]和points[i]表示引用,在堆中指向两个不同的地址,比较大小得用points[i-1].compareTo(points[i])
  4. 在FastCollinearPoints.java中,一定要注意什么时候对共线点数变量count进行判断,有两种情况,一个是,相邻元素与参考点的斜率不同;另一个是循环到最后一个元素.这两种情况在代码注释中有解释
  5. 唯一一处FAILED,扣了1分,没系统学过java,先跳过了
    1
    2
    3
    4
    5
    6
    7
    8
    Test 7: check for dependence on either compareTo() or compare()
    returning { -1, +1, 0 } instead of { negative integer,
    positive integer, zero }
    * filename = equidistant.txt
    - number of entries in student solution: 0
    - number of entries in reference solution: 4
    - 4 missing entries in student solution, including: '(30000, 0) -> (20000, 10000) -> (10000, 20000) -> (0, 30000)'
    ==> FAILED
  6. week3课件中,递归调用的图示:
    这是包含两个递归调用的递归 (图示只画了一半)
    Merge.jpg

代码

(如需提交,请删除中文注释)

一:Point.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import java.util.Comparator;
import edu.princeton.cs.algs4.StdDraw;
public class Point implements Comparable<Point> {
// x-coordinate of this point
private final int x;
// y-coordinate of this point
private final int y;
// constructs the point (x, y)
public Point(int x, int y) {
this.x = x;
this.y = y;
}
// draws this point
public void draw() {
StdDraw.point(x,y);
}
// draws the line segment from this point to that point
public void drawTo(Point that) {
StdDraw.line(this.x, this.y, that.x, that.y);
}
// string representation
public String toString() {
return "(" + x + ", " + y + ")";
}
// compare two points by y-coordinates, breaking ties by x-coordinates
public int compareTo(Point that) {
if(y<that.y || (y==that.y && x<that.x)) return -1;
else if(y==that.y && x==that.x) return 0;
else return +1;
}
// the slope between this point and that point
public double slopeTo(Point that) {
if(x==that.x && y==that.y) return Double.NEGATIVE_INFINITY;
if(x==that.x && y!=that.y) return Double.POSITIVE_INFINITY;
if(y==that.y) return +0.0;
return (double)(y-that.y)/(x-that.x);
}
// compare two points by slopes they make with this point
public Comparator<Point> slopeOrder(){
return new SlopeOrder();
}
//nested class
//sort rule
private class SlopeOrder implements Comparator<Point>{
public int compare(Point p,Point q) {
//p点斜率大
if(slopeTo(p)<slopeTo(q)) return -1;
//p点斜率小
else if(slopeTo(p)>slopeTo(q)) return 1;
//p,q斜率相等
else return 0;
}
}

public static void main(String[] args) {
Point p1 = new Point(0,0);
Point p2 = new Point(1,1);
Point p3 = new Point(2,2);
Point p4 = new Point(2,1);
Point p5 = new Point(4,1);
System.out.println("p1.compareTo(p1) is "+p1.compareTo(p2));
System.out.println("p2.compareTo(p1) is "+p2.compareTo(p1));
System.out.println("p1.compareTo(p1) is "+p1.compareTo(p1)+"\n");

System.out.println("p1.slopeTo(p2) is " +p1.slopeTo(p2));
System.out.println("p1.slopeTo(p4) is "+p1.slopeTo(p4));
System.out.println("p1.slopeTo(p1) is "+p1.slopeTo(p1));
System.out.println("p3.slopeTo(p4) is "+p3.slopeTo(p4));
System.out.println("p2.slopeTo(p5) is "+p2.slopeTo(p5));
}
}

二:BruteCollinearPoints.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
import java.util.ArrayList;
import java.util.Arrays;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Insertion;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdDraw;

public class BruteCollinearPoints {
//to store line segments
private ArrayList<LineSegment> LineSegmentList;
//to store the given points
private Point[] points;

//在构造函数中找出由4点构成的线段(作业说了:没有5点及更多点共线的情况)
// finds all line segments containing 4 point
public BruteCollinearPoints(Point[] pointsIn) {
//三种异常
//一:if the argument to the constructor is null
System.out.println(" a ");
if(pointsIn == null) throw new IllegalArgumentException("there is no point");
//二:if any point in the array is null
int N = pointsIn.length;
for(int i=0;i<N;i++) if(pointsIn[i]==null) throw new IllegalArgumentException("exist null point");
//三:if the argument to the constructor contains a repeated point
//检查是否有重复的点,先排序,再查重会方便,作业允许这样: For example, you may use Arrays.sort()
points = new Point[N];
for(int i=0;i<N;i++) points[i] = pointsIn[i];
Arrays.sort(points);
for(int i=1;i<N;i++) if(points[i-1].compareTo(points[i])==0) throw new IllegalArgumentException("exist repeated point");

//to save every required line segment
LineSegmentList = new ArrayList<LineSegment>();

//find line segment
for(int dot1=0;dot1<=N-4;dot1++) {
for(int dot2=dot1+1;dot2<=N-3;dot2++) {
//k12:the slope between point[dot2] and point[dot1]
double k12 = points[dot2].slopeTo(points[dot1]);
for(int dot3=dot2+1;dot3<=N-2;dot3++) {
//k13:the slope between point[dot3] and point[dot1]
double k13 = points[dot3].slopeTo(points[dot1]);
if(k13 != k12) continue;
for(int dot4=dot3+1;dot4<=N-1;dot4++) {
//k14:the slope between point[dot4] and point[dot1]
double k14 = points[dot4].slopeTo(points[dot1]);
if(k14 != k12) continue;
//find a line segment
LineSegment linesegment = new LineSegment(points[dot1],points[dot4]);
LineSegmentList.add(linesegment);
}
}
}
}
}
// the number of line segments
public int numberOfSegments() {
return LineSegmentList.size();
}
// the line segments
public LineSegment[] segments() {
LineSegment[] segments = new LineSegment[LineSegmentList.size()];
int index=0;
for(LineSegment Line : LineSegmentList) {
segments[index++] = Line;
}
return segments;
}
//main
public static void main(String[] args) {
In in = new In("src/week3/input8.txt");
int n = in.readInt();
StdOut.println("total "+n+" points");
Point[] points = new Point[n];
for (int i = 0; i < n; i++) {
int x = in.readInt();
int y = in.readInt();
StdOut.println("("+x+","+y+")");
points[i] = new Point(x,y);
}
//draw the points
StdDraw.enableDoubleBuffering();
StdDraw.setXscale(0, 32768);
StdDraw.setYscale(0, 32768);
StdDraw.setPenColor(StdDraw.RED);
StdDraw.setPenRadius(0.01);
for (Point p : points) {
p.draw();
}
StdDraw.show();
// print and draw the line segments
BruteCollinearPoints collinear = new BruteCollinearPoints(points);
StdOut.println(collinear.numberOfSegments());
for (LineSegment segment : collinear.segments()) {
StdOut.println(segment);
segment.draw();
}
StdDraw.show();
}
}

三:FastCollinearPoints.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
import java.util.ArrayList;
import java.util.Arrays;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdOut;

//much faster than the brute-force solution
public class FastCollinearPoints {
//to store line segments
private ArrayList<LineSegment> LineSegmentList;
//to store the given points
private Point[] points;

// finds all line segments containing 4 or more points
public FastCollinearPoints(Point[] pointsIn) {
//三种异常
//一:if the argument to the constructor is null
if(pointsIn == null) throw new IllegalArgumentException("there is no point");
//number of points
int N=pointsIn.length;
//二:if any point in the array is null
for(int i=0;i<N;i++) if(pointsIn[i]==null) throw new IllegalArgumentException("exist null point");
//三:if the argument to the constructor contains a repeated point
//检查是否有重复的点,先排序,再查重会方便,作业允许这样: For example, you may use Arrays.sort()
//同时有利于后面排除重复线段
points = new Point[N];
for(int i=0;i<N;i++) points[i] = pointsIn[i];
//用的是结合了归并和插入的tim排序,稳定排序
Arrays.sort(points);
for(int i=1;i<N;i++) if(points[i-1].compareTo(points[i])==0) throw new IllegalArgumentException("exist repeated point");

//to save every required line segment
LineSegmentList = new ArrayList<LineSegment>();


//当前的参考点
Point currentCheck;
//对照点重新存储,不包括参考点,共N-1个
Point[] otherPoints = new Point[N-1];
//开始比较斜率,一个一个来
for (int i=0;i<N;i++) {
currentCheck = points[i];
// copy points without Point currentCheck to otherPoints
for(int j=0;j<N;j++) {
if(j<i) otherPoints[j] = points[j];
if(j>i) otherPoints[j-1] = points[j];
}

//根据斜率对点排序
//用的是结合了归并和插入的tim排序,稳定排序
Arrays.sort(otherPoints,currentCheck.slopeOrder());
//遍历已经排序的otherPoints找线段
//注意,归并和插入排序都是稳定的,所以tim排序是稳定的,这非常重要
//配合Point的compareTo方法,可以直接过滤掉重复线段
//一开始没太注意compareTo方法,后来发现这个方法能固定住点之间的相对位置,所以可以过滤重复线段
//两点共线
int count=2;
for(int k=1;k<N-1;k++) {
double k1 = otherPoints[k-1].slopeTo(currentCheck);
double k2 = otherPoints[k].slopeTo(currentCheck);
if(k1==k2) {
count++;
//当循环到最后一个点,同时这个点和前面的点共线
if(k==N-2) {
//如果4点及以上共线,并且otherPoints中与参考点共线且排在最左边的点比参考点大的话,注意此处是遍历到头,所以索引是k-count+2
if(count>=4 && currentCheck.compareTo(otherPoints[k-count+2])==-1) {
//线段起点
Point start = currentCheck;
//线段终点
Point end = otherPoints[k];
LineSegment linesegment = new LineSegment(start,end);
LineSegmentList.add(linesegment);
}
}
}
else{
//如果4点及以上共线,并且otherPoints中与参考点共线且排在最左边的点比参考点大的话,索引是k-count+1
if(count>=4 && currentCheck.compareTo(otherPoints[k-count+1])==-1) {
Point start = currentCheck;
Point end = otherPoints[k-1];
LineSegment linesegment = new LineSegment(start,end);
LineSegmentList.add(linesegment);
}
count=2;
}
}
}
}

// the number of line segments
public int numberOfSegments() {
return LineSegmentList.size();
}
// the line segments
public LineSegment[] segments() {
LineSegment[] segments = new LineSegment[LineSegmentList.size()];
int index=0;
for(LineSegment Line : LineSegmentList) {
segments[index++] = Line;
}
return segments;
}

//main
public static void main(String[] args) {
In in = new In("src/week3/input9.txt");
int n = in.readInt();
StdOut.println("total "+n+" points");
Point[] points = new Point[n];
for (int i = 0; i < n; i++) {
int x = in.readInt();
int y = in.readInt();
StdOut.println("("+x+","+y+")");
points[i] = new Point(x,y);
}

//draw the points
StdDraw.enableDoubleBuffering();
StdDraw.setXscale(0, 32768);
StdDraw.setYscale(0, 32768);
StdDraw.setPenColor(StdDraw.RED);
StdDraw.setPenRadius(0.01);
for (Point p : points) {
p.draw();
}
StdDraw.show();

//print and draw the line segments
FastCollinearPoints collinear = new FastCollinearPoints(points);
StdOut.println(collinear.numberOfSegments());
for (LineSegment segment : collinear.segments()) {
StdOut.println(segment);
segment.draw();
}
StdDraw.show();
}
}

总结

一.Deque

目标:
A double-ended queue or deque is a generalization of a stack and a queue that supports adding and removing items from either the front or the back of the data structure. Create a generic data type Deque that implements the following API
要求:
Your deque implementation must support each deque operation (including construction) in constant worst-case time. A deque containing n items must use at most 48n + 192 bytes of memory and use space proportional to the number of items currently in the deque. Additionally, your iterator implementation must support each operation (including construction) in constant worst-case time.
分析:
deque可以分别在头尾做添加删除操作,并且在最坏的情况下消耗常数时间,所以数组不行,因为使用数组在头部添加或删除元素时必须修改后面所有元素的索引,这个操作耗费时间随数组长度的增加而增加.所以采用链表结构,在头尾维护两个指针即可实现constant time

二.Randomized queue

目标:
A randomized queue is similar to a stack or queue, except that the item removed is chosen uniformly at random from items in the data structure. Create a generic data type RandomizedQueue that implements the following API
要求:
Your randomized queue implementation must support each randomized queue operation (besides creating an iterator) in constant amortized time. That is, any sequence of m randomized queue operations (starting from an empty queue) must take at most cm steps in the worst case, for some constant c. A randomized queue containing n items must use at most 48n + 192 bytes of memory. Additionally, your iterator implementation must support operations next() and hasNext() in constant worst-case time; and construction in linear time; you may (and will need to) use a linear amount of extra memory per iterator.
分析:
为实现randomized queue的(除iterator操作)操作平摊时间最差是常数需要采用数组实现,虽然数组长度的扩展或者缩短所需时间正比于数组当前存储元素的个数,但是实现其余API(除iterator操作)的操作只需常数时间,把耗费的时间平摊后就是常数时间了.
为什么不能采用链表结构呢?链表结构实现literator非常方便,只需创建一个指针,不断移动指针的位置就可以实现iterator的各个功能,耗费常数时间,但是题目并不要求iterator耗费常数时间,注意到public Item dequeue()这个API,要求remove and return a random item,难点在于随机返回一个元素,首先创建一个随机数作为索引,对于链表来说,需要移动相应次数的指针找到那个元素,这个操作耗费时间正比于随机数的大小,不是常数时间.

三. Permutation

目标:
Write a client program Permutation.java that takes an integer k as a command-line argument; reads in a sequence of strings from standard input using StdIn.readString(); and prints exactly k of them, uniformly at random. Print each item from the sequence at most once.
要求:
The running time of Permutation must be linear in the size of the input. You may use only a constant amount of memory plus either one Deque or RandomizedQueue object of maximum size at most n. (For an extra challenge, use only one Deque or RandomizedQueue object of maximum size at most k)
分析:
没能完成extra challenge,所以扣了5分
这个直接看代码即可

代码

一.Deque

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
import java.util.Iterator;

public class Deque<Item> implements Iterable<Item>{
private Node first,last; //64位系统,每个引用8bytes,此处共16bytes
private int n; //4bytes

private class Node{ //64位系统,对象头16bytes , 内部类开销8bytes
private Item item; //64位系统,8bytes
private Node next; //64位系统,8bytes
private Node pre; //64位系统,8bytes 所以,1个Node占用48bytes,n个Node就是48n bytes
}

// construct an empty deque
public Deque() {
first = null;
last = null;
n = 0;
}

//is Deque empty?
public boolean isEmpty() {
return n == 0;
}

// return the number of items on the deque
public int size() {
return n;
}

// add the item to the front
public void addFirst(Item item) {
if(item==null) throw new java.lang.IllegalArgumentException("there is nothing");
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
//if(isEmpty()) just use n rather to call isEmpty()
if(n==0) last = first;
else oldfirst.pre = first;
n++;
}

// add the item to the end
public void addLast(Item item) {
if(item==null) throw new java.lang.IllegalArgumentException("there is nothing");
Node oldlast = last;
last = new Node();
last.item = item;
last.pre = oldlast;
if(n==0) first = last;
else oldlast.next = last;
n++;
}

// remove and return the item from the front
public Item removeFirst() {
//if 'if' runs,the program would stop
if(n==0) throw new java.util.NoSuchElementException("Deque is empty!!");
Item temp = first.item;
first = first.next;
n--;
//check if the Deque is empty after remove
if(n==0) last = null;//first is null now
else first.pre = null;
return temp;
}

// remove and return the item from the end
public Item removeLast() {
if(n==0) throw new java.util.NoSuchElementException("Deque is empty!!");
Item temp = last.item;
last = last.pre;
n--;
if(n==0)first = null;
else last.next=null;
return temp;
}

// return an iterator over items in order from front to end
public Iterator<Item> iterator(){
return new ListIterator();
}
private class ListIterator implements Iterator<Item>{ //对象头:16bytes
private Node current = first; //内部类额外开销8bytes,引用8bytes

public boolean hasNext() {
return current != null;
}

public void remove() {
throw new java.lang.UnsupportedOperationException("you mustn't do this!");
}

public Item next() {
if(current == null) throw new java.util.NoSuchElementException("no such element");
Item temp = current.item;
current = current.next;
return temp;
}
}

//main
public static void main(String[] args) {
Deque<String> deque = new Deque<String>();
System.out.println(deque.size());
deque.addFirst("haha");
deque.addFirst("hehe");
deque.addFirst("heihei");
deque.addFirst("hiahia");
deque.addFirst("houhou");
System.out.println(deque.size());
deque.removeFirst();
System.out.println(deque.size());
deque.removeLast();
System.out.println(deque.size());
Iterator<String> i = deque.iterator();
while(i.hasNext()) System.out.println(i.next());
}
}

二.Randomized queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
import java.util.Iterator;
import edu.princeton.cs.algs4.StdRandom;

//Additionally, your iterator implementation must support operations next() and hasNext()
//in constant worst-case time;
public class RandomizedQueue<Item> implements Iterable<Item> {
private Item[] randomq;
private int n;

// construct an empty randomized queue
public RandomizedQueue() {
randomq = (Item[]) new Object[1];
n = 0;
}
// is the randomized queue empty?
public boolean isEmpty() {
return n == 0;
}
// return the number of items on the randomized queue
public int size() {
return n;
}

//resize the array
private void resize(int size) {
//temp is a "yinyong"
Item[] temp = (Item[]) new Object[size];
for(int i=0;i<n;i++) temp[i] = randomq[i];
randomq = temp;
}

// add the item
public void enqueue(Item item) {
if (item==null) throw new java.lang.IllegalArgumentException("there is nothing");
if(n==randomq.length) resize(2*n);
randomq[n++] = item;

}

// remove and return a random item
//exchange the chosen element with the last element
//then,delete the last one
//so that realize deleting the random element in the end of queue
public Item dequeue() {
//faster than call isEmpty()
if(n==0) throw new java.util.NoSuchElementException("array is empty");
int i = StdRandom.uniform(0,n);
Item temp = randomq[i];
// pay attention to the change of n
if(i != --n) randomq[i] = randomq[n];
randomq[n] = null;
//here without n>0.wrong,try:add one,delete one
if(n>0 && n==randomq.length/4) resize(randomq.length/2);
return temp;
}

// return a random item (but do not remove it)
public Item sample() {
if(n==0) throw new java.util.NoSuchElementException("array is empty");
return randomq[StdRandom.uniform(0,n)];
}

// return an independent iterator over items in random order
public Iterator<Item> iterator(){
return new RandomIterator();
}

// inner class
private class RandomIterator implements Iterator<Item>{
// m is as index,just like the pointer in Deque
private int m;
private Item[] iterq;
private RandomIterator() {
iterq = (Item[])new Object[n];
for(int i=0;i<n;i++) iterq[i] = randomq[i];
//random order
StdRandom.shuffle(iterq);
}

public boolean hasNext() {
return m < n;
}

public void remove() {
throw new java.lang.UnsupportedOperationException("you mustn't do this!");
}

public Item next() {
if(m>=n) throw new java.util.NoSuchElementException("no next element!");
Item temp = iterq[m++];
return temp;
}
}
// unit testing (optional)
public static void main(String[] args) {
RandomizedQueue<String> rq = new RandomizedQueue<String>();
System.out.println(rq.isEmpty());
System.out.println(rq.size());
rq.enqueue("haha");
rq.enqueue("heihei");
rq.enqueue("hiahia");
rq.enqueue("hehe");
rq.enqueue("houhou");
System.out.println(rq.size());
rq.dequeue();
rq.dequeue();

Iterator<String> iter = rq.iterator();
while(iter.hasNext()) System.out.println(iter.next());
System.out.println();
Iterator<String> iter2 = rq.iterator();
while(iter2.hasNext()) System.out.println(iter2.next());
}
}

三. Permutation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class Permutation {
public static void main(String[] args) {
//jvm在调用主函数时,传入的是new args[0]
int k = Integer.parseInt(args[0]);
RandomizedQueue rq = new RandomizedQueue();
while(!StdIn.isEmpty()) {
rq.enqueue(StdIn.readString());
}
while(rq.size()-k>0) rq.dequeue();
for(int i=0;i<k;i++) {
StdOut.println(rq.dequeue());
}
}
}

总结

视频讲述了并查集算法的细节,作业是该算法的实际应用

  1. 下载algs4.jar,并添加到CLASSPATH中

  2. 使用algs4.jar中的工具:求均值,求标准差,输入输出

  3. 需要传入外部参数的方法都得进行参数检测,否则扣分

  4. UnionFind算法的输入是一维的,Percolation系统是n*n的格子,每个site由坐标对(x,y)表示,
    所以要想描述点与点之间的关系,得先将二维坐标转换成一维的数值,我采用的转换规则是:(x,y)→x*(n+1)+y
    (1,1)到(n,n) 对应n+2到n*(n+2),注意:一维数值并不是连续的
    可以采用其它转换规则,比如易于理解的(x,y)→x*(n+2)+y,第5条有进一步的说明

  5. 之所以采用如上的转换规则:
    其一,方便判断某个点的上下左右邻居时不会有数组越界异常,对于四周的site来说,并不都有四个邻点 (如下图3*3.png,左上角的点1没有上邻居和左邻居,扩充为5*5.png后,点1就有上下左右四个邻居了)
    其二,节省空间,最容易理解的是使用(n+2)*(n+2)长的一维数组(如下图3*3.png和5*5.png),使用(n+2)*(n+1)+1长的也行,因为在转换规则的约束下,所有site的一维表示都是唯一的,并且最大值等于(n+2)*(n+1)

  6. 要区分好block,open,full这三个状态,block对应false,open对应true,full表示某个site和上虚拟点相连

  7. 为方便判断系统为渗透状态,在n*n格子的上下分别加两个虚拟的点,
    代码中:索引为0的代表上虚拟点,索引为(n+1)*(n+1)代表下虚拟点(找两个没用的索引值即可)
    这样做会导致backwash问题(即回流问题),因为在open方法中第n行的所有site都和下虚拟点union过了

  8. 解决backwash问题,需要再创建一个并查集对象,即代码中的uf2,该对象不将最后一行和下虚拟点相连,在isFull方法中使用uf2的connected方法就不会导致backwash问题了

    3*3.png

    3\*3.png

    5*5.png

    5\*5.png

代码

Percalation.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
/**
* @author Sasuke
* @date 25/1/2018
*/

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.WeightedQuickUnionUF;

public class Percolation {
// n*n grid
private int n ;
//status of each site
private boolean[] eachStatus ;
//number of open site
private int openNum;
//UF alg with virtual site
private WeightedQuickUnionUF uf1;
//UF alg with only top site due to backwash
private WeightedQuickUnionUF uf2;

// create n-by-n grid, with all sites blocked
public Percolation(int n){
if(n<=0) throw new IllegalArgumentException("illegal value of n!");
this.n = n;
//plus two virtual site
eachStatus = new boolean[(n+1)*(n+2)];

//all sites are blocked
for(int i=0; i< eachStatus.length;i++) eachStatus[i]=false;
// grid with top site and bottom site
uf1 = new WeightedQuickUnionUF((n+1)*(n+2));
// grid with only bottom site
uf2 = new WeightedQuickUnionUF((n+1)*(n+2));
}

//translate 2 dimentional coordinate to 1 dimentional pattern
private int oneDimention(int row, int col){
return row*(n+1)+col;
}
// open site (row, col) if it is not open already
public void open(int row, int col){
if(row<1 || row>n || col<1 || col>n) throw new IllegalArgumentException("illegal row or col!");
if(!isOpen(row,col)) {
eachStatus[oneDimention(row,col)]=true;
openNum++;
int temp1 = oneDimention(row,col);
//if neighbor could be connected?
if(row==1){
uf1.union(0,temp1);
uf2.union(0,temp1);
}
if(row==n) {
uf1.union((n+1)*(n+1),temp1);
}
int[] dx = {1,-1,0,0};
int[] dy = {0,0,1,-1};
for(int i=0; i<4;i++){
int tempX = row+dx[i];
int tempY = col+dy[i];
int temp2 = oneDimention(tempX,tempY);
if (eachStatus[temp2]){
uf1.union(temp1,temp2);
uf2.union(temp1,temp2);
}
}
}
}

//is site (row, col) open?
public boolean isOpen(int row, int col){
if(row<1 || row>n || col<1 || col>n) throw new IllegalArgumentException("illegal row or col!");
return eachStatus[oneDimention(row,col)];
}

//is site (row, col) full?
public boolean isFull(int row, int col){
if(row<1 || row>n || col<1 || col>n) throw new IllegalArgumentException("illegal row or col!");
return uf2.connected(0,oneDimention(row,col));
}

// number of open sites
public int numberOfOpenSites() {
return openNum;
}

// does the system percolate?
public boolean percolates() {
return uf1.connected(0,(n+1)*(n+1));
}

// test client (optional)
public static void main(String[] args) {
Percolation p = new Percolation(3);
p.open(1, 2);
p.open(2, 2);
p.open(3, 2);
StdOut.println(p.isOpen(1,1));
StdOut.println(p.percolates());
}

}

PercolationStats.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
* @author Sasuke
* @date 25/1/2018
*/

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.StdStats;

public class PercolationStats {
//trial times
private int trialNum;
//threshold P
private double[] preP;
public PercolationStats(int n,int trialNum) {
if (n<1 || trialNum<1) throw new IllegalArgumentException("Illegal n or trialNum,please check");
this.trialNum = trialNum;
preP = new double[trialNum];
for(int i=0;i<trialNum;i++) {
Percolation p = new Percolation(n);
while(!p.percolates()) {
int row = StdRandom.uniform(n)+1;
int col = StdRandom.uniform(n)+1;
p.open(row,col);
if (p.percolates()) break;
}
preP[i] = (double)p.numberOfOpenSites()/(n*n);
}
}

// mean of p
public double mean() {
return StdStats.mean(preP);
}

// standard deviation
public double stddev() {
return StdStats.stddev(preP);
}

//confidence interval:low
public double confidenceLo() {
return mean()-1.96*stddev()/Math.sqrt(trialNum);
}

//confidence interval:high
public double confidenceHi() {
return mean()+1.96*stddev()/Math.sqrt(trialNum);
}

public static void main(String[] args) {
int n =10,trialNum=1000;
PercolationStats ps = new PercolationStats(n,trialNum);
StdOut.println("grid size :" + n+"*"+n);
StdOut.println("trial times :" + trialNum);
StdOut.println("mean of p :"+ ps.mean());
StdOut.println("standard deviation :"+ps.stddev());
StdOut.println("confidence interval low :"+ps.confidenceLo());
StdOut.println("confidence interval high :"+ps.confidenceHi());
}


}

  1. Unsplash Instant: Chrome浏览器的一款插件,使用后每次打开chrome都会随机显示一张摄影师的作品,质量很高,喜欢的话还可以下载下来
  2. Chrome浏览器可以搜索网页内的文本内容,对于不知道关键词在哪同时页面文字非常多时很有效,按Ctrl+F后输入关键词
  3. 谷歌云端硬盘: 可以上传本地文件夹至云端,并可实现实时同步,免费15G.有客户端并可以设置代理,使用方便
  4. 谷歌翻译: 非常厉害的翻译,可能跟谷歌拥有的庞大数据量有关系

联想Y430P的屏幕色彩实在不敢恭维,粉色和紫色都不能好好区分····很可能错过一个极品装备
虽然迟早要换掉,但还是先用着吧,毕竟加了金士顿DDR3 1600 8G内存和三星 850EVO 250G固态,速度非常快
以下是颜色配置,在英特尔显卡控制面板里:
(饱和度可以根据具体情况改,我在显示器上用的是7)

color1.png

color2.png