编写递归代码最重要有以下三点： - 递归总有一个最简单的情况——方法的第一条语句总是一个包含return 的条件语句。 - 递归调用总是尝试去解决一个规模更小的子问题，这样递归才能收敛到最简单的情况 - 递归调用的父问题 和 尝试解决的 子问题之间 不应该有交集。
API的目的是将调用和实现分离：除了API中给出的信息，调用者不需要知道实现的其他细节，而实现也不应考虑特殊的应用场景。 - 程序员可以将API看做调用和实现之间的一份契约，它详细说明了每个方法的作用。实现的目标就是能够遵守这份契约。
在我们的模型中，Java程序可以从命令行参数或者一个名为标准输入流的抽象字符流中获得输入，并将输出写入另一个为标准输出流的字符流中。
标准输入流最重要的特点是这些值会在你的程序读取之后消失。只要程序读取一个值，它就不能回退并再次读取它。
定理：a,b 是整数，则gcd(a, b) = gcd(b,a mod b)
设k，r为整数。设r = a mod b ,则a可表示为 a = r + k*b
假设d 是{a,b}的公约数，则d整除a，b。而r = a - k*b; 所以d整除r， d也是b和r的公约数。假设d 是{b,r}的公约数，则d整除b，r。而a = r + k*b 所以d也是a，b的公约数。所以{a，b}，{b, r}的公因子集合是一样的。特别地{a,b}的最大公因子也是{b,r}的最大公因子。即 gcd(a, b) = gcd(b,a mod b)数据类型指的是一组值和一组对这些值的操作的集合。 - Java编程的基础主要是使用class关键字构造被称为 引用类型 的数据类型。 - 抽象数据类型（ADT）是一种能够对使用者隐藏数据表示的数据类型。
同一份api的不同实现。 通常采用一种非正式的命名约定 - 通过前缀性修饰符区别同一份API的不同实现 - 维护一个没有前缀的参考实现，它应该适合于大多数用例的需求。
抽象数据类型是一种向用例隐藏内部表示的数据类型。
我们提倡的编程风格：将大型程序分解为能够独立开发和调试的小型模块（也促进了代码复用）。
Java系统的新实现往往更新了多种数据类型的或静态方法库的实现，但它们的API并没有变化。
equals 模板
@Override public boolean equals(Object obj) { //如果引用相同，直接返回true 不需要其他测试工作 if (this == obj) { return true; } //对象为空直接返回false if (obj == null) { return false; } //两个对象的类不同 if (obj.getClass() != this.getClass()) { return false; }// //书上没这么用，还是直接getClass比较好// if (!(obj instanceof Date)) {// return false;// } //强制类型 Date that = (Date)obj; if (that.day != day) { return false; } if (that.year != year) { return false; } if (that.mon != mon) { return false; } return true; }契约式设计的编程模型采用的就是断言的思想。 - 数据类型的设计者需要说明前提条件（调用某个方法需要满足的条件，如：二分查找需要满足有序） - 后置条件（实现在方法返回时必须达到的要求） - 副作用（方法可能对对象状态产生的任何变更）
要保证含有一个可变的实例变量的数据类型的不可变性，需要得到一个本地副本，称为保护性复制。
背包是一种不支持从中删除的集合数据类型——它的目的是帮助用例收集元素并迭代遍历所有收集到的元素。（当然可以检查背包是否为空或者获取其中的数量的功能还是有的）。
入队列和出队列的顺序
使用Collection类的Iterator，可以方便的遍历Vector, ArrayList, LinkedList等集合元素，避免通过get()方法遍历时，针对每一种对象单独进行编码。
迭代器模式
参考 - Java目前还不支持创建 泛型数组。因为java的泛型是擦除实现
List<String>[] l = new ArrayList<String>[10];//错误List<String>[] l = (ArrayList<String>[] )new Object[10];Item[] a = (Item[]) new Object[N];//正确以栈为栗子： - push()中，检查数组是否太小，如果没有多余的空间，就将数组的长度加倍。
if(N == a.length){ resize(a.length * 2);}pop()中， 首先删除栈顶元素。然后数组太大就将它的长度减半。 检测条件为栈的大小是否小于数组的四分之一。 Item item = a[--N];a[N] = null;//防止游离if(N > 0 && N == a.length / 4){ // 另一条件N > 0 勿忘 resize(a.length / 2);}return item;调整数组的函数实现
PRivate void resize(int size){ Item[] tmp = (Item[]) new Object[size]; for(int i = 0 ; i < N; i++){ tmp[i] = a[i]; } a = tmp;}用数组实现的栈的栗子： - 对pop的实现中，被弹出的元素的引用仍然在数组中，应该将其置为null。
任意可迭代的集合数据类型需要实现的东西 1. 通过实现Iterable接口 - 实现iterator方法,返回Iterator 2. 定义一个实现了Iterator接口的 嵌套内部类 - 实现 hasNext方法 - 实现 next方法 - remove方法可以放空，或者抛异常
数组实现的迭代 栗子：
@Overridepublic Iterator<Item> iterator() { return new ReverseArrayIterator();}private class ReverseArrayIterator<Item> implements Iterator<Item>{ private int i = N; @Override public boolean hasNext() { return i > 0; } @Override public Item next() { return (Item) a[--i]; } public void remove(){ }}链表实现的迭代栗子：
private class Itr implements Iterator<Item> { Node current = first; @Override public boolean hasNext() { return current != null; } @Override public Item next() { Item i = current.item; current = current.next; return i; } @Override public void remove() { }}定义：链表是一种递归的数据结构，或者为空，或者是一个指向一个结点的引用，该结点含有一个泛型元素和一个指向另一条链表的引用。
在研究一个新的应用领域的时，我们将会按照以下步骤识别目标并使用数据结构对象解决问题。 1. 定义API。 2. 根据特定的应用场景开发用例代码，先确定客户怎么使用（跟以往的思路有些不同） 3. 描述一种数据结构。（一组值的表示）， 并在API所对应的抽象数据类型的实现中根据它定义类的实例变量。 4. 描述算法（实现一组操作方式），并根据它实现类中的实例方法 5. 分析算法的性能优点。
时间 空间
D.E.Knuth 的基本见地： 一个程序运行的时间主要和两点有关： - 执行每条语句的耗时 - 取决于计算机、Java编译器和操作系统 - 执行每条语句的频率 - 取决程序本身 和 输入
定义： 我们用~f(N)表示所有随着N的增大除以f(N)的结果趋近于1的函数。我们用g(N)~f(N)表示g(N)/f(N)的随着N的·增大趋近于1。
执行最频繁的指令决定了程序执行的时间，称这些指令为内循环。
本书中 - 性质表示需要用实验验证的猜想 - 命题表示 在某个成本模型下算法的数学性质。
ref
先计算内层循环的时间复杂度,然后用内层的复杂度乘以外层循环的次数
三层循环参考
先计算方法体的的时间复杂度. 
各种级别的对应的经典算法是什么
普通语句 两个数相加
对数的底数和增长的数量级无关（因为不同底数仅相当于一个常数因子）
一维数组找出最大元素
归并排序
检查所有元素对
检查所有三元组
检查所有子集
2sum 计算出数组中和为0的整数对的数量（假设所有元素都是不同的） - 先进行排序 - 然后进行二分查找 - 二分查找不成功，返回-1，我们不改变计数器的值 - 二分查找返回的j > i， 计数器的值+1 - 二分查找的j 在 0 和 i之间，也有a[i] + a[j] = 0;但是不能改变计数器的值,以免重复计数 - 复杂度 NlogN + logN
public int twoSumFast(int[] a){ Arrays.sort(a); int cnt = 0; for(int i = 0 ;i<a.length; i++){ if(Binarysearch.rank(-a[i],a) > i) { cnt++; } } return cnt;}3sum问题快速解法 - (假设所有元素各不相同) - 复杂度 N^2logN
public int threeSumFast(int[] a){ Arrays.sort(a); int cnt = 0; for(int i = 0; i < a.length; i++){ for(int j = i+1; j < a.length; i++){ if(Binarysearch.rank(-(a[i] + a[j]), a) > j) { cnt++; } } } return cnt;}本书中会尝试按照以下的方式解决各种算法问题 1. 实现并分析问题的一种简单解法，通常称它们为暴力解法 2. 考察算法的各种改进 3. 用实验证明新的算法更快。
开发一个输入生成器来产生实际情况下的各种可能的输入
例如使用循环，每次将问题的输入规模增长一倍，再调用方法public static double timeTrail(int N) { int MAX = 100000; int[] a = new int[N]; for (int i = 0; i < N; i++) { a[i] = StdRandom.uniform(-MAX, MAX); } Stopwatch stopwatch = new Stopwatch(); ThreeSum.count(a); return stopwatch.elapsedTime();}public static void main(String[] args) { double prev = timeTrail(125); for(int N = 250 ; true; N+=N){ double time = timeTrail(N); StdOut.printf("%6d %7.1f ", N , time); StdOut.printf("%5.1f/n", time / prev); prev = time; }}命题C (倍率定理) 如果T(N) ~ aN^blgN,那么T(2N)/T(N) ~ 2^b。 - 注：一般而言，数学模型的对数项是不能忽略的，但在倍率假设中它在预测性能的公式中并不那么重要。
性能分析无法得到正确的结果 - 一般都是由于我们的猜想基于的一个或多个假设并不完全正确所造成的。
问题所要处理对输入建模。困难点： - 建立输入模型是不切实际的 - 对输入的分析可能极端困难
命题D。 在Bag、Stack、Queue的链表实现中所有的操作在最坏情况下都是常数级别的
随机打乱输入
例如：栈。先入栈N个值再将它们弹出所得到的性能 跟 N次压入弹出的混合操作序列所得到的性能可能是不同的。
命题E。在基于可调整大小的数组实现的Stack数据结构中，对空数据结构所进行的任意操作序列对数组的平均访问次数 在最坏情况下 均为常数 - 证明：P125
| 类型 | 所占字节数 |
|---|---|
| 对象的引用 （一般是一个内存的地址） | 8 |
| 对象开销 | 16 |
| boolean | 1 |
| byte | 1 |
| char | 2 |
| int | 4 |
| float | 4 |
| double | 8 |
| long | 8 |
填充字节用来填充字节数
HotSpot的对齐方式是以8字节对齐,所有没有对象最终大小没有到8个字节的倍数的,都会被填充一般内存的使用都会被填充为8字节（64位计算机中的机器字）当我们说明一个引用所占的内存时，会单独说明它所指向的对象所占用的内存
嵌套的非静态（内部)类,还需额外的8个字节（用于一个指向外部类的引用）
分析时，画出图像，一个一个对应写出来。
| 数组 | 字节 |
|---|---|
| 对象开销 | 16 |
| int 数组长度 | 4 |
| 填充字节 | ？ |
| … | … |
eg：
| 数组 | 字节 |
|---|---|
| 对象开销 | 16 |
| int 数组长度 | 4 |
| 填充字节 | 4 |
| double | 8 |
| double | 8 |
| 。。。 | |
| double | 8 |
- 一个原始数据类型的数组一般需要24字节的头信息 - 16字节的对象开销 - 4字节（int类型）保存数组长度 - 4个填充字节
一个对象的数组（一个对象的引用的数组），一般需要24字节的头信息小结
| 类型 | 字节数 | 近似 |
|---|---|---|
| int[] | 24+4N | ~4N |
| double[] | 24+8N | ~8N |
| long[] | 24+8N | ~8N |
| Date[] | 24+8N + 32N | ~40N |
| double[][] | 24+8M + (24+8N)*M | ~8MN |
三个int值： - 偏移量 - 计数器（字符串的长度） - 散列值
//String对象public class String{ char[] value; int offset; int count; int hash; ....|| 字符串对象 | 字节 |
|---|---|
| 对象开销 | 16 |
| 字符串的值（引用） | 8 |
| 偏移量 （int） | 4 |
| 字符串的长度（int） | 4 |
| 散列值 （int） | 4 |
| 填充字节 | 4 |
一个长度为N的String对象一般需要使用40字节（String对象本身），加上（24+2N）字节（字符数组），总共（64+2N）字节。
调用subString方法时，会创建一个新的String对象（40字节），但是它会重用相同的value数组（通过偏移量和它的字符串长度来指定 ），因此只占40字节内存。
先画出图来，再写代码，易理解。 - 用节点（带标签的圆圈）表示触点 - 用一个节点到另一个结点的箭头表示 链接
由此得到的数据结构的图像表示使我们理解算法的操作变得相对容易。
等价关系能够将对象分为多个等价类。 - 当且仅当两个对象相连时他们才属于同一个等价类。
此程序能够判定我们是否需要在p和q之间架设一条新的连接才能进行通信，或是我们可以通过已有的连接在两者之间建立通信线路。
在程序中，可以声明多个引用来指向同一对象，这个时候就可以通过为程序中声明的引用和实际对象建立动态连通图来判断哪些引用实际上是指向同一对象。
并查集 笔记
对问题进行建模的时候，先尽量想清楚要解决的问题是什么。 就动态连接性这个场景而言，我们要解决的问题可能是： - 给出两个结点，判断他们是否连通，==如果连通，需要给出具体的路径== - union-find 属于第一种 - 给出两个结点，判断他们是否连通，==如果连通，不需要给出具体的路径== - 使用基于DFS的算法
更高的抽象层次上，可以将输入的所有整数 看做属于不同的数学集合。 - 在处理一个整数对p和q时，我们是在判断它们是否属于相同的集合 - 如果不是，就将p所属的集合和q所属的集合归并到同一个集合中。
将 整数对 称为连接将 对象 称为触点将 等价类 称为连通分量（简称 分量）union-find的成本模型。在研究实现union-find的API的各种算法时，我们统计的是数组的访问次数（无论读写）
API 
注意其中使用整数来表示节点，如果需要使用其他的数据类型表示节点，比如使用字符串，那么可以用哈希表来进行映射，即将String映射成这里需要的Integer类型。
在同一个连通分量中的所有触点的id[] 中的值必须全部相同。
命题F。在quick-find算法中，每次find()调用只需访问数组一次，归并两个分量的union操作访问数组的次数在(N+3) 和 (2N+1)之间。
考虑一下，为什么以上的quick-find 解法会造成“牵一发而动全身”？因为每个节点所属的组号都是单独记录，各自为政的，没有将它们以更好的方式组织起来，当涉及到修改的时候，除了逐一通知、修改，别无他法。
所以现在的问题就变成了，如何将节点以更好的方式组织起来，组织的方式有很多种，但是最直观的还是将组号相同的节点组织在一起，想想所学的数据结构，什么样子的数据结构能够将一些节点给组织起来？常见的就是链表，图，树，什么的了。但是哪种结构对于查找和修改的效率最高？毫无疑问是树，因此考虑如何将节点和组的关系以树的形式表现出来。
union与find算法是互补的。 赋予id[] 数组的值 不同的意义，每一个触点所对应的id[]元素 都是同一个分量中另一个的触点的名称（也可能是自己）
“根节点”作为连通分量的标识。
//建立链接，每一个触点所对应的id[]元素 都是同一个分量中另一个的触点的名称（也可能是自己）public int quick_find(int p) { //找出分量的名称 while (id[p] != p) { p = id[p]; } return p;}//public void quick_union(int p ,int q) { //p和q的根触点 （类似于树的根节点） int pRoot = quick_find(p); int qRoot = quick_find(q); if (pRoot == qRoot) { return; } id[pRoot] = qRoot; count--;// 全局的统计量更改}定义。一棵树的大小是它节点的数量 - 树中的一个节点的深度是它到根节点的路径上的链接数（即 路径节点总数-1）
命题G。quick-union算法中的find()方法访问数组的次数为1 加上给触点所对应的节点的深度的两倍。union和connected 访问数组的次数为两次find操作（如果不在同一个分量中还要加1）
目的：控制树高。以减少find查询时间。
添加一个数组和一些代码来记录树中的节点数，让比较小（节点数目比较少）的树的根指向比较大（节点数目多）的树的根，（减少find查询时间）改进算法的效率。
命题H。对N个触点，加权union算法构造的森林中的任意节点的深度最多为lgN。
推论。对于加权quick-union算法和N个触点，在最坏情况下find connected 和 union 的成本增长数量级为logN。
命题和它的推论的实际意义在于加权quick-union算法是三种算法中唯一能解决大型实际问题的算法。
路径压缩算法，每个结点都直接连接到根节点。 - 实现：在检查节点的同时将它们直接链接到根节点。
public int find(int p){ int root = p; while(root != id[root]){ root = id[root]; } while(p != root){ int newP = p; id[p] = root; p = newP; } return root;}新闻热点
疑难解答
