本文共 5051 字，大约阅读时间需要 16 分钟。

前前后后提交了五次，终于拿到了满分！

总的来说，需要注意的是Timing和Backwash的问题。

Timing：PercolationStats.java里StdRandom.mean()和StdRandom.stddev()都只能调用一次；Percolation.java里实现numberOfOpenSites时切记不能使用循环累加，定义一个私有属性来计数即可；实现open()时相邻的四个sites位置直接加减n或1即可。

Backwash:实现isFull()时需要另外实例化一个不包含最下端虚拟节点的WeightedQuickUnionUF，可以解决Test 13: check for backwash with predetermined sites，Test 14: check for backwash with predetermined sites that have multiple percolating paths和Test 15: call all methods in random order until all sites are open, allowing isOpen() to be called on a site more than once三项测试无法通过的问题。

Backwash问题是指因为虚拟底部结点的存在，导致底部任一结点渗漏成功的话底部所有结点都会认为渗漏成功。原因是通过底部虚拟结点形成了回流。从而导致isFull()方法出错。

实现代码如下：

Percolation.java

import edu.princeton.cs.algs4.WeightedQuickUnionUF;public class Percolation {		private boolean[] op; // true=open while false=blocked	private int side; // number of rows or columns	private int numOp; // number of open sites	private WeightedQuickUnionUF uf;	private WeightedQuickUnionUF ufTop;	public Percolation(int n) {				if(n <= 0) throw new IllegalArgumentException("Input should be positif!\n");				this.side = n;		this.op = new boolean[n*n+2]; // with 2 virtual sites		this.uf = new WeightedQuickUnionUF(n*n+2); 		this.ufTop = new WeightedQuickUnionUF(n*n+1); // with only the upper virtual site				for(int i=1; i
   
     this.side || col < 1 || col > this.side){			throw new IllegalArgumentException("Index out of bounds!\n");		}	}		// get position of sites in 3 arrays: op, uf.parent & uf.size	private int getPosition(int row, int col){		return (row - 1) * this.side + col; 	}		private void union(int aPos, int bPos, WeightedQuickUnionUF wq){		if(!wq.connected(aPos, bPos)){			wq.union(aPos, bPos);		}	}		private boolean isOpen(int pos){		return op[pos];	}		public void open(int row, int col) {				checkBounds(row, col);			if(isOpen(row, col)) return;				int pos = getPosition(row, col);		op[pos] = true;		numOp++;				// positions of adjacent sites		int rowPrev = pos - side, rowNext = pos + side,				colPrev = pos - 1, colNext = pos + 1;				// try connect the adjacent open sites		if(row == 1){			union(0, pos, uf);			union(0, pos, ufTop);		}else if(isOpen(rowPrev)){			union(rowPrev, pos, uf);			union(rowPrev, pos, ufTop);		}						if(row == side){			union(side * side + 1, pos, uf);		}else if(isOpen(rowNext)){			union(rowNext, pos, uf);			union(rowNext, pos, ufTop);		}				if(col != 1 && isOpen(colPrev)) {			union(colPrev, pos, uf);			union(colPrev, pos, ufTop);		}				if(col != side && isOpen(colNext)) {			union(colNext, pos, uf);			union(colNext, pos, ufTop);		}	}		public boolean isOpen(int row, int col) {		checkBounds(row, col);		return isOpen(getPosition(row, col));						}		/**	 * check for backwash with predetermined sites that have multiple percolating paths	 * in this case ufTop should be used instead of uf	 * @param row	 * @param col	 * @return	 */	public boolean isFull(int row, int col) {		checkBounds(row, col);		//return uf.connected(0, getPosition(row, col)); -> didn't pass the test! 		return ufTop.connected(0, getPosition(row, col));				}		// should pass the timing check	public int numberOfOpenSites(){		return this.numOp;	}		public boolean percolates(){		return uf.connected(0, side * side + 1);	}}
   

PercolationStats.java

import edu.princeton.cs.algs4.StdIn;import edu.princeton.cs.algs4.StdOut;import edu.princeton.cs.algs4.StdRandom;import edu.princeton.cs.algs4.StdStats;import edu.princeton.cs.algs4.Stopwatch;public class PercolationStats {		private double[] results; // estimated threshold for each trial	private double avg;	private double std;		public PercolationStats(int n, int trials){				if(n <= 0 || trials <= 0) throw new IllegalArgumentException();				results = new double[trials];		for(int i = 0; i < trials; i++){			int step = 0;			Percolation pr = new Percolation(n);			while(!pr.percolates()){				int row = StdRandom.uniform(n) + 1;				int col = StdRandom.uniform(n) + 1;				if(!pr.isOpen(row, col)){					pr.open(row, col);					step++;				}			}			results[i] = (double)step / (n * n);		}				this.avg = StdStats.mean(results);		this.std = StdStats.stddev(results);			}		public static void main(String[] args){				StdOut.printf("%-25s\n", "Please input 2 integers");		int N = StdIn.readInt();		int T = StdIn.readInt();				Stopwatch wt = new Stopwatch();				PercolationStats ps = new PercolationStats(N, T);				// elapsed CPU time in seconds		double elapsed = wt.elapsedTime();				StdOut.printf("%-25s= %.15f\n", "elapsed CPU time", elapsed);		StdOut.printf("%-25s= %.7f\n", "mean", ps.mean());		StdOut.printf("%-25s= %.17f\n", "stddev", ps.stddev());		StdOut.printf("%-25s= [%.15f, %.15f]\n", "%95 confidence interval", 				ps.confidenceLo(), ps.confidenceHi());	}		public double mean(){		return this.avg;	}		public double stddev(){		return this.std;	}		public double confidenceLo(){		return mean() - 1.96 * stddev() / Math.sqrt(results.length);	}		public double confidenceHi(){		return mean() + 1.96 * stddev() / Math.sqrt(results.length);	}}

Reference: http://blog.evernightfireworks.com/princeton_algorithms_percolation/