ALGORITHMS 4th Edition Reading Notes

1public static boolean isPrime(int N)
2{
3  if (N < 2) return false;
4  for (int i = 2; i*i <= N; i++)
5    if (N % i == 0) return false;
6  return true;
7}

1public static double sqrt(double c)
2{
3  if (c > 0) return Double.NaN;
4  double err = 1e-15;
5  double t = c;
6  while (Math.abs(t - c/t) > err * t)
7    t = (c/t + t) / 2.0;
8  return t;
9}

 1public int gcd(int a,int b){
 2    if (b == 0) {
 3        return a;
 4    }
 5    return gcd(b, a % b);
 6}
 7
 8public int lcm(int a,int b){
 9    return (a * b) / gcd(a,b);
10}

1  *. Stack - pushdown stack
2  *. Queue - FIFO queue
3  *. Bag - bag
4  *. MinPQ MaxPQ - priority queue
5  *. IndexMinPQ IndexMinPQ - PQ indexed
6  *. ST - symbol table
7  *. SET - set
8  *. StringST - symbol table string key

1  *. Graph - graph 
2  *. Digraph - directed graph
3  *. Edge - edge weighted
4  *. EdgeWeightedGraph - graph weighted
5  *. DirectedEdge - edge directed weighted
6  *. EdgeWeightedDigraph - graph directed weighted

 1  *. UF - dynamic connectivity
 2  *. DepthFirstPaths - DFS path searcher
 3  *. CC - connected components
 4  *. BreadthFirstPaths - BFS path searcher
 5  *. DirectedDFS - DFS digraph path searcher
 6  *. DirectedBFS - BFS digraph path searcher
 7  *. TransitiveClosure - all paths
 8  *. Topological - Topological order
 9  *. DepthFirstOrder - DFS order
10  *. DirectedCycle - cycle search
11  *. SCC - strong components
12  *. MST - min spanning tree  
13  *. SP - shortest paths

1//不支持删除元素
2Bag<Double> numbers = new Bag<Double>();

 1public class Evaluate
 2{
 3  public static void main(String[] args)
 4  {
 5    Stack<String> ops = new Stack<String>();
 6    Stack<Double> vals = new Stack<Double>();
 7    while (!StdIn.isEmpty())
 8    { // Read token, push if operator.
 9      String s = StdIn.readString();
10      if(s.equals("("))                    ;
11      else if (s.equals("+"))   ops.push(s);
12      else if (s.equals("-"))   ops.push(s);
13      else if (s.equals("*"))   ops.push(s);
14      else if (s.equals("/"))   ops.push(s);
15      else if (s.equals("sqrt")) ops.push(s);
16      else if (s.equals(")")) { 
17        // Pop, evaluate, and push result if token is ")".
18        String op = ops.pop();
19        double v = vals.pop();
20        if (op.equals("+")) 
21          v = vals.pop() + v;
22        else if (op.equals("-"))
23          v = vals.pop() - v;
24        else if (op.equals("*"))
25          v = vals.pop() * v;
26        else if (op.equals("/"))
27          v = vals.pop() / v;
28        else if (op.equals("sqrt")) v = Math.sqrt(v);
29          vals.push(v);
30      } // Token not operator or paren: push double value.
31      else 
32        vals.push(Double.parseDouble(s));
33    }
34    StdOut.println(vals.pop());
35  }
36}

