数据结构与算法第一章-Percolation

Posted on | In | | 阅读数

前言

《算法4》这本书的第一章，首先介绍的就是Java的基础知识（泛型、面向对象），同时，还有预备的数学知识，例如如何计算时间复杂度O(n)，以及预估上下界、接下来就是介绍几个基础的数据结构了，如栈、背包、队列。

这篇文章就是梳理一下书里介绍的内容，再用自己的语言表达出去。最后还有普林斯顿公开课编程大作业的思路介绍。



资源

coursera公开课视频：https://www.coursera.org/learn/algorithms-part1/home/welcome

太卡的话可能需要挂梯子。或者没有梯子的同学直接去B站看，搜名字就有了（不过这样就做不了编程作业了）

要pdf的书可以联系我，直接发云盘链接给你。搭配视频一起学习最佳。



栈

1)栈的英文为(stack)，它一个先入后出( FILO-First In Last out)的有序列表。

2)在栈中，允许插入和删除的端,为变化的一端,称为栈顶(Top),另一端为固定的一端,称为栈底( Bottom)。

3)可以把栈想象就是一个玻璃瓶子，我们要添加元素，就往瓶中塞东西，而要取元素时，就从最接近瓶口处拿。这么形容就非常贴近我们生活，以便更好的记住。

出入栈：

img


背包

背包是一种可以容纳元素的容器，可以使用add方法添加元素。

背包不支持从中删除元素的集合数据类型，不过支持遍历（取出元素是无序的），所以当我们想要找出背包其中元素时，只能foreach遍历背包，一个个找出。


先进先出队列

先进先出队列（或简称队列）是一种基于先进先出（FIFO）策略的集合类型（Queue），这个我们可以联系生活中银行办理业务的队伍来思考，先排队先处理业务——先进先出，如下图所示：

队列与栈不同的是，队列添加元素时，是往“瓶底”里面添加的。而取出时，就与栈是一样的，从瓶口取出。


链表

1)链表是以节点的方式来存储是链式存储

2)每个节点包含data域（存放的数据）, next域:指向下一个节点，当next指向null时，可以表明才链表元素是尾结点

3)链表的各个节点在内存中不一定是连续的物理存储（像数组就是连续的物理存储），但在逻辑上，他们是串联起来的

链表通过next字段实现了逻辑上的连接，它通过next域里面存储的物理存储地址找到下一个节点。



编程作业

编程作业链接：https://coursera.cs.princeton.edu/algs4/assignments/percolation/specification.php

首先：

先说说一些个人感悟吧，由于我英语不太好，把以上东西看了几遍又几遍，但总是不知其意。坐在电脑面前瞪眼。

这的确是我之前没接触过的领域，虽然我学习好了java基础，但我发现，不会写就是不会写。这时候，那可以去就复现别人的代码，先找一份别人完成了的内容，先看他的代码，然后试试看能不能理解。最后自己写出来。

主要是学习思路，而不是代码如何写。


还有，如果单纯的想要学习基本的数据结构，下面这份编程作业是不需要看的。


思路：

总体来说，这是一个物理的模型吧，从中每次打开一个格子，格子间连通的条件是： 上下左右都是“打开”状态

当最顶部和最底部发生连通时，就可以说这个模型发生渗透。

这个编程作业也提示了，可以虚拟化两个格子出来，然后判断是否连通就可以通过判断这两个格子是否是connected的来完成，就不用每次都从上到下遍历了，这么做好处显而易见，但是也有一个隐藏的坏处，就是backwish，回流。

我对backwish的理解是这样的，由于所有的底层区域都和虚拟底层区域相连，所以一旦当区域渗透，则和其他的底层开启区域相连的区域也显示为区域满状态。

解决方法：另外加一个不使用虚拟底层的模型，将两个模型结合在一起来判断是否渗透，通过浪费一些内存来保证效率。

Percolation

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
import edu.princeton.cs.algs4.WeightedQuickUnionUF;

public class Percolation {
    private final int size;
    private final WeightedQuickUnionUF uf;
    private final WeightedQuickUnionUF ufTop;
    private boolean[][] ifOpen;
    private int count = 0;


    // creates n-by-n grid, with all sites initially blocked
    public Percolation(int n) {

        if (n <= 0) throw new IllegalArgumentException("n is<=0");

        this.size = n;

        ifOpen = new boolean[n][n];

        uf = new WeightedQuickUnionUF(n * n + 2);  // 包含两个虚拟节点 （0,col）
        ufTop = new WeightedQuickUnionUF(n * n + 2);  // 包含顶部虚拟节点 （n*n,col)


        // 模型需要从1开始，到n， 所以，存放东西时需要+1
    }

    private void ifValid(int row, int col) {
        if (row < 1 || row > size || col < 1 || col > size)
            throw new IllegalArgumentException();
    }


