Algorithms4 《算法》第四版 内容整理第一章干货

    int[] a =new int[N];
    ...
    a[i] = 1234;
    ...
    int[] b = a;
    ...
    b[i] = 5678//a[i]的值也会编程5678

    public static int rank(int key, int[] a)
    { return rank(key, a, 0, a.length - 1); }
    public static int rank(int key, int[] a, int lo, int hi)
    {//如果key存在于a[]中，它的索引不会小于lo且不会大于hi
      if(lo > hi) return -1;
      int mid = lo + (hi - lo) / 2;
      if(key < a[mid]) return rank(key, a, lo, mid -1 );
      else if(key > a[mid]) return rank(key, a, mid + 1, hi);
      else return mid;
    }

    public interface Datable
    {
      int month();
      int day();
      int year();
    }
    public class Date implements Datable
    {
      //实现代码
    }

    public class Vector
    {
      private final double[] coords;
      public Vector(double[] a)
      {
    coords = a;
      }
      ...
    }
    用例程序可以通过给定的数组创建一个Vector对象，并在构造对象执行之后改变Vector中的元素的值：
    double[] a = {3.0, 4.0};
    Vector vector = new Vector(a);
    a[0] = 0.0;//绕过 了公有API

    public ckass Stats
    {
      public static void main(String[] args)
      {
    Bag<Double> numbers = new Bag<Double>();
    while(!StdIn.isEmpty())
        numbers.add(StdIn.readDouble());
    int N = numbers.size();
    double sum = 0.0;
    for (double x : numbers)
        sum += x;
    double mean = sum/N;
    sum = 0.0;
    for(double x : numbers)
        sum +=(x - mean)*(x - mean);
    double std = Math.sqrt(sum/(N-1));
    StdOut.printf("Mean: %.2f\n", mean);
    StdOut.printf("Std dev: %.2f\n", std);
      }
    }

    In类的静态方法readInts()的一种实现，该方法解决的问题：用例无需预先知道文件的大小即可将文件中的所有整数读入一个数组中。

    public static int[] readInts(String name)
    {
    In in = new In(name);
    Queue<Integer> q = new Queue<Integer>();
    while (!in.isEmpty())
    q.enqueue(in.readInt());
    int N = q.size();
    int [] a = new int[N];
    for (int i = 0; i < N; i++)
    a[i] = q.dequeue();
    return a;
    }

    把标准输入中的所有整数逆序排列，无需预先知道整数的多少。

    public class Reverse
    {
    public static void main(String[] args)
    {
      Stack<Integer> stack;
      stack = new Stack<Integer>();
      while(!StdIn.isEmpty())
      stack.push(StdIn.readInt());
      for (int i : stack)
      StdOut.println(i);
    }
    }

    import java.util.Iterator;

    public class ResizingArrayStack<Item> implements Iterable<Item>
    {
    private Item[] a = (Item[]) new Object[1];//栈元素。java不允许创建泛型数组，因此需要使用类型转换
    private int N = 0;//元素数量
    public boolean isEmpty() {return N == 0;}
    public int size() {return N;}
    private void resize(int max)
    {//由于java数组创建后无法改变大小，采用创建大小为max的新数组来替代旧数组的方式动态改变数组实际大小
      Item[] temp = (Item[]) new Object[max];
      for (int i = 0;i < N; i++)
      temp[i] = a[i];
      a = temp;
    }
    public void push(Item item)
    {//将元素添加到栈顶
      if (N == a.length) resize(2*a.length);
      a[N++] = item;
    }
    public Item pop()
    {//从栈顶删除元素
      Item item = a[--N];
      a[N] = null;//避免对象游离
      if (N > 0 && N == a.length/4) resize(a.length/2);
      return item;
    }
    public Iterator<Item> iterator()
    { return new ReverseArrayIterator(); }
    private class ReverseArrayIterator implements Iterator<Item>
    {//支持后进先出的迭代
      private int i = N;
      public boolean hasNext() { return i > 0;}
      public Item next() { return a[--i];}
      public void remove() { }
    }
    }

    private class Node//在需要使用Node类的类中定义它并将它标记为private，因为它不是为用例准备的。

    {
    Item item;
    Node next;
    }

* 设置next域来构造链表：   

* 链表表示的是一列元素。