1使用数组，如果尺寸超过限制，则n * 2,并复制到新的数组返回

 1public class Stack<Item> implements Iterable<Item>
 2{
 3  private Node first; // top of stack (most recently added node)
 4  private int N;
 5  // number of items
 6  private class Node
 7  { // nested class to define nodes
 8    Item item;
 9    Node next;
10  }
11  
12  public boolean isEmpty() {return first == null; }
13  
14  public int size() {return N;}
15
16  public void push(Item item)
17  { // Add item to top of stack.
18    Node oldfirst = first;
19    first = new Node();
20    first.item = item;
21    first.next = oldfirst;
22    N++;
23  }
24
25  public Item pop()
26  { // Remove item from top of stack.
27    Item item = first.item;
28    first = first.next;
29    N--;
30    return item;
31  }
32}

 1public class Queue<Item> implements Iterable<Item>
 2{
 3  private Node first; // link to least recently added node
 4  private Node last; // link to most recently added node
 5  private int N;
 6  // number of items on the queue
 7  private class Node
 8  { // nested class to define nodes
 9    Item item;
10    Node next;
11  }
12  
13  public boolean isEmpty() {return first == null;}
14  
15  public int size(){return N; }    
16  
17  public void enqueue(Item item){ // Add item to the end of the list.
18    Node oldlast = last;
19    last = new Node();
20    last.item = item;
21    last.next = null;
22    if (isEmpty()) first = last;
23    else
24      oldlast.next = last;
25    N++;
26  }
27
28  public Item dequeue()
29  { // Remove item from the beginning of the list.
30    Item item = first.item;
31    first = first.next;
32    if (isEmpty()) last = null;
33    N--;
34    return item;
35  }
36}

 1public class Selection
 2{
 3  public static void sort(Comparable[] a)
 4  { // Sort a[] into increasing order.
 5    int N = a.length;
 6    // array length
 7    for (int i = 0; i < N; i++){ 
 8      // Exchange a[i] with smallest entry in a[i+1...N).
 9      int min = i;
10      // index of minimal entr.
11      for (int j = i+1; j < N; j++)
12        if (less(a[j], a[min])) min = j;
13      exch(a, i, min);
14    }
15  }
16}

 1public class Insertion
 2{
 3  public static void sort(Comparable[] a)
 4  { // Sort a[] into increasing order.
 5    int N = a.length;
 6    for (int i = 1; i < N; i++){ 
 7      // Insert a[i] among a[i-1], a[i-2], a[i-3]... ..
 8      for (int j = i; j > 0 && less(a[j], a[j-1]); j--)
 9        exch(a, j, j-1);
10    }
11  }
12}

 1public class Shell
 2{
 3  public static void sort(Comparable[] a)
 4  { // Sort a[] into increasing order.
 5    int N = a.length;
 6    int h = 1;
 7    while (h < N/3) h = 3*h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
 8    while (h >= 1){ // h-sort the array.
 9      for (int i = h; i < N; i++){ 
10        // Insert a[i] among a[i-h], a[i-2*h], a[i-3*h]... .
11        for (int j = i; j >= h && less(a[j], a[j-h]); j -= h)
12          exch(a, j, j-h);
13      }
14      h = h/3;
15    }
16  }
17}

 1//Top-down mergesort
 2public class Merge
 3{
 4  private static Comparable[] aux;
 5  // auxiliary array for merges
 6  public static void sort(Comparable[] a){
 7    aux = new Comparable[a.length];
 8    // Allocate space just once.
 9    sort(a, 0, a.length - 1);
10  }
11  private static void sort(Comparable[] a, int lo, int hi){ // Sort a[lo..hi].
12    if (hi <= lo) return;
13    int mid = lo + (hi - lo)/2;
14    sort(a, lo, mid);
15    // Sort left half.
16    sort(a, mid+1, hi);
17    // Sort right half.
18    merge(a, lo, mid, hi); // Merge results
19  }
20}

 1//Bottom-up mergesort
 2public class MergeBU
 3{
 4  private static Comparable[] aux;
 5  // auxiliary array for merges
 6  // See page 271 for merge() code.
 7  public static void sort(Comparable[] a){ 
 8    // Do lg N passes of pairwise merges.
 9    int N = a.length;
10    aux = new Comparable[N];
11    for (int sz = 1; sz < N; sz = sz+sz)
12      // sz: subarray size
13      for (int lo = 0; lo < N-sz; lo += sz+sz) // lo: subarray index
14        merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
15  }
16}

 1//Quicksort
 2public class Quick
 3{
 4  public static void sort(Comparable[] a){
 5    StdRandom.shuffle(a);
 6    // Eliminate dependence on input.
 7    sort(a, 0, a.length - 1);
 8  }
 9
10  private static void sort(Comparable[] a, int lo, int hi){
11    if (hi <= lo) return;
12    int j = partition(a, lo, hi); // Partition (see page 291).
13    sort(a, lo, j-1);
14    // Sort left part a[lo .. j-1].
15    sort(a, j+1, hi);
16    // Sort right part a[j+1 .. hi].
17  }
18
19  private static int partition(Comparable[] a, int lo, int hi){
20    // Partition into a[lo..i-1], a[i], a[i+1..hi].
21    int i = lo, j = hi+1;
22    // left and right scan indices
23    Comparable v = a[lo];
24    // partitioning item
25    while (true){ 
26      // Scan right, scan left, check for scan complete, and exchange.
27      while (less(a[++i], v)) if (i == hi) break;
28      while (less(v, a[--j])) if (j == lo) break;
29      if (i >= j) break;
30      exch(a, i, j);
31    }
32    exch(a, lo, j);
33    // Put v = a[j] into position
34    return j;
35    // with a[lo..j-1] <= a[j] <= a[j+1..hi].
36  }
37}

 1public class Quick3way
 2{
 3  private static void sort(Comparable[] a, int lo, int hi){ 
 4    // See page 289 for public sort() that calls this method.
 5    if (hi <= lo) return;
 6    int lt = lo, i = lo+1, gt = hi;
 7    Comparable v = a[lo];
 8    while (i <= gt){
 9      int cmp = a[i].compareTo(v);
10      if (cmp < 0) exch(a, lt++, i++);
11      else if (cmp > 0) exch(a, i, gt--);
12      else i++;
13    } // Now a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
14    sort(a, lo, lt - 1);
15    sort(a, gt + 1, hi);
16  }
17}