本文主要是介绍Coursera普林斯顿大学算法课第一次作业，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
前前后后提交了五次，终于拿到了满分！
总的来说，需要注意的是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=blockedprivate int side; // number of rows or columnsprivate int numOp; // number of open sitesprivate 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 sitesthis.uf = new WeightedQuickUnionUF(n*n+2); this.ufTop = new WeightedQuickUnionUF(n*n+1); // with only the upper virtual sitefor(int i=1; i<n*n+1; i++) op[i] = false;op[0] = op[n*n+1] = true;this.numOp = 0;}// both ROW and COL should be integer within 1~nprivate void checkBounds(int row, int col){if(row < 1 || row > 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.sizeprivate 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 sitesint rowPrev = pos - side, rowNext = pos + side,colPrev = pos - 1, colNext = pos + 1;// try connect the adjacent open sitesif(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 checkpublic 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 trialprivate 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 secondsdouble 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/
这篇关于Coursera普林斯顿大学算法课第一次作业的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