* 在表尾插入结点   

    public class Stack<Item> implements Iterable<Item>

    {
    private Node first;//栈顶（最近添加的元素）
    private int N;
    private class Node
    {//定义了结点的嵌套类
      Item item;
      Node next;
    }
    public boolean isEmpty() {return N == 0;}//或：return first == null;
    public int size() {return N;}
    public void push(Item item)
    {//向栈顶添加元素
      Node oldfirst = first;
      first = new Node();
      first.item = item;
      first.next = oldfirst;
      N++;
    }
    public Item pop()
    {
      Item item = first.item;
      first = first.next;
      N--;
      return item;
    }
    //iterator()的实现见背包实现算法
    public static void main(String[] args)
    {//输入to be or not to - be - - that - - - is
      Stack<String> s = new Stack<String>();
      while(!StdIn.isEmpty())
      {
    String item = StdIn.readString();
    if(!item.equals("-"))
        s.push(item);
    else if(!s.isEmpty()) StdOut.print(s.pop() + " ");
      }
      StdOut.println("(" + s.size() + " left on stack)");
    }
    }

    public class Queue<Item> implements Iterable<Item>

    {
    private Node first;
    private Node last;
    private int N;
    private class Node
    {
      Item item;
      Node next;
    }
    public boolean isEmpty() {return N == 0;}//或：return first == null;
    public int size() {return N;}
    public void enqueue(Item item)
    {//向表尾添加元素
      Node oldfirst = last;
      last = new Node();
      last.item = item;
      last.next = null;
      if (isEmpty()) first = last;
      else oldfirst.next = last;
      N++;
    }
    public Item dequeue()
    {//从表头删除元素
      Item item = first.item;
      first = first.next;
      if (isEmpty()) last = null;
      N--;
      return item;
    }
    //
    public static void main(String[] args)
    {//输入to be or not to - be - - that - - - is
      Queue<String> s = new Queue<String>();
      while(!StdIn.isEmpty())
      {
    String item = StdIn.readString();
    if(!item.equals("-"))
        q.enqueue(item);
    else if(!q.isEmpty()) StdOut.print(q.dequeue() + " ");
      }
      StdOut.println("(" + q.size() + " left on queue)");
    }
    }

    import java.util.Iterator;

    public class Bag<Item> implements Iterable<Item>
    {
    private Node first;
    private class Node
    {
      Item item;
      Node next;
    }
    public void add(Item item)
    {
      Node oldfirst = first;
      first = new Node();
      first.item = item;
      first.next = oldfirst;
    }
    //通过遍历链表使Stack、Queue、Bag变为可迭代的。对于Stack，链表的访问顺序是后进先出；Queue，链表的访问顺序是先进先出；Bag，后进先出顺序，但顺序不重要。
    public Iterator<Item> iterator()
    { return new ListIterator();}
    private class ListIterator implements Iterator<Item>
    {
      private Node current = first;
      public boolean hasNext()
      { return current != null;}
      public void remove() { }
      public Item next()
      {
    Item item = current.item;
    current = current.next;
    return item;
      }
    }
    }

    import java.util.Arrays;
    public class ThreeSumFast
    {
      public static int cout(int[] a)
      {
    Arrays.sort(a);
    int N = a.length;
    int cnt = 0;
    for (int i = 0; i< N; i++)
        for(int j = i + 1;j < N; j++)
            if (BinarySearch.rank(-a[i]-a[j], a) > j)
                cnt++;
    return cnt;
      }
    }

    public int find(int p)

    { return id[p]; }
    public void union(int p, int q)
    {//将p和q归并到相同的分量中
    int pID = find(p);
    int qID = find(q);
    
    //如果p和q已经在相同的分量之中则不需要采取任何行动
    if (pID == qID) return;
    
    //将p的分量重命名为q的名称
    for (int i = 0;i < id.length; i++)
    if (id[i] == pID) id[i] = qID;
    count--;
    }

    private int find(int p)

    {//找出分量的名称
    while(p != id[p]) p = id[p];
    return p;
    }
    public void union(int p, int q)
    {//将p和q的根节点统一
    int pRoot = find(p);
    int qRoot = find(q);
    if (pRoot == qRoot) return;
    id[pRoot] = qRoot;
    count--;
    }

    public class UF
    {
      private int[] id;//父链接数组（由触点索引）
      private int[] sz;//（有触点索引的）各个根节点所对应的分量的大小
      private int count; //连通分量的数量
      public WeightedQuickUnionUF(int N)
      {
    count = N;
    id = new int[N];
    for(int i=0;i < N;i++)
      id[i] = i;
    sz = new int[N];
    for(int i = 0; i < N; i++) sz[i] = 1;
      }
      public int count()
      { return count;}
      public boolean connected(int p, int q)
      { renturn find(p) == find(q); }
      public int find(int p)
      {//跟随链接找到根节点
    while(p != id[p]) p = id[p];
    return p;
      }
      public void union(int p, int q)
      {
    int i = find(p);
    int j = find(q);
    if(i == j) return;
    //将小树的根节点连接到大树的根节点
    if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i];}
    else{id[j] = i;sz[i] += sz[j];}
    count--;
      }
    }