import edu.princeton.cs.algs4.StdRandom; //导入依赖的package包/类
/**
 * Ex 1.4.17
 * Farthest Pair
 * O(N)
 * @param n
 *		数组的元素个数
 */
private static void farthestPair(int n) {
    //创建并打乱数组
    double[] a = new double[n];

    for (int i = 0; i < n; i++)
        a[i] = i;

    StdRandom.shuffle(a);

    double min = a[0];
    double max = a[0];

    for (int i = 0; i < n; i++) {
        //找出最小的数
        min = Math.min(a[i], min);
        max = Math.max(a[i], max);
    }

    o("相差最大的两个数分别是: " + min + ", "+ max);

}
 

import edu.princeton.cs.algs4.StdRandom; //导入依赖的package包/类
/**
* return (but do not remove) a random item
*/
public Item sample() {
	if (size() == 0)
		throw new NoSuchElementException("");

	//generate the random index that will be dequeued.
	int outIndex = StdRandom.uniform(size);

	Node tmp = last;
	Node tmpNext = null;

	for (int i = 0; i < outIndex; i++) {
		tmpNext = tmp;
		tmp = tmp.previous;
	}

	return tmp.item;
}
 

import edu.princeton.cs.algs4.StdRandom; //导入依赖的package包/类
/**
* perform trials independent experiments on an n-by-n grid
* @param n
*          grid的大小
* @param trials
*          尝试trials次试验
*/
public PercolationStats(int n, int trials) {
    //检验参数合法性
    if (n <= 0 || trials <= 0)
        throw new IllegalArgumentException("参数不能小于等于0!");

    results = new double[trials];

    for(int i = 0;i < trials;i++) {
        Percolation percolationTest = new Percolation(n);

        int rndRow, rndCol;
        while (!percolationTest.percolates()) {
            if(percolationTest.isOpen(rndRow = (StdRandom.uniform(n) + 1), rndCol = (StdRandom.uniform(n) + 1)))
                continue;
            else
                percolationTest.open(rndRow, rndCol);
        }
        results[i] = (percolationTest.numberOfOpenSites() * 1.0) / (n * n);
    }

    mean = StdStats.mean(results);
    stddev = StdStats.stddev(results);
}
 

import edu.princeton.cs.algs4.StdRandom; //导入依赖的package包/类
/**
* Ex 2.3.17
* Sentinels
* 使用哨兵减少冗余的if判断
* @param a
*       要排序的数组
*/
@SuppressWarnings("unchecked")
private static void quickSortWithSentinels(Comparable[] a) {
    //把a打乱
    StdRandom.shuffle(a);

    //找到最大的item并且交换到a[length - 1]
    //sentinel2
    int indexOfMax = 0;
    for (int i = 1; i < a.length; i++)
        if (a[i].compareTo(a[indexOfMax]) > 0)
            indexOfMax = i;
    exch(a, indexOfMax, a.length - 1);

    quickSortWithSentinels(a, 0, a.length - 1);
}
 

import edu.princeton.cs.algs4.StdRandom; //导入依赖的package包/类
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++) {
        Percolation percolation = new Percolation(n);
        while (!percolation.percolates()) {
            int row = StdRandom.uniform(1, n + 1);
            int col = StdRandom.uniform(1, n + 1);
            if (!percolation.isOpen(row, col)) percolation.open(row, col);
        }

        int openSites = percolation.numberOfOpenSites();
        results[i] = (double) openSites / (double) (n * n);

    }

    mean = StdStats.mean(results);
    stddev = StdStats.stddev(results);
}
 

import edu.princeton.cs.algs4.StdRandom; //导入依赖的package包/类
public static void main(String[] args) {
    Exercise20_DynamicGrowth dynamicGrowth = new Exercise20_DynamicGrowth();

    DynamicWeightedQuickUnion dynamicWeightedQuickUnion = dynamicGrowth.new DynamicWeightedQuickUnion();

    //Add five sites
    dynamicWeightedQuickUnion.newSite();
    dynamicWeightedQuickUnion.newSite();
    dynamicWeightedQuickUnion.newSite();
    dynamicWeightedQuickUnion.newSite();
    dynamicWeightedQuickUnion.newSite();


    while(dynamicWeightedQuickUnion.count() != 1) {

        int randomSite1 = StdRandom.uniform(dynamicWeightedQuickUnion.getNumberOfSites());
        int randomSite2 = StdRandom.uniform(dynamicWeightedQuickUnion.getNumberOfSites());

        if(!dynamicWeightedQuickUnion.connected(randomSite1, randomSite2)) {
            dynamicWeightedQuickUnion.union(randomSite1, randomSite2);

            StdOut.println("United sites " + randomSite1 + " and " + randomSite2);
        }
    }
}
 