    private int position(int row, int col) {
        // 返回传入行列在一维数组中的位置
        return (row - 1) * size + col;
    }


    // opens the site (row, col) if it is not open already
    public void open(int row, int col) {
        // 传入一个位置，如果该节点没打开，那就打开
        ifValid(row, col);

        if (!ifOpen[row - 1][col - 1]) {  // 因为模型是从1开始的，对应的开关状态应该-1
            ifOpen[row - 1][col - 1] = true;
            count++;

            int position = position(row, col);

            if (row == 1) { // 如果是第一行，直接与顶部虚拟节点相连
                uf.union(0, position);
                ufTop.union(0, position);
            }

            if (row == size) {  // 如果是最后一行，跟底部虚拟节点相连，ufTop不包含底部虚拟节点，用于判断full
                uf.union(size * size + 1, position);
            }

            if (row > 1 && ifOpen[row - 2][col - 1]) {
                // row -1 - 1 , 前一个减一代表是对应关系，再-1代表当前节点的前一个元素
                uf.union(position, position - size);  // position - size = 减去一行(也就是上个节点状态)
                ufTop.union(position, position - size);
            }

            if (row < size && ifOpen[row][col - 1]) {  // row = row -1 + 1，表示下一个节点
                uf.union(position, position + size);
                ufTop.union(position, position + size);
            }

            if (col > 1 && ifOpen[row - 1][col - 2]) {
                uf.union(position, position - 1);
                ufTop.union(position, position - 1);
            }

            if (col > size && ifOpen[row - 1][col]) {
                uf.union(position, position + 1);
                ufTop.union(position, position + 1);
            }

        }
    }


    // is the site (row, col) open?
    public boolean isOpen(int row, int col) {
        ifValid(row, col);
        // 判断一个节点是否打开
        return ifOpen[row - 1][col - 1];
    }

    // is the site (row, col) full?
    public boolean isFull(int row, int col) {
        // 判断该点是否变成蓝色格子
        ifValid(row, col);

        return (ufTop.connected(position(row, col), 0) && !ifOpen[row - 1][col - 1]);
    }

    // returns the number of open sites
    public int numberOfOpenSites() {
        return count;
    }

    // does the system percolate?
    public boolean percolates() {
        // 判断该模型是否渗透
        return uf.connected(0, size * size + 1);
    }
}

PercolationStats

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
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.StdStats;

public class PercolationStats {
    private final double meanVal;
    private final double stdVal;
    private final double halfInterval;  // 1.96s / 根号T 的值


    // perform independent trials on an n-by-n grid

    /**
     * @param n      模型的大小
     * @param trials 做实验的总次数
     */
    public PercolationStats(int n, int trials) {
        if (n <= 0 || trials <= 0)
            throw new IllegalArgumentException();

        double[] results = new double[trials];  // 用于存放每一次实验结果的数组

        for (int i = 0; i < trials; i++) {

            Percolation percolation = new Percolation(n);
            while (!percolation.percolates()) {
                // 如果还没渗透，就一直打开格子
                int sizePos = StdRandom.uniform(n * n) + 1;
                int row, col;

                if (sizePos % n == 0) {  // 如果刚好是n的倍数，证明在最后一列
                    row = sizePos / n;
                    col = n;
                } else {
                    row = sizePos / n + 1;
                    col = sizePos % n;
                }

                percolation.open(row, col);

            }
            // 当满足渗透时，跳出循环
            double nums = n * n;
            results[i] = percolation.numberOfOpenSites() / nums;  // 打开的格子占总数的多少

        }

        // 实验完毕后，计算结果
        meanVal = StdStats.mean(results);
        stdVal = StdStats.stddev(results);
        halfInterval = 1.96 * stdVal / Math.sqrt(trials);

    }

    // sample mean of percolation threshold
    public double mean() {
        return meanVal;
    }

    // sample standard deviation of percolation threshold
    public double stddev() {
        return stdVal;
    }


    // low endpoint of 95% confidence interval
    public double confidenceLo() {
        return meanVal - halfInterval;
    }


    // high endpoint of 95% confidence interval
    public double confidenceHi() {
        return meanVal + halfInterval;
    }

    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        int times = Integer.parseInt(args[1]);
        PercolationStats percolationStats = new PercolationStats(n, times);

        double mean = percolationStats.mean();
        double stddev = percolationStats.stddev();

        double conLow = percolationStats.confidenceLo();
        double conHight = percolationStats.confidenceHi();

        StdOut.printf("mean%20s= %f\n", " ", mean);
        StdOut.printf("stddev%18s= %f\n", " ", stddev);
        StdOut.printf("95%% confidence interval = [%f, %f]", conLow, conHight);

    }

}