import edu.princeton.cs.algs4.StdRandom; //导入依赖的package包/类
/**
 * Returns a random simple graph containing <tt>V</tt> vertices and <tt>E</tt> edges.
 * @param V the number of vertices
 * @param E the number of vertices
 * @return a random simple graph on <tt>V</tt> vertices, containing a total
 *     of <tt>E</tt> edges
 * @throws IllegalArgumentException if no such simple graph exists
 */
public static Graph simple(int V, int E) {
    if (E > (long) V*(V-1)/2) throw new IllegalArgumentException("Too many edges");
    if (E < 0)                throw new IllegalArgumentException("Too few edges");
    Graph G = new Graph(V);
    SET<Edge> set = new SET<Edge>();
    while (G.E() < E) {
        int v = StdRandom.uniform(V);
        int w = StdRandom.uniform(V);
        Edge e = new Edge(v, w);
        if ((v != w) && !set.contains(e)) {
            set.add(e);
            G.addEdge(v, w);
        }
    }
    return G;
}
 

import edu.princeton.cs.algs4.StdRandom; //导入依赖的package包/类
private Exercise21_ComparableTransactions[] generateRandomTransactions(int numberOfObjects) {
    Exercise21_ComparableTransactions[] transactions = new Exercise21_ComparableTransactions[numberOfObjects];

    for(int i=0; i < numberOfObjects; i++) {
        String who = "Client " + (i + 1);

        int month = StdRandom.uniform(12) + 1;
        int maxDay = month == 2 ? 28 : 30;
        int day = StdRandom.uniform(maxDay) + 1;
        int year = StdRandom.uniform(1900, 2018);
        Date date = new Date(month, day, year);

        double amount = (double) Math.round(StdRandom.uniform(0.0, 1000000.0) * 100) / 100;

        Exercise21_ComparableTransactions transaction = new Exercise21_ComparableTransactions(who, date, amount);
        transactions[i] = transaction;
    }

    return transactions;
}
 

import edu.princeton.cs.algs4.StdRandom; //导入依赖的package包/类
/**
 * Returns an Eulerian cycle graph on <tt>V</tt> vertices.
 *
 * @param  V the number of vertices in the cycle
 * @param  E the number of edges in the cycle
 * @return a graph that is an Eulerian cycle on <tt>V</tt> vertices
 *         and <tt>E</tt> edges
 * @throws IllegalArgumentException if either V &le; 0 or E &le; 0
 */
public static Graph eulerianCycle(int V, int E) {
    if (E <= 0)
        throw new IllegalArgumentException("An Eulerian cycle must have at least one edge");
    if (V <= 0)
        throw new IllegalArgumentException("An Eulerian cycle must have at least one vertex");
    Graph G = new Graph(V);
    int[] vertices = new int[E];
    for (int i = 0; i < E; i++)
        vertices[i] = StdRandom.uniform(V);
    for (int i = 0; i < E-1; i++) {
        G.addEdge(vertices[i], vertices[i+1]);
    }
    G.addEdge(vertices[E-1], vertices[0]);
    return G;
}
 

import edu.princeton.cs.algs4.StdRandom; //导入依赖的package包/类
/**
 * Returns a wheel graph on <tt>V</tt> vertices.
 * @param V the number of vertices in the wheel
 * @return a wheel graph on <tt>V</tt> vertices: a single vertex connected to
 *     every vertex in a cycle on <tt>V-1</tt> vertices
 */
public static Graph wheel(int V) {
    if (V <= 1) throw new IllegalArgumentException("Number of vertices must be at least 2");
    Graph G = new Graph(V);
    int[] vertices = new int[V];
    for (int i = 0; i < V; i++)
        vertices[i] = i;
    StdRandom.shuffle(vertices);

    // simple cycle on V-1 vertices
    for (int i = 1; i < V-1; i++) {
        G.addEdge(vertices[i], vertices[i+1]);
    }
    G.addEdge(vertices[V-1], vertices[1]);

    // connect vertices[0] to every vertex on cycle
    for (int i = 1; i < V; i++) {
        G.addEdge(vertices[0], vertices[i]);
    }

    return G;
}
 

import edu.princeton.cs.algs4.StdRandom; //导入依赖的package包/类
private static int insertsAndRemovesIn1Second(PriorityQueue<Double> priorityQueue, Comparable[] keys) {
    //Fill the priority queue
    for(int i=0; i < keys.length; i++) {
        priorityQueue.insert((double) keys[i]);
    }

    int numberOfRemoveMaxIn1Second = 0;
    int randomIndex = StdRandom.uniform(keys.length);

    Stopwatch timer = new Stopwatch();
    while (timer.elapsedTime() <= 1) {
        priorityQueue.deleteTop();
        numberOfRemoveMaxIn1Second++;
        priorityQueue.insert((double) keys[randomIndex]);
    }

    return numberOfRemoveMaxIn1Second;
}
 

import edu.princeton.cs.algs4.StdRandom; //导入依赖的package包/类
/**
 * Returns a uniformly random <tt>k</tt>-regular graph on <tt>V</tt> vertices
 * (not necessarily simple). The graph is simple with probability only about e^(-k^2/4),
 * which is tiny when k = 14.
 * @param V the number of vertices in the graph
 * @return a uniformly random <tt>k</tt>-regular graph on <tt>V</tt> vertices.
 */
public static Graph regular(int V, int k) {
    if (V*k % 2 != 0) throw new IllegalArgumentException("Number of vertices * k must be even");
    Graph G = new Graph(V);

    // create k copies of each vertex
    int[] vertices = new int[V*k];
    for (int v = 0; v < V; v++) {
        for (int j = 0; j < k; j++) {
            vertices[v + V*j] = v;
        }
    }

    // pick a random perfect matching
    StdRandom.shuffle(vertices);
    for (int i = 0; i < V*k/2; i++) {
        G.addEdge(vertices[2*i], vertices[2*i + 1]);
    }
    return G;
}
 

import edu.princeton.cs.algs4.StdRandom; //导入依赖的package包/类
private List<Exercise18_RandomGridGenerator.Connection> erdosRenyiGeneratingConnections(int numberOfSites, UF unionFind) {

        List<Exercise18_RandomGridGenerator.Connection> connectionsGenerated = new ArrayList<>();

        while(unionFind.count() != 1) {

            int randomSite1 = StdRandom.uniform(numberOfSites);
            int randomSite2 = StdRandom.uniform(numberOfSites);

            Exercise18_RandomGridGenerator.Connection connection = new Exercise18_RandomGridGenerator().new Connection(
                    randomSite1, randomSite2);
            connectionsGenerated.add(connection);

            if(!unionFind.connected(randomSite1, randomSite2)) {
                unionFind.union(randomSite1, randomSite2);
            }
        }

        return connectionsGenerated;
    }
 

import edu.princeton.cs.algs4.StdRandom; //导入依赖的package包/类
public EdgeWeightedGraphWithNeighborsInOrder generateWorstCaseGraphForEagerPrim(int vertices) {
    EdgeWeightedGraphWithNeighborsInOrder edgeWeightedGraph = new EdgeWeightedGraphWithNeighborsInOrder(vertices);

    double maxWeight = StdRandom.uniform();
    double valueToDecrease = 0.00001;

    for(int vertex1 = 0; vertex1 < vertices; vertex1++) {
        valueToDecrease = valueToDecrease + 0.00001;

        for(int vertex2 = vertex1 + 1; vertex2 < vertices; vertex2++) {
            double weight = maxWeight - valueToDecrease;
            Edge edge = new Edge(vertex1, vertex2, weight);
            edgeWeightedGraph.addEdge(edge);
        }
    }

    return edgeWeightedGraph;
}
 

import edu.princeton.cs.algs4.StdRandom; //导入依赖的package包/类
public Exercise28_SpaceEfficientDataStructures.EdgeWeightedGraphSpaceEfficient erdosRenyiGraphUniformWeights(int vertices,
                                                                                                             int edges) {
    Exercise28_SpaceEfficientDataStructures.EdgeWeightedGraphSpaceEfficient randomEdgeWeightedGraphSpaceEfficient =
            spaceEfficientDataStructures.new EdgeWeightedGraphSpaceEfficient(vertices);

    for(int edge = 0; edge < edges; edge++) {
        int vertexId1 = StdRandom.uniform(vertices);
        int vertexId2 = StdRandom.uniform(vertices);

        double uniformRandomWeight = StdRandom.uniform();
        Edge newEdge = new Edge(vertexId1, vertexId2, uniformRandomWeight);

        randomEdgeWeightedGraphSpaceEfficient.addEdge(newEdge);
    }

    return randomEdgeWeightedGraphSpaceEfficient;
}
 

import edu.princeton.cs.algs4.StdRandom; //导入依赖的package包/类
public Exercise28_SpaceEfficientDataStructures.EdgeWeightedGraphSpaceEfficient erdosRenyiGraphGaussianWeights(int vertices,
                                                                                                              int edges) {
    Exercise28_SpaceEfficientDataStructures.EdgeWeightedGraphSpaceEfficient randomEdgeWeightedGraphSpaceEfficient =
            spaceEfficientDataStructures.new EdgeWeightedGraphSpaceEfficient(vertices);

    for(int edge = 0; edge < edges; edge++) {
        int vertexId1 = StdRandom.uniform(vertices);
        int vertexId2 = StdRandom.uniform(vertices);

        double gaussianRandomWeight = StdRandom.gaussian();
        Edge newEdge = new Edge(vertexId1, vertexId2, gaussianRandomWeight);

        randomEdgeWeightedGraphSpaceEfficient.addEdge(newEdge);
    }

    return randomEdgeWeightedGraphSpaceEfficient;
}
 

import edu.princeton.cs.algs4.StdRandom; //导入依赖的package包/类
private static double timeRandomInput(SortTypes sortType, int initialLength, int numberOfExperiments) {
    double total = 0;
    int length = initialLength;

    for(int experiment = 0; experiment < numberOfExperiments; experiment++) {
        Comparable[] array = new Comparable[length];

        for(int i=0; i < length; i++) {
            array[i] = StdRandom.uniform();
        }

        total += time(sortType, array);

        length *= 2;
    }

    return total;
}
 

import edu.princeton.cs.algs4.StdRandom; //导入依赖的package包/类
private Coordinate[] getRandomCoordinates(EdgeWeightedGraph edgeWeightedGraph) {
            Coordinate[] vertexCoordinates = new Coordinate[edgeWeightedGraph.vertices()];

            for(int vertex = 0; vertex < edgeWeightedGraph.vertices(); vertex++) {
                // tinyEWG coordinates
//                double randomXCoordinate = StdRandom.uniform();
//                double randomYCoordinate = StdRandom.uniform();

                double randomXCoordinate = StdRandom.uniform(1000);
                double randomYCoordinate = StdRandom.uniform(1000);

                vertexCoordinates[vertex] = new Coordinate(randomXCoordinate, randomYCoordinate);
            }

            return vertexCoordinates;
        }
 

import edu.princeton.cs.algs4.StdRandom; //导入依赖的package包/类
private void connectVerticesToNeighbors(Exercise30_EuclideanWeightedGraphs.EuclideanEdgeWeightedGraph randomEuclideanGridEdgeWeightedGraph,
                                        int vertexNumberSqrt) {
    int[] neighborRows = {-1, 1, 0 ,0};
    int[] neighborColumns = {0, 0, -1 ,1};

    for(int row = 0; row < vertexNumberSqrt; row++) {
        for(int column = 0; column < vertexNumberSqrt; column++) {
            for(int i = 0; i < 4; i++) {
                int neighborRow = row + neighborRows[i];
                int neighborColumn = column + neighborColumns[i];

                if(isValidCell(vertexNumberSqrt, neighborRow, neighborColumn)) {
                    int vertexId1 = getVertexId(row, column, vertexNumberSqrt);
                    int vertexId2 = getVertexId(neighborRow, neighborColumn, vertexNumberSqrt);

                    //Used to avoid connecting vertices more than once
                    if(vertexId1 < vertexId2) {
                        double randomEdgeWeight = StdRandom.uniform();
                        Edge edge = new Edge(vertexId1, vertexId2, randomEdgeWeight);
                        randomEuclideanGridEdgeWeightedGraph.addEdge(edge);
                    }
                }
            }
        }
    }
}
 

import edu.princeton.cs.algs4.StdRandom; //导入依赖的package包/类
private static Comparable[] generate95PercentSortedArray(int arrayLength) {

        Comparable[] array = new Comparable[arrayLength];

        int fivePercentLength = (int) (arrayLength * 0.05);

        for(int i=0; i < arrayLength; i++) {
            array[i] = i;
        }

        //Shuffle 5% of values
        for(int i=0; i <= fivePercentLength / 2; i++) {
            int randomIndex1 = StdRandom.uniform(0, arrayLength);
            int randomIndex2 = StdRandom.uniform(0, arrayLength);

            Comparable temp = array[randomIndex1];
            array[randomIndex1] = array[randomIndex2];
            array[randomIndex2] = temp;
        }

        return array;
    }