《剑指offer》内容总结 （1）剑指Offer——Trie树(字典树) （2）剑指Offer——分治算法 （3）剑指Offer——简述堆和栈的区别 （4）数据结构进阶(四)二叉排序树(二叉查找树) （5）Java多线程讲解 （6）剑指Offer——全排列递归思路 （7）剑指Offer——二叉树 （8）剑指Offer——栈的java实现和栈的应用举例 （9）剑指Offer——动态规划算法 （10）剑指Offer——二分查找算法 （11）剑指Offer——贪心算法 （12）剑指Offer——排序算法小结
Trie树
Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
Trie树也有它的缺点，Trie树的内存消耗非常大。当然，或许用左儿子右兄弟的方法建树的话，可能会好点。可见，优化的点存在于建树过程中。
和二叉查找树不同，在trie树中，每个结点上并非存储一个元素。trie树把要查找的关键词看作一个字符序列，并根据构成关键词字符的先后顺序构造用于检索的树结构。在trie树上进行检索类似于查阅英语词典。
3个基本性质
1.根节点不包含字符，每条边代表一个字符。
2.从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3.每个节点的所有子节点包含的字符都不相同。
字典树的构建
题目：给你100000个长度不超过10的单词。对于每一个单词，我们要判断他出没出现过，如果出现了，求第一次出现在第几个位置。
分析：这题当然可以用hash来解决，但是本文重点介绍的是trie树，因为在某些方面它的用途更大。比如说对于某一个单词，我们要询问它的前缀是否出现过。这样hash就不好搞了，而用trie还是很简单。
假设我要查询的单词是abcd，那么在他前面的单词中，以b，c，d，f之类开头的我显然不必考虑。而只要找以a开头的中是否存在abcd就可以了。同样的，在以a开头中的单词中，我们只要考虑以b作为第二个字母的，一次次缩小范围和提高针对性，这样一个树的模型就渐渐清晰了。
好比假设有b，abc，abd，bcd，abcd，efg，hii 这6个单词，我们构建的树就是如下图这样的（图片来自百度百科）：
如上图所示，对于每一个节点，从根遍历到他的过程就是一个单词，如果这个节点被标记为红色，就表示这个单词存在，否则不存在。
那么，对于一个单词，我只要顺着他从根走到对应的节点，再看这个节点是否被标记为红色就可以知道它是否出现过了。把这个节点标记为红色，就相当于插入了这个单词。
这样一来我们查询和插入可以一起完成（重点体会这个查询和插入是如何一起完成的，稍后，下文具体解释）。
我们可以看到，trie树每一层的节点数是26^i（26个英文字母）级别的。所以为了节省空间，我们用动态链表，或者用数组来模拟。空间的花费，不会超过单词数×单词长度。
已知n个由小写字母构成的平均长度为10的单词,判断其中是否存在某个串为另一个串的前缀子串。下面对比3种方法：
最容易想到的：1.即从字符串集中从头往后搜，看每个字符串是否为字符串集中某个字符串的前缀，复杂度为O(n^2)。
2.使用hash：我们用hash存下所有字符串的所有前缀子串，建立存有子串hash的复杂度为O(n*len)，而查询的复杂度为O(n)* O(1)= O(n)。
3.使用trie：因为当查询如字符串abc是否为某个字符串的前缀时，显然以b,c,d....等不是以a开头的字符串就不用查找了。所以建立trie的复杂度为O(n*len)，而建立+查询在trie中是可以同时执行的，建立的过程也就可以称为查询的过程，hash就不能实现这个功能。所以总的复杂度为O(n*len)，实际查询的复杂度也只是O(len)。（说白了，就是Trie树的平均高度h为len，所以Trie树的查询复杂度为O（h）=O（len）。好比一棵二叉平衡树的高度为logN，则其查询，插入的平均时间复杂度亦为O（logN））。
查询
Trie树是简单但实用的数据结构，通常用于实现字典查询。我们做即时响应用户输入的AJAX搜索框时，就是Trie树。本质上，Trie是一棵存储多个字符串的树。相邻节点间的边代表一个字符，这样树的每条分支代表一则子串，而树的叶节点则代表完整的字符串。和普通树不同的地方是，相同的字符串前缀共享同一条分支。下面，再举一个例子。给出一组单词，inn, int, at, age, adv, ant, 我们可以得到下面的Trie：
可以看出：
每条边对应一个字母。
每个节点对应一项前缀。叶节点对应最长前缀，即单词本身。
单词inn与单词int有共同的前缀“in”, 因此他们共享左边的一条分支，root->i->in。同理，ate, age, adv, 和ant共享前缀"a"，所以他们共享从根节点到节点"a"的边。
查询操纵非常简单。比如要查找int，顺着路径i -> in -> int就找到了。
搭建Trie的基本算法也很简单，无非是逐一把每个单词的每个字母插入Trie。插入前先看前缀是否存在。如果存在，就共享，否则创建对应的节点和边。比如要插入单词add，就有下面几步：
考察前缀"a"，发现边a已经存在。于是顺着边a走到节点a。
考察剩下的字符串"dd"的前缀"d"，发现从节点a出发，已经有边d存在。于是顺着边d走到节点ad
考察最后一个字符"d"，这下从节点ad出发没有边d了，于是创建节点ad的子节点add，并把边ad->add标记为d。
查找分析
在trie树中查找一个关键字的时间和树中包含的结点数无关，而取决于组成关键字的字符数。而二叉查找树的查找时间和树中的结点数有关O(log2n)。
如果要查找的关键字可以分解成字符序列且不是很长，利用trie树查找速度优于二叉查找树。例如：若关键字长度最大是5，则利用trie树，利用5次比较可以从26^5＝11881376个可能的关键字中检索出指定的关键字。而利用二叉查找树至少要进行次比较。
应用
1. 字符串检索，词频统计，搜索引擎的热门查询
事先将已知的一些字符串（字典）的有关信息保存到trie树里，查找另外一些未知字符串是否出现过或者出现频率。
举例：
1、有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
2、给出N 个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。
3、给出一个词典，其中的单词为不良单词。单词均为小写字母。再给出一段文本，文本的每一行也由小写字母构成。判断文本中是否含有任何不良单词。例如，若rob是不良单词，那么文本problem含有不良单词。
4、1000万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串。请怎么设计和实现？
5、一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。
6、寻找热门查询：搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复读比较高，虽然总数是1千万，但是如果去除重复和，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G(京东笔试题简答题与此类似)。
(1) 请描述你解决这个问题的思路；
(2) 请给出主要的处理流程，算法，以及算法的复杂度。
2. 字符串最长公共前缀
Trie树利用多个字符串的公共前缀来节省存储空间，反之，当我们把大量字符串存储到一棵trie树上时，我们可以快速得到某些字符串的公共前缀。举例：
1) 给出N 个小写英文字母串，以及Q 个询问，即询问某两个串的最长公共前缀的长度是多少. 解决方案：
首先对所有的串建立其对应的字母树。此时发现，对于两个串的最长公共前缀的长度即它们所在结点的公共祖先个数，于是，问题就转化为了离线（Offline）的最近公共祖先（Least Common Ancestor，简称LCA）问题。
而最近公共祖先问题同样是一个经典问题，可以用下面几种方法：
1. 利用并查集（Disjoint Set），可以采用经典的Tarjan 算法；
2. 求出字母树的欧拉序列（Euler Sequence ）后，就可以转为经典的最小值查询（Range Minimum Query，简称RMQ）问题了；
3. 排序
Trie树是一棵多叉树，只要先序遍历整棵树，输出相应的字符串便是按字典序排序的结果。
举例：给你N 个互不相同的仅由一个单词构成的英文名，让你将它们按字典序从小到大排序输出。
4. 作为其他数据结构和算法的辅助结构
如后缀树，AC自动机等。
举例
下面以字典树的构建与单词查找为例。
TrieTreeNode.java
- package cn.edu.ujn.trieTree;
- public class TrieTreeNode {
- int nCount; //记录该字符出现次数
- char ch; //记录该字符
- TrieTreeNode[] child; // 记录子节点
- final int MAX_SIZE = 26;
- public TrieTreeNode() {
- nCount=1;
- child = new TrieTreeNode[MAX_SIZE];
- }
- }
TrieTree.java
- package cn.edu.ujn.trieTree;
- public class TrieTree {
- //字典树的插入和构建
- public void createTrie(TrieTreeNode node,String str){
- if (str == null || str.length() == 0) {
- return;
- }
- char[] letters = str.toCharArray();
- for (int i = 0; i < letters.length; i++) {
- int pos = letters[i] - 'a'; // 用相对于a字母的值作为下标索引，也隐式地记录了该字母的值
- if (node.child[pos] == null) {
- node.child[pos] = new TrieTreeNode();
- }else {
- node.child[pos].nCount++;
- }
- node.ch = letters[i];
- node = node.child[pos];
- }
- }
- //字典树的查找
- public int findCount(TrieTreeNode node,String str){
- if (str == null || str.length() == 0) {
- return -1;
- }
- char[] letters = str.toCharArray();
- for (int i = 0; i < letters.length; i++) {
- int pos = letters[i] - 'a';
- if (node.child[pos] == null) {
- return 0;
- }else {
- node = node.child[pos];
- }
- }
- return node.nCount;
- }
- }
Test.java
- package cn.edu.ujn.trieTree;
- public class Test {
- public static void main(String[] args) {
- /**
- * Problem Description 老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计
- * 出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
- */
- String[] strs = { "banana", "band", "bee", "absolute", "acm" };
- String[] prefix = { "ba", "b", "band", "abc" };
- TrieTree tree = new TrieTree();
- TrieTreeNode root = new TrieTreeNode();
- for (String s : strs) {
- tree.createTrie(root, s);
- }
- // tree.printAllWords();
- for (String pre : prefix) {
- int num = tree.findCount(root, pre);
- System.out.println(pre + " " + num);
- }
- }
- }
小结
看过上面的代码，是否发现这个代码有什么问题呢？尽管这个实现方式查找的效率很高，时间复杂度是O(m)，m是要查找的单词中包含的字母的个数。但是确浪费大量存放空指针的存储空间。因为不可能每个节点的子节点都包含26个字母的。所以对于这个问题，字典树存在的意义是解决快速搜索的问题，所以采取以空间换时间的作法也毋庸置疑。
Trie树占用内存较大，例如：处理最大长度为20、全部为小写字母的一组字符串，则可能需要 2620 个节点来保存数据。而这样的树实际上稀疏的十分厉害，可以采用左儿子右兄弟的方式来改善，也可以采用需要多少子节点则添加多少子节点来解决（不要类似网上的示例，每个节点初始化时就申请一个长度为26的数组）。
Wiki上提到了采用三数组Trie(Tripple-Array Trie)和二数组Trie(Double-Array Trie)来解决该问题，此外还有压缩等方式来缓解该问题。
示例优化
TrieTreeNode.java
- package cn.edu.ujn.trieTreeMap;
- import java.util.HashMap;
- import java.util.Map;
- public class TrieNode {
- int nCount; //记录该字符出现次数
- Map<Character, TrieNode> childdren; // 记录子节点
- public TrieNode() {
- nCount = 1;
- childdren = new HashMap<Character, TrieNode>();
- }
- }
TrieTree.java
- package cn.edu.ujn.trieTreeMap;
- // 利用Map动态创建节点
- public class TrieTree {
- // 字典树的插入和构建
- public void insert(TrieNode node, String word) {
- for (int i = 0; i < word.length(); i++) {
- Character c = new Character(word.charAt(i));
- if (!node.childdren.containsKey(c)) {
- node.childdren.put(c, new TrieNode());
- }else{
- node.childdren.get(c).nCount++;
- }
- node = node.childdren.get(c);
- }
- }
- // 字典树的查找
- public int search(TrieNode node, String word) {
- for (int i = 0; i < word.length(); i++) {
- Character c = new Character(word.charAt(i));
- if (!node.childdren.containsKey(c)) {
- return 0;
- }
- node = node.childdren.get(c);
- }
- return node.nCount;
- }
- }
Test.java
- package cn.edu.ujn.trieTreeMap;
- public class Test {
- public static void main(String[] args) {
- /**
- * Problem Description 老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计
- * 出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
- */
- String[] strs = { "banana", "band", "bee", "absolute", "acm" };
- String[] prefix = { "ba", "b", "band", "abc" };
- TrieTree tree = new TrieTree();
- TrieNode node = new TrieNode();
- for (String s : strs) {
- tree.insert(node, s);
- }
- // tree.printAllWords();
- for (String pre : prefix) {
- int num = tree.search(node, pre);
- System.out.println(pre + " " + num);
- }
- }
- }
计算结果如下：
经过以上方法的改进，可避免冗余节点的存在。将字典树的优势进一步放大。当然，也可以使用左儿子右兄弟的形式创建字典树。此方法后续介绍~
文件读入
- package cn.edu.ujn.trieTreeMap;
- import java.io.BufferedReader;
- import java.io.File;
- import java.io.FileInputStream;
- import java.io.InputStreamReader;
- public class Test {
- public static void main(String[] args) {
- /**
- * Problem Description 老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计
- * 出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
- */
- String[] strs = { "banana", "band", "bee", "absolute", "acm" };
- String[] prefix = { "网易", "软件", "band", "abc" };
- TrieTree tree = new TrieTree();
- TrieNode node = new TrieNode();
- BufferedReader br = null;
- try {
- File file= new File("C://Users//SHQ//Desktop//Offer.txt");
- //读取语料库words.txt
- br = new BufferedReader(new InputStreamReader(new FileInputStream(file.getAbsolutePath()),"GBK"));
- String word="";
- while ((word = br.readLine()) != null) {
- tree.insert(node, word);
- }
- }catch (Exception e) {
- // TODO: handle exception
- e.printStackTrace();
- }
- /*for (String s : strs) {
- tree.insert(node, s);
- }*/
- // tree.printAllWords();
- for (String pre : prefix) {
- int num = tree.search(node, pre);
- System.out.println(pre + " " + num);
- }
- }
- }
计算结果如下:
Offer.txt文本内容如下:
可知计算结果正确。而且出现了中文字符，对于数字的操作同理。而利用第一种方法就无法实现固定分配内存。只能使用动态分配机制。
（2）剑指Offer——分治算法
基本概念
在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……
任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。
基本思想及策略
分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
如果原问题可分割成k个子问题，1<k≤n，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
分治法适用的情况
分治法所能解决的问题一般具有以下几个特征：
1) 该问题的规模缩小到一定的程度就可以容易地解决；
2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
3) 利用该问题分解出的子问题的解可以合并为该问题的解；
4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题；
第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；
第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；
第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。
第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。
分治法的基本步骤
分治法在每一层递归上都有三个步骤：
step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
step3 合并：将各个子问题的解合并为原问题的解。
它的一般的算法设计模式如下：
Divide-and-Conquer(P)
1. if |P|≤n0
2. then return(ADHOC(P))
3. 将P分解为较小的子问题 P1 ,P2 ,…,Pk
4. for i←1 to k
5. do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi
6. T ← MERGE(y1,y2,…,yk) △ 合并子问题
7. return(T)
其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC(P)求解。算法MERGE(y1,y2,…,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,…,Pk的相应的解y1,y2,…,yk合并为P的解。
分治法的复杂性分析
一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：
T（n）= k T(n/m)+f(n)
通过迭代法求得方程的解：
递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当mi≤n<mi+1时，T(mi)≤T(n)<T(mi+1)。
可使用分治法求解的一些经典问题
（1）二分搜索
（2）大整数乘法
（3）Strassen矩阵乘法
（4）棋盘覆盖
（5）合并排序
（6）快速排序
（7）线性时间选择
（8）最接近点对问题
（9）循环赛日程表
（10）汉诺塔
依据分治法设计程序时的思维过程
实际上就是类似于数学归纳法，找到解决本问题的求解方程公式，然后根据方程公式设计递归程序。
1、一定是先找到最小问题规模时的求解方法
2、然后考虑随着问题规模增大时的求解方法
3、找到求解的递归函数式后（各种规模或因子），设计递归程序即可。
（3）剑指Offer——简述堆和栈的区别
堆(Heap)
Java堆是被所有线程共享的一块内存区域，在虚拟机启动时创建；
Java虚拟机规范描述:所有的对象实例及数组都要在堆上分配；
Java堆可以处于物理上不连续的内存空间，只要逻辑上连续即可;
(线程共享)堆内存中的对象对所有线程可见。堆内存中的对象可以被所有线程访问;
(异常提示)如果是堆内存没有可用的空间存储生成的对象，JVM会抛出java.lang.OutOfMemoryError；
(内存分配)动态分配内存
栈(Stack)
存放基本类型的数据和对象的引用，即存放变量;
如果存放的是基本类型数据（非静态变量），则直接将变量名和值存入stack中的内存中；
如果是引用类型，则将变量名存入栈，然后指向它new出的对象（存放在堆中）;
(线程私有)栈内存归属于单个线程，每个线程都会有一个栈内存，其存储的变量只能在其所属线程中可见，即栈内存可以理解成线程的私有内存;
(内存分配)栈的内存要远远小于堆内存，如果你使用递归的话，那么你的栈很快就会充满。如果递归没有及时跳出，很可能发生*Error问题;
(异常提示)如果栈内存没有可用的空间存储方法调用和局部变量，JVM会抛出java.lang.*Error；
(内存分配)内存分配固定；
存取速度比堆要快，仅次于寄存器，栈数据可以共享；
附 栈数据共享
栈有一个很重要的特殊性，就是存在栈中的数据可以共享。假设我们同时定义：
int a = 3;
int b = 3；
编译器先处理int a = 3；首先它会在栈中创建一个变量为a的引用，然后查找栈中是否有3这个值，如果没找到，就将3存放进来，然后将a指向3。接着处理int b = 3；在创建完b的引用变量后，因为在栈中已经有3这个值，便将b直接指向3。这样，就出现了a与b同时均指向3的情况。
这时，如果再令a=4；那么编译器会重新搜索栈中是否有4值，如果没有，则将4存放进来，并令a指向4；如果已经有了，则直接将a指向这个地址。因此a值的改变不会影响到b的值。
要注意这种数据的共享与两个对象的引用同时指向一个对象的这种共享是不同的，因为这种情况a的修改并不会影响到b, 它是由编译器完成的，它有利于节省空间。而一个对象引用变量修改了这个对象的内部状态，会影响到另一个对象引用变量。
String是一个特殊的包装类数据。可以用：
String str = new String("abc");
String str = "abc";
两种的形式来创建，第一种是用new()来新建对象的，它会在存放于堆中。每调用一次就会创建一个新的对象。
而第二种是先在栈中创建一个对String类的对象引用变量str，然后查找栈中有没有存放"abc"，如果没有，则将"abc"存放进栈，并令str指向”abc”，如果已经有”abc”则直接令str指向“abc”。
比较类里面的数值是否相等时，用equals()方法；当测试两个包装类的引用是否指向同一个对象时，用==，下面用例子说明上面的理论。
String str1 = "abc";
String str2 = "abc";
System.out.println(str1==str2); //true
可以看出str1和str2是指向同一个对象的。
String str1 =new String ("abc");
String str2 =new String ("abc");
System.out.println(str1==str2); // false
用new的方式是生成不同的对象。每一次生成一个。
因此用第一种方式创建多个”abc”字符串,在内存中其实只存在一个对象而已. 这种写法有利于节省内存空间. 同时它可以在一定程度上提高程序的运行速度，因为JVM会自动根据栈中数据的实际情况来决定是否有必要创建新对象。而对于String str = new String("abc")；的代码，则一概在堆中创建新对象，而不管其字符串值是否相等，是否有必要创建新对象，从而加重了程序的负担。
另一方面, 要注意: 我们在使用诸如String str = "abc"；的格式定义类时，总是想当然地认为，创建了String类的对象str。担心陷阱！对象可能并没有被创建！而可能只是指向一个先前已经创建的 对象。只有通过new()方法才能保证每次都创建一个新的对象。
由于String类的immutable性质，当String变量需要经常变换其值时，应该考虑使用StringBuffer(线程安全，效率低)类，以提高程序效率。
（4）数据结构进阶(四)二叉排序树(二叉查找树)
注:构造一棵二叉排序树的目的，其实并不是为了排序(中序遍历)，而是为了提高查找、插入、删除关键字的速度。
定义
二叉排序树又叫二叉查找树，英文名称是：Binary Sort Tree.BST的定义就不详细说了，我用一句话概括：左 < 中 < 右。 根据这个原理，我们可以推断：BST的中序遍历必定是严格递增的。
二叉查找树是满足以下条件的二叉树：
1.左子树上的所有节点值均小于根节点值；
2.右子树上的所有节点值均不小于根节点值；
3.左右子树也满足上述两个条件。
二叉查找树是基于二叉树的，其结点数据结构定义为如下：
- public class TreeNode {
- public Integer data;
- /*该节点的父节点*/
- public TreeNode parent;
- /*该节点的左子节点*/
- public TreeNode left;
- /*该节点的右子节点*/
- public TreeNode right;
- public TreeNode(Integer data) {
- this.data = data;
- }
- @Override
- public String toString() {
- return "TreeNode [data=" + data + "]";
- }
- }
现在明白了什么是二叉查找树，那么二叉查找树的基本操作又是如何来实现的呢？
查找
在二叉查找树中查找x的过程如下：
1、若二叉树是空树，则查找失败。
2、若x等于根结点的数据，则查找成功，否则。
3、若x小于根结点的数据，则递归查找其左子树，否则。
4、递归查找其右子树。
根据上述的步骤，写出其查找操作的代码：
- /**
- * @param data
- * @return TreeNode
- */
- public TreeNode findTreeNode(Integer data){
- if(null == root){
- return null;
- }
- TreeNode current = root;
- while(current != null){
- if(current.data > data){
- current = current.left;
- }else if(current.data < data){
- current = current.right;
- }else {
- return current;
- }
- }
- return null;
- }
插入
二叉查找树的插入过程如下：
1.若当前的二叉查找树为空，则插入的元素为根节点；
2.若插入的元素值小于根节点值，则将元素插入到左子树中；
3.若插入的元素值不小于根节点值，则将元素插入到右子树中。
- /**
- * 往树中加节点
- * @param data
- * @return Boolean 插入成功返回true
- */
- public Boolean addTreeNode(Integer data) {
- if (null == root) {
- root = new TreeNode(data);
- System.out.println("数据成功插入到平衡二叉树中");
- return true;
- }
- TreeNode treeNode = new TreeNode(data);// 即将被插入的数据
- TreeNode currentNode = root;
- TreeNode parentNode;
- while (true) {
- parentNode = currentNode;// 保存父节点
- // 插入的数据比父节点小
- if (currentNode.data > data) {
- currentNode = currentNode.left;
- // 当前父节点的左子节点为空
- if (null == currentNode) {
- parentNode.left = treeNode;
- treeNode.parent = parentNode;
- System.out.println("数据成功插入到二叉查找树中");
- size++;
- return true;
- }
- // 插入的数据比父节点大
- } else if (currentNode.data < data) {
- currentNode = currentNode.right;
- // 当前父节点的右子节点为空
- if (null == currentNode) {
- parentNode.right = treeNode;
- treeNode.parent = parentNode;
- System.out.println("数据成功插入到二叉查找树中");
- size++;
- return true;
- }
- } else {
- System.out.println("输入数据与节点的数据相同");
- return false;
- }
- }
删除
二叉查找树的删除，分三种情况进行处理：
1.p为叶子节点，直接删除该节点，再修改其父节点的指针（注意分是根节点和不是根节点），如图a。
2.p为单支节点（即只有左子树或右子树）。让p的子树与p的父亲节点相连，删除p即可；（注意分是根节点和不是根节点）；如图b。
3.p的左子树和右子树均不空。找到p的后继y，因为y一定没有左子树，所以可以删除y，并让y的父亲节点成为y的右子树的父亲节点，并用y的值代替p的值；或者方法二是找到p的前驱x，x一定没有右子树，所以可以删除x，并让x的父亲节点成为y的左子树的父亲节点。如图c。
（5）Java多线程讲解
前言
接到菜鸟网络的电话面试，面试官让自己谈一下自己对多线程的理解，现将其内容整理如下。
线程生命周期
Java线程具有五种基本状态
新建状态（New）：当线程对象创建后，即进入了新建状态，如：Thread t = new MyThread();
就绪状态（Runnable）：当调用线程对象的start()方法（t.start();），线程即进入就绪状态。处于就绪状态的线程，只是说明此线程已经做好了准备，随时等待CPU调度执行，并不是说执行了t.start()此线程立即就会执行；
运行状态（Running）：当CPU开始调度处于就绪状态的线程时，此时线程才得以真正执行，即进入到运行状态。注：就绪状态是进入到运行状态的唯一入口，也就是说，线程要想进入运行状态执行，首先必须处于就绪状态中；
阻塞状态（Blocked）：处于运行状态中的线程由于某种原因，暂时放弃对CPU的使用权，停止执行，此时进入阻塞状态，直到其进入到就绪状态，才有机会再次被CPU调用以进入到运行状态。根据阻塞产生的原因不同，阻塞状态又可以分为三种：
1.等待阻塞：运行状态中的线程执行wait()方法，使本线程进入到等待阻塞状态；
2.同步阻塞 -- 线程在获取synchronized同步锁失败(因为锁被其它线程所占用)，它会进入同步阻塞状态；
3.其他阻塞 -- 通过调用线程的sleep()或join()或发出了I/O请求时，线程会进入到阻塞状态。当sleep()状态超时、join()等待线程终止或者超时、或者I/O处理完毕时，线程重新转入就绪状态。
死亡状态（Dead）：线程执行完了或者因异常退出了run()方法，该线程结束生命周期。
注 同步阻塞的正解
JAVA多线程实现的三种方式
JAVA多线程实现方式主要有三种：继承Thread类、实现Runnable接口、使用Callable、FutureTask实现有返回结果的多线程。其中前两种方式线程执行完后都没有返回值，只有最后一种是带返回值的。
1.继承Thread类实现多线程
继承Thread类的方法尽管列为一种多线程实现方式，但Thread本质上也是实现了Runnable接口的一个实例，它代表一个线程的实例，并且，启动线程的唯一方法就是通过Thread类的start()实例方法。start()方法是一个native方法，它将启动一个新线程，并执行run()方法。这种方式实现多线程很简单，通过自己的类直接extends Thread，并复写run()方法，就可以启动新线程并执行自己定义的run()方法。例如：
- public class MyThread extends Thread {
- public void run() {
- System.out.println("MyThread.run()");
- }
- }
在合适的地方启动线程如下：
- MyThread myThread1 = new MyThread();
- MyThread myThread2 = new MyThread();
- myThread1.start();
- myThread2.start();
2.实现Runnable接口方式实现多线程
如果自己的类已经extends另一个类，就无法直接extends Thread，此时，必须实现一个Runnable接口，如下：
- public class MyThread extends OtherClass implements Runnable {
- public void run() {
- System.out.println("MyThread.run()");
- }
- }
为了启动MyThread，需要首先实例化一个Thread，并传入自己的MyThread实例：
- MyThread myThread = new MyThread();
- Thread thread = new Thread(myThread);
- thread.start();
事实上，当传入一个Runnable target参数给Thread后，Thread的run()方法就会调用target.run()，参考JDK源代码：
- public void run() {
- if (target != null) {
- target.run();
- }
- }
3.使用Callable和Future创建线程
Callable接口提供了一个call()方法可以作为线程执行体，但call()方法比run()方法功能更为强大：call()方法可以有返回值；call()方法可以声明抛出异常。代码如下:
- //实现Callable接口实现线程类
- public class callableThread implements Callable<Integer>{
- //实现call()方法作为线程执行体
- public Integer call(){
- int i = 0;
- for(; i < 100; i++){
- System.out.println(Thread.currentThread().getName() + “ 的循环变量i的值:” + i);
- }
- //call()方法可以有返回值
- return i;
- }
- public static void main(String [] args){
- //创建Callable对象
- callableThread ct= new callableThread();
- //使用FutureTask来包装Callable对象
- FutureTask<Integer> task = new FutureTask<Integer>(ct);
- for(int i = 0; i < 100; i++){
- System.out.println(Thread.currentThread().getName() + “ 的循环变量i的值:” + i);
- if(i ==20){
- //实质还是以Callable对象来创建并启动线程
- new Thread(task,有返回值的线程).start;
- }
- }
- try{
- //获取线程返回值
- System.out.println(“子线程的返回值:” + task.get());
- }
- catch(Exception ex){
- ex.printStackTrace();
- }
- }
- }
多线程通信(摘录自课本)
经典场景：用2个线程，这2个线程分别代表存款和取款。——现在系统要求存款者和取款者不断重复的存款和取款的动作，而且每当存款者将钱存入账户后，取款者立即取出这笔钱。不允许2次连续存款、2次连续取款。
传统的线程通信
实现上述场景需要用到Object类提供的wait、notify和notifyAll三个方法，这3个方法并不属于Thread类。但这3个方法必须由同步监视器调用，可分为2种情况：
A、对于使用synchronized修饰的同步方法，因为该类的默认实例this就是同步监视器，所以可以在同步中直接调用这3个方法。
B、对于使用synchronized修改的同步代码块，同步监视器是synchronized后可括号中的对象，所以必须使用括号中的对象调用这3个方法
传统方法概述：
一、wait方法：导致当前线程进入等待，直到其他线程调用该同步监视器的notify方法或notifyAll方法来唤醒该线程。
wait方法有3中形式：无参数的wait方法，会一直等待，直到其他线程通知；带毫秒参数的wait和微妙参数的wait，这2种形式都是等待时间到达后苏醒。调用wait方法的当前线程会释放对该对象同步监视器的锁定。
二、notify：唤醒在此同步监视器上等待的单个线程。如果所有线程都在此同步监视器上等待，则会随机选择唤醒其中一个线程。只有当前线程放弃对该同步监视器的锁定后（用wait方法），才可以执行被唤醒的线程。
三、notifyAll：唤醒在此同步监视器上等待的所有线程。只有当前线程放弃对该同步监视器的锁定后，才能执行唤醒的线程。
使用条件变量Condition控制协调
如果程序不使用synchronized关键字来保证同步，而是直接使用Lock对象来保证同步，则系统中不存在隐式的同步监视器对象，也不能使用wait、notify、notifyAll方法来协调进程的运行。
当使用Lock对象同步，Java提供一个Condition类来保持协调，使用Condition可以让那些已经得到Lock对象却无法继续执行的线程释放Lock对象,Condition对象也可以唤醒其它处于等待的线程，Condition将同步监视器(wait()、notify()、notifyAll())分解成截然不同的对象，以便通过将这些对象与Lock对象组合使用，为每个对象提供多个等待集（wait-set）。在这种情况下，Lock替代了同步方法和同步代码块，Condition替代同步监视器的功能。
Condition实例实质上被绑定在一个Lock对象上，要获得特定的Lock实例的Condition实例，调用Lock对象的newCondition即可。
使用阻塞队列(BlockingQueue)控制线程通信
java中阻塞BlockingQueue 接口实现类中用的较多的通常是ArrayBlockingQueue,LinkedBlockingQueue.它们都是线程安全的.ArrayBlockingQueue以数组的形式存储,LinkedBlockingQueue以node节点的方式进行存储.
开发中如果队列的插入操作比较频繁建议使用LinkedBlockingQueue,因为每个node节点都有一个前后指针,插入新元素仅需要变更前后的指针引用即可, ArrayBlockingQueue插入新元素,则新元素之后的元素数组下标位置都要发生变化,性能较差. 如果队列的读取操作比较频繁建议使用ArrayBlockingQueue, ArrayBlockingQueue通过数组下标直接能找到对应元素,LinkedBlockingQueue则需要遍历node链来找到元素.
BlockingQueue 队列常用的操作方法:
1.往队列中添加元素: add(), put(), offer()
2.从队列中取出或者删除元素: remove() element() peek() pool() take()
队列添加新元素一般都是往队尾添加元素,
offer()方法往队列添加元素如果队列已满直接返回false,队列未满则直接插入并返回true;
add()方法是对offer()方法的简单封装.如果队列已满,抛出异常new IllegalStateException("Queue full");
put()方法往队列里插入元素,如果队列已经满,则会一直等待直到队列为空插入新元素,或者线程被中断抛出异常.
队列中取出或者删除元素都是针对队头的元素
remove()方法直接删除队头的元素:
peek()方法直接取出队头的元素,并不删除.
element()方法对peek方法进行简单封装,如果队头元素存在则取出并不删除,如果不存在抛出异常NoSuchElementException()
pool()方法取出并删除队头的元素,当队列为空,返回null;
take()方法取出并删除队头的元素,当队列为空,则会一直等待直到队列有新元素可以取出,或者线程被中断抛出异常
offer()方法一般跟pool()方法相对应, put()方法一般跟take()方法相对应.日常开发过程中offer()与pool()方法用的相对比较频繁.
sleep()和yield()的区别
sleep()和yield()的区别:sleep()使当前线程进入停滞状态(阻塞态)，失去锁的占有权，所以执行sleep()的线程在指定的时间内肯定不会被执行；yield()不会阻塞线程，它只是将该线程转入就绪态。yield()只是让当前线程暂停一下，让系统的线程调度器重新调度一次，完全可能的情况是:当某个线程调用了yield()方法暂停之后，线程调度器又将其调度出来重新执行。
sleep方法使当前运行中的线程睡眠一段时间，进入不可运行状态(阻塞态)，这段时间的长短是由程序设定的，yield方法使当前线程让出CPU占有权，但让出的时间是不可设定的。实际上，yield()方法对应了如下操作：先检测当前是否有相同优先级的线程处于同可运行状态，如有，则把CPU 的占有权交给此线程，否则，继续运行原来的线程。所以yield()方法称为“退让”，它把运行机会让给了同等优先级的其他线程。
另外，sleep方法允许较低优先级的线程获得运行机会，但 yield()方法执行时，当前线程仍处在可运行状态(仍未失去锁)，所以，不可能让出较低优先级的线程些时获得CPU占有权。在一个运行系统中，如果较高优先级的线程没有调用sleep方法，又没有受到IO阻塞，那么，较低优先级线程只能等待所有较高优先级的线程运行结束，才有机会运行。
死锁与线程阻塞的区别
死锁
所谓死锁: 是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。
那么为什么会产生死锁呢？
1.因为系统资源不足。
2.进程运行推进的顺序不合适。
3.资源分配不当。
学过操作系统的朋友都知道：产生死锁的条件有四个：
1.互斥条件：所谓互斥就是进程在某一时间内独占资源。
2.请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
3.不剥夺条件:进程已获得资源，在末使用完之前，不能强行剥夺。
4.循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。
阻塞
线程被堵塞可能是由下述五方面的原因造成的：
(1) 调用sleep(毫秒数)，使线程进入“睡眠”状态。在规定的时间内，这个线程是不会运行的。
(2) 用suspend()暂停了线程的执行。除非线程收到resume()消息，否则不会返回“可运行”状态。
(3) 用wait()暂停了线程的执行。除非线程收到nofify()或者notifyAll()消息，否则不会变成“可运行”。
(4) 线程正在等候一些IO（输入输出）操作完成。
(5) 线程试图调用另一个对象的“同步”方法，但那个对象处于锁定状态，暂时无法使用。
亦可调用yield()（Thread类的一个方法）自动放弃CPU，以便其他线程能够运行。然而，假如调度机制觉得我们的线程已拥有足够的时间，并跳转到另一个线程，就会发生同样的事情。也就是说，没有什么能防止调度机制重新启动我们的线程。
（6）剑指Offer——全排列递归思路
前言
全排列，full permutation, 可以利用二叉树的遍历实现。二叉树的递归遍历，前中后都简洁的难以置信，但是都有一个共同特点，那就是一个函数里包含两次自身调用。
所以，如果一个递归函数中包含了两次自身调用，那么这类问题就是归纳成二分问题。也就是to be or not to be , is the problem。如果一个使用相同手段并且每一个点上可分为两种情况的问题，基本都可以转化为递归问题。当然，如果是有三个孩子的树，那么我们可能需要在一个递归函数中调用自身三次。
这里的递归，和我们计算的阶乘又有不一样，因为他没有返回，是发散的。也就是从一个节点，发散到N个节点，我们要的结果是叶子节点。
计算全排列，我们可以单独拿出每一个元素作为根节点来构成一棵树，所有的可能排列情况就都隐藏在森林中了。现在来看每一颗树，假如4个元素，A，B，C，D，以A为根是第一颗，表示以A开头的排列。
那么，第二个位置可以选着B，C，D，如果我们选择了B，那么B下还有 C， D可以选择， 如果我们选了C，那么最后只剩下D，这样，就列出第一种。如图所示：
我们可以看到，这里的孩子个数是递减的，直到最后一个元素，就不用选择了，同时也得到一种可能。
要枚举出所有的，那么就遍历这样一颗树。好了，先上代码。
- package cn.edu.ujn.nk;
- public class FullPermutation {
- /**
- * recursive method, used for the tree traversal.
- *
- * @param inStr
- * the elements need to be choose
- * @param pos
- * the position of the elements we choose
- * @param parentData
- * the elements have been chosen
- */
- public void permutation(String inStr, int pos, StringBuffer parentData) {
- if (inStr.length() == 0) {
- return;
- }
- if (inStr.length() == 1) {
- System.out.println("{" + inStr + "}");
- return;
- }
- // here we need a new buffer to avoid to pollute the other nodes.
- StringBuffer buffer = new StringBuffer();
- // copy from the parent node
- buffer.append(parentData.toString());
- // choose the element
- buffer.append(inStr.charAt(pos));
- // get the remnant elements.
- String subStr = kickChar(inStr, pos);
- // got one of the result
- if (subStr.length() == 1) {
- buffer.append(subStr);
- System.out.println(buffer.toString());
- return;
- }
- // here we use loop to choose other children.
- for (int i = 0; i < subStr.length(); i++) {
- permutation(subStr, i, buffer);
- }
- }
- // a simple method to delete the element we choose
- private String kickChar(String src, int pos) {
- StringBuffer srcBuf = new StringBuffer();
- srcBuf.append(src);
- srcBuf.deleteCharAt(pos);
- return srcBuf.toString();
- }
- public static void main(String args[]) {
- FullPermutation p = new FullPermutation();
- StringBuffer buffer = new StringBuffer();
- String input = "ABCD";
- for (int i = 0; i < input.length(); i++) {
- p.permutation(input, i, buffer);
- }
- }
- }
（7）剑指Offer——二叉树
前言
数据结构通常是编程面试中考察的重点。在参加面试之前，应聘者需要熟练掌握链表、树、栈、队列和哈希表等数据结构，以及它们的操作。本片博文主要讲解二叉树操作的相关知识，主要包括二叉树的建立、遍历方法的循环和递归写法。
二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。
二叉树的java实现
首先创建一棵二叉树如下图，然后对这颗二叉树进行遍历操作（遍历操作的实现分为递归实现和非递归实现），同时还提供一些方法如获取双亲结点、获取左孩子、右孩子等。
- package cn.edu.ujn.nk;
- import java.util.Stack;
- /**
- * 二叉树的链式存储
- * @author WWX
- */
- public class BinaryTree {
- private TreeNode root=null;
- public BinaryTree(){
- root=new TreeNode(1,"rootNode(A)");
- }
- /**
- * 创建一棵二叉树
- * <pre>
- * A
- * B C
- * D E F
- * </pre>
- * @param root
- * @author WWX
- */
- public void createBinTree(TreeNode root){
- TreeNode newNodeB = new TreeNode(2,"B");
- TreeNode newNodeC = new TreeNode(3,"C");
- TreeNode newNodeD = new TreeNode(4,"D");
- TreeNode newNodeE = new TreeNode(5,"E");
- TreeNode newNodeF = new TreeNode(6,"F");
- root.leftChild=newNodeB;
- root.rightChild=newNodeC;
- root.leftChild.leftChild=newNodeD;
- root.leftChild.rightChild=newNodeE;
- root.rightChild.rightChild=newNodeF;
- }
- public boolean isEmpty(){
- return root==null;
- }
- //树的高度
- public int height(){
- return height(root);
- }
- //节点个数
- public int size(){
- return size(root);
- }
- private int height(TreeNode subTree){
- if(subTree == null)
- return 0; // 递归结束：空树高度为0
- else{
- int i = height(subTree.leftChild);
- int j = height(subTree.rightChild);
- return (i < j) ? (j + 1) : (i + 1);
- }
- }
- private int size(TreeNode subTree){
- if(subTree == null){
- return 0;
- }else{
- return 1 + size(subTree.leftChild) + size(subTree.rightChild);
- }
- }
- //返回双亲结点
- public TreeNode parent(TreeNode element){
- return (root == null|| root == element) ? null : parent(root, element);
- }
- public TreeNode parent(TreeNode subTree,TreeNode element){
- if(subTree == null)
- return null;
- if(subTree.leftChild == element || subTree.rightChild == element)
- //返回父结点地址
- return subTree;
- TreeNode p;
- // 先在左子树中找，如果左子树中没有找到，才到右子树去找
- if((p = parent(subTree.leftChild, element)) != null)
- //递归在左子树中搜索
- return p;
- else
- //递归在右子树中搜索
- return parent(subTree.rightChild, element);
- }
- public TreeNode getLeftChildNode(TreeNode element){
- return (element != null) ? element.leftChild : null;
- }
- public TreeNode getRightChildNode(TreeNode element){
- return (element != null) ? element.rightChild : null;
- }
- public TreeNode getRoot(){
- return root;
- }
- //在释放某个结点时，该结点的左右子树都已经释放，
- //所以应该采用后续遍历，当访问某个结点时将该结点的存储空间释放
- public void destroy(TreeNode subTree){
- //删除根为subTree的子树
- if(subTree!=null){
- //删除左子树
- destroy(subTree.leftChild);
- //删除右子树
- destroy(subTree.rightChild);
- //删除根结点
- subTree=null;
- }
- }
- public void traverse(TreeNode subTree){
- System.out.println("key:"+subTree.key+"--name:"+subTree.data);;
- traverse(subTree.leftChild);
- traverse(subTree.rightChild);
- }
- //前序遍历
- public void preOrder(TreeNode subTree){
- if(subTree!=null){
- visted(subTree);
- preOrder(subTree.leftChild);
- preOrder(subTree.rightChild);
- }
- }
- //中序遍历
- public void inOrder(TreeNode subTree){
- if(subTree!=null){
- inOrder(subTree.leftChild);
- visted(subTree);
- inOrder(subTree.rightChild);
- }
- }
- //后续遍历
- public void postOrder(TreeNode subTree) {
- if (subTree != null) {
- postOrder(subTree.leftChild);
- postOrder(subTree.rightChild);
- visted(subTree);
- }
- }
- //前序遍历的非递归实现
- public void nonRecPreOrder(TreeNode p){
- Stack<TreeNode> stack=new Stack<TreeNode>();
- TreeNode node=p;
- while(node!=null||stack.size()>0){
- while(node!=null){
- visted(node);
- stack.push(node);
- node=node.leftChild;
- }
- while(stack.size()>0){
- node=stack.pop();
- node=node.rightChild;
- }
- }
- }
- //中序遍历的非递归实现
- public void nonRecInOrder(TreeNode p){
- Stack<TreeNode> stack =new Stack<BinaryTree.TreeNode>();
- TreeNode node =p;
- while(node!=null||stack.size()>0){
- //存在左子树
- while(node!=null){
- stack.push(node);
- node=node.leftChild;
- }
- //栈非空
- if(stack.size()>0){
- node=stack.pop();
- visted(node);
- node=node.rightChild;
- }
- }
- }
- //后序遍历的非递归实现
- public void noRecPostOrder(TreeNode p){
- Stack<TreeNode> stack=new Stack<BinaryTree.TreeNode>();
- TreeNode node =p;
- while(p!=null){
- //左子树入栈
- for(;p.leftChild!=null;p=p.leftChild){
- stack.push(p);
- }
- //当前结点无右子树或右子树已经输出
- while(p!=null&&(p.rightChild==null||p.rightChild==node)){
- visted(p);
- //纪录上一个已输出结点
- node =p;
- if(stack.empty())
- return;
- p=stack.pop();
- }
- //处理右子树
- stack.push(p);
- p=p.rightChild;
- }
- }
- public void visted(TreeNode subTree){
- subTree.isVisted=true;
- System.out.println("key:"+subTree.key+"--name:"+subTree.data);;
- }
- /**
- * 二叉树的节点数据结构
- * @author WWX
- */
- private class TreeNode{
- private int key = 0;
- private String data = null;
- private boolean isVisted = false;
- private TreeNode leftChild = null;
- private TreeNode rightChild = null;
- public TreeNode(){}
- /**
- * @param key 层序编码
- * @param data 数据域
- */
- public TreeNode(int key,String data){
- this.key = key;
- this.data = data;
- this.leftChild = null;
- this.rightChild = null;
- }
- }
- //测试
- public static void main(String[] args) {
- BinaryTree bt = new BinaryTree();
- bt.createBinTree(bt.root);
- System.out.println("the size of the tree is " + bt.size());
- System.out.println("the height of the tree is " + bt.height());
- System.out.println("***递归实现****(前序遍历)[ABDECF]遍历*****************");
- bt.preOrder(bt.root);
- System.out.println("***递归实现****(中序遍历)[DBEACF]遍历*****************");
- bt.inOrder(bt.root);
- System.out.println("***递归实现****(后序遍历)[DEBFCA]遍历*****************");
- bt.postOrder(bt.root);
- System.out.println("***非递归实现****(前序遍历)[ABDECF]遍历*****************");
- bt.nonRecPreOrder(bt.root);
- System.out.println("***非递归实现****(中序遍历)[DBEACF]遍历*****************");
- bt.nonRecInOrder(bt.root);
- System.out.println("***非递归实现****(后序遍历)[DEBFCA]遍历*****************");
- bt.noRecPostOrder(bt.root);
- }
- }
（8）剑指Offer——栈的java实现和栈的应用举例
栈是一种先进后出的数据结构, 栈的实现如下：
首先定义了栈需要实现的接口:
- public interface MyStack<T> {
- /**
- * 判断栈是否为空
- */
- boolean isEmpty();
- /**
- * 清空栈
- */
- void clear();
- /**
- * 栈的长度
- */
- int length();
- /**
- * 数据入栈
- */
- boolean push(T data);
- /**
- * 数据出栈
- */
- T pop();
- }
接下来定义了栈的数组实现：
- package cn.edu.ujn.stack;
- /**
- * 栈的数组实现, 底层使用数组
- * @author SHQ
- *
- * @param <T>
- */
- public class MyArrayStack<T> implements MyStack<T> {
- // 定义初始栈的大小
- private Object[] objs = new Object[16];
- // 栈的大小
- private int size = 0;
- @Override
- public boolean isEmpty() {
- return size == 0;
- }
- @Override
- public void clear() {
- // 将数组中的数据置为null, 方便GC进行回收
- for (int i = 0; i < size; i++) {
- objs[size] = null;
- }
- size = 0;
- }
- @Override
- public int length() {
- return size;
- }
- @Override
- public boolean push(T data) {
- // 判断是否需要进行数组扩容
- if (size >= objs.length) {
- resize();
- }
- objs[size++] = data;
- return true;
- }
- /**
- * 数组扩容
- */
- private void resize() {
- Object[] temp = new Object[objs.length * 3 / 2 + 1];
- // 复制
- for (int i = 0; i < size; i++) {
- temp[i] = objs[i];
- objs[i] = null;
- }
- // 将objs重新设置为栈空间
- objs = temp;
- }
- @SuppressWarnings("unchecked")
- @Override
- public T pop() {
- if (size == 0) {
- return null;
- }
- return (T) objs[--size];
- }
- @Override
- public String toString() {
- StringBuilder sb = new StringBuilder();
- sb.append("MyArrayStack: [");
- for (int i = 0; i < size; i++) {
- sb.append(objs[i].toString());
- if (i != size - 1) {
- sb.append(", ");
- }
- }
- sb.append("]");
- return sb.toString();
- }
- }
然后定义了栈的链表实现：
- package cn.edu.ujn.stack;
- /**
- * 栈的链表实现, 底层使用链表
- * @author SHQ
- *
- * @param <T>
- */
- public class MyLinkedStack<T> implements MyStack<T> {
- /**
- * 栈顶指针
- */
- private Node top;
- /**
- * 栈的长度
- */
- private int size;
- public MyLinkedStack() {
- top = null;
- size = 0;
- }
- @Override
- public boolean isEmpty() {
- return size == 0;
- }
- @Override
- public void clear() {
- top = null;
- size = 0;
- }
- @Override
- public int length() {
- return size;
- }
- @Override
- public boolean push(T data) {
- Node node = new Node();
- node.data = data;
- node.pre = top;
- // 改变栈顶指针
- top = node;
- size++;
- return true;
- }
- @Override
- public T pop() {
- if (top != null) {
- Node node = top;
- // 改变栈顶指针
- top = top.pre;
- size--;
- return node.data;
- }
- return null;
- }
- /**
- * 将数据封装成结点
- */
- private final class Node {
- private Node pre;
- private T data;
- }
- }
两种实现的比较, 主要比较数据入栈和出栈的速度:
- package cn.edu.ujn.stack;
- public class Test {
- public static void main(String[] args) {
- testSpeed();
- }
- private static void testSpeed() {
- // 测试数组实现
- //MyStack<Person> stack = new MyArrayStack<Person>();
- // 测试链表实现
- MyStack<Person> stack = new MyLinkedStack<Person>();
- int num = 1000000;
- long start = System.currentTimeMillis();
- for (int i = 0; i < num; i++) {
- stack.push(new Person("xing", 25));
- }
- long temp = System.currentTimeMillis();
- System.out.println("push time: " + (temp - start));
- while (stack.pop() != null)
- ;
- System.out.println("pop time: " + (System.currentTimeMillis() - temp));
- }
- }
运行结果如下:
可见入栈、出栈速度MyArrayStack则有明显的优势.
为什么测试结果是这样的? 可能有些朋友的想法是：数组实现的栈应该具有更快的遍历速度, 但增删速度应该比不上链表实现的栈才对。但是栈中数据的增删具有特殊性: 只在栈顶入栈和出栈。也就是说数组实现的栈在增加和删除元素时并不需要移动大量的元素, 只是在数组扩容时需要进行复制。而链表实现的栈入栈和出栈时都需要将数据包装成Node或者从Node中取出数据, 还需要维护栈顶指针和前驱指针。
栈的应用举例
1.将10进制正整数num转换为n进制
- package cn.edu.ujn.stack;
- public class StackApp {
- /**
- * @param args
- */
- public static void main(String[] args) {
- //System.out.println(conversion4D2X(22, 2));
- //System.out.println(isMatch("[()]"));
- System.out.println(lineEdit("Hello #world"));
- }
- /**
- *栈的应用举例-将10进制正整数num转换为n进制
- * @param num 待转化十进制数
- * @param n 转化进制
- * @return
- */
- private static String conversion4D2X(int num, int n) {
- MyStack<Integer> myStack = new MyArrayStack<Integer>();
- Integer result = num;
- while (true) {
- // 将余数入栈
- myStack.push(result % n);
- result = result / n;
- if (result == 0) {
- break;
- }
- }
- StringBuilder sb = new StringBuilder();
- // 按出栈的顺序倒序排列即可
- while ((result = myStack.pop()) != null) {
- sb.append(result);
- }
- return sb.toString();
- }
- }
2.检验符号是否匹配.
'['和']', '('和')'成对出现时字符串合法. 例如"[][]()", "[[([]([])()[])]]"是合法的; "([(])", "[())"是不合法的.
遍历字符串的每一个char, 将char与栈顶元素比较. 如果char和栈顶元素配对, 则char不入栈, 否则将char入栈. 当遍历完成时栈为空说明字符串是合法的.
- /**
- * 栈的应用举例-检验符号是否匹配:
- * '['和']', '('和')'成对出现时字符串合法. 例如"[][]()", "[[([]([])()[])]]"是合法的; "([(])", "[())"是不合法的.
- * @param str
- * @return boolean
- */
- private static boolean isMatch(String str) {
- MyStack<Character> myStack = new MyArrayStack<Character>();
- char[] arr = str.toCharArray();
- for (char c : arr) {
- Character temp = myStack.pop();
- // 栈为空时只将c入栈
- if (temp == null) {
- myStack.push(c);
- }
- // 配对时c不入栈
- else if (temp == '[' && c == ']') {
- }
- // 配对时c不入栈
- else if (temp == '(' && c == ')') {
- }
- // 不配对时c入栈
- else {
- myStack.push(temp);
- myStack.push(c);
- }
- }
- return myStack.isEmpty();
- }
3.行编辑
输入行中字符'#'表示退格, '@'表示之前的输入全都无效.
使用栈保存输入的字符, 如果遇到'#'就将栈顶出栈, 如果遇到@就清空栈. 输入完成时将栈中所有字符出栈后反转就是输入的结果:
- /**
- * 栈的应用举例-行编辑:
- * 输入行中字符'#'表示退格, '@'表示之前的输入全都无效.
- * @param input
- * @return String
- */
- private static String lineEdit(String input) {
- MyStack<Character> myStack = new MyArrayStack<Character>();
- char[] arr = input.toCharArray();
- for (char c : arr) {
- if (c == '#') {
- myStack.pop();
- } else if (c == '@') {
- myStack.clear();
- } else {
- myStack.push(c);
- }
- }
- // StringBuffer线程安全，StringBuilder线程不安全效率高
- StringBuilder sb = new StringBuilder();
- Character temp = null;
- while ((temp = myStack.pop()) != null) {
- sb.append(temp);
- }
- // 反转字符串
- sb.reverse();
- return sb.toString();
- }
（9）剑指Offer——动态规划算法
什么是动态规划？
和分治法一样，动态规划（dynamic programming）是通过组合子问题而解决整个问题的解。
分治法是将问题划分成一些独立的子问题，递归地求解各子问题，然后合并子问题的解。
动态规划适用于子问题不是独立的情况，也就是各子问题包含公共的子子问题。
此时，分治法会做许多不必要的工作，即重复地求解公共的子问题。动态规划算法对每个子问题只求解一次，将其结果保存起来，从而避免每次遇到各个子问题时重新计算答案。
适用范围
最优性原理体现为问题的最优子结构特性。当一个问题的最优解中包含了子问题的最优解时，则称该问题具有最优子结构特性。
最优性原理是动态规划的基础。任何一个问题，如果失去了这个最优性原理的支持，就不可能用动态规划设计求解。
1.问题中的状态满足最优性原理。
2.问题中的状态必须满足无后效性。
所谓无后效性是指：“下一时刻的状态只与当前状态有关，而和当前状态之前的状态无关，当前状态是对以往决策的总结”。
动态规划算法的设计
两种方法：
自顶向下（又称记忆化搜索、备忘录）：基本上对应着递归函数实现，从大范围开始计算，要注意不断保存中间结果，避免重复计算
自底向上（递推）：从小范围递推计算到大范围
动态规划的重点
递归方程+边界条件
爬楼梯问题
一个人每次只能走一层楼梯或者两层楼梯，问走到第80层楼梯一共有多少种方法。
设DP[i]为走到第i层一共有多少种方法，那么DP[80]即为所求。很显然DP[1]=1, DP[2]=2（走到第一层只有一种方法：就是走一层楼梯；走到第二层有两种方法：走两次一层楼梯或者走一次两层楼梯）。同理，走到第i层楼梯，可以从i-1层走一层，或者从i-2走两层。很容易得到：
递推公式：DP[i]=DP[i-1]+DP[i-2]
边界条件：DP[1]=1 DP[2]=2
(a)自顶向下的解法：
- long long dp[81] = {0};/*用于保存中间结果否则会重复计算很多重复的子问题*/
- long long DP(int n)
- {
- if(dp[n])
- return dp[n];
- if(n == 1)
- return 1;
- if(n == 2)
- return 2;
- dp[n] = DP(n-1) + DP(n-2);
- return dp[n];
- }
(b)自底向上的解法：
- int i;
- long long dp[81]; /* 注意当n超过75时，结果值将超过int范围 */
- dp[1] = 1;
- dp[2] = 2;
- for(i=3; i <= 80; i++)
- dp[i] = dp[i-1] + dp[i-2];
最长上升子序列
对于序列：4 1 2 24，它的最长上升子序列是1 2 4，长度为3。
对于序列：4 2 4 25 6，它的最长上升子序列是2 4 5 6，长度为4。
设a[i]表示原序列，设DP[i]表示以第i个数结尾的最长上升序列的长度，那么很显然想导出DP[i]的值，需要在DP[k](1<=k<i)中找出满足a[k]<a[i]最大的一项。假设第kk项是我们找到的答案，那么第i个数就可以接在第kk个数之后，成为以第i个数结尾的最长升序列。如果没有找到答案，换言之第i个数比前面的数都要小，那么DP[i]=1，也即生成了从自己开始又以自己结尾的最长升序列。综上，我们很容易得出：
递推公式：DP[i]=max(DP[k]+1,DP[i]) 1<=k<i
边界条件：DP[i]=1 1<=i<=n
算法复杂度为O(n^2)
- void RiseSequence(int Array[], int num)
- {
- #define MAX_LENGTH 30
- struct
- {
- int SequenceValue; /* max length ending with this num */
- int PreviousIndex; /* record the previous number */
- }ArrayInfo[MAX_LENGTH], temp;
- int i;
- for(i = 0; i < num; i++)
- {
- int j;
- ArrayInfo[i].SequenceValue = 1;
- ArrayInfo[i].PreviousIndex = -1;
- for(j = 0; j < i; j++)
- {
- if(Array[j] < Array[i] && (ArrayInfo[j].SequenceValue + 1 > ArrayInfo[i].SequenceValue))
- {
- ArrayInfo[i].SequenceValue = ArrayInfo[j].SequenceValue + 1;
- ArrayInfo[i].PreviousIndex = j;
- }
- }
- }
- temp.SequenceValue = ArrayInfo[0].SequenceValue;
- for(i = 1; i < num; i++)
- {
- if(temp.SequenceValue < ArrayInfo[i].SequenceValue)
- {
- temp.SequenceValue = ArrayInfo[i].SequenceValue;
- temp.PreviousIndex = i;
- }
- }
- for(i = 0; i < temp.SequenceValue; i++)
- {
- printf("%d ", Array[temp.PreviousIndex]); /* in reverse order */
- temp.PreviousIndex = ArrayInfo[temp.PreviousIndex].PreviousIndex;
- }
- printf(" the max rising sequence length is %d ", temp.SequenceValue);
- }
最长公共子序列
给定两个序列X和Y，称序列Z是X和Y的公共子序列如果Z既是X的一个子序列，又是Y的一个子序列。例如，如果X={a,b,c,b,d,a,b} Y={b,d,c,a,b,a} 那么序列{b,c,a}就是X和Y的一个公共子序列，但是它并不是X和Y的最长公共子序列，因为它的长度为3。而同为X和Y公共子序列的{b,c,b,a}，长度为4，因为找不到长度为5或更大的公共子序列，所以X和Y的最长公共子序列长度就为4。
假设两个序列数组分别为a，b。定义f(i,j)为计算到a数组第i个数、b数组第j个数时所得到的最长公共子序列的长度。这时有两种情况：
1.假如a[i]=b[j]，那么f(i,j)=f(i-1,j-1)+1
2.假如a[i]!=b[j]，那么f(i,j)=max(f(i-1,j),f(i,j-1))
边界条件为：f(i,0)=0 1<=i<=len(a)
f(0,j)=0 1<=j<=len(b)
算法复杂度：O(n^2)，len(a)表示数组a的长度。
尾声
动态规划绝对不是一两篇文章可以讲清楚的。当然也不是通过一两道题目可以完全学会。学习的关键是用动规的思想去想问题，去设计状态转移方程式。
动态规划还有很多变形，如状态压缩，树形等等。
虽然通常我们用递归的方式分析动态规划问题，但最终都会基于循环去编码。
（10）剑指Offer——二分查找算法
前言
本片博文主要讲解查找算法的相关知识。重点介绍二分查找。
二分查找算法是在有序数组中用到的较为频繁的一种查找算法，在未接触二分查找算法时，最通用的一种做法是，对数组进行遍历，跟每个元素进行比较，其时间为O(n).但二分查找算法则更优，因为其查找时间为O(lgn)。
在面试的时候二分查找是用的比较多一种查找算法，如何在面试官面前快速准确得的写出代码决定你是否能够被录取。以前一直以为二分查找很简单，所以就没怎么重视，但是真要在面试官面前对着黑板手写出来，还是漏洞百出。
注
1.二分查找的时间复杂度是O(log(n))，最坏情况下的时间复杂度是O(n)。
2.二分查找的一个条件是待查询的数组是有序的，我们假设这里的数组是升序的。
3.二分查找的主要思路就是设定两个指针start和end分别指向数组元素的首尾两端，然后比较数组中间结点arry[mid]和待查找元素。如果待查找元素小于中间元素，那么表明带查找元素在数组的前半段，那么将end=mid-1，如果待查找元素大于中间元素，那么表明该元素在数组的后半段，将start=mid+1;如果中间元素等于待查找元素，那么返回mid的值。
譬如数组{1， 2， 3， 4， 5， 6， 7， 8， 9}，查找元素6，用二分查找的算法执行的话，其顺序为：
1.第一步查找中间元素，即5，由于5<6，则6必然在5之后的数组元素中，那么就在{6， 7， 8， 9}中查找；
2.寻找{6， 7， 8， 9}的中位数，为8，8>6，则6应该在8左边的数组元素中，那么就在｛6，7，8｝中查找；
3.寻找{6， 7， 8}的中位数，为7，7>6，则6应该在7左边的数组元素中，那么只剩下6，即找到了。
二分查找算法就是不断将数组进行对半分割，每次拿中间元素和goal进行比较。
源码
- package cn.edu.ujn.demo;
- public class BinarySearch {
- /**
- * @param args
- */
- public static void main(String[] args) {
- int [] array = {1,2,3,4,4,7,12};
- int len = array.length;
- //System.out.println(binarySearchRecursion(array, 7, array[0], array[len-1]));
- System.out.println(binarySearchRecursionNon(array, 7, array[0], array[len-1]));
- }
- /**
- * 二分查找(递归)
- * @param arry 递增数组
- * @param value 待查找数值
- * @param start 起始查找位置
- * @param end 末查找位置
- * @return
- */
- private static int binarySearchRecursion(int arry[],int value,int start,int end)
- {
- if(start > end)
- return -1;
- int mid=start + (end-start)/2;
- if(arry[mid] == value)
- return mid;
- else if(value < arry[mid])
- {
- end = mid - 1;
- return binarySearchRecursion(arry,value,start,end);
- }
- else
- {
- start = mid + 1;
- return binarySearchRecursion(arry,value,start,end);
- }
- }
- /**
- * 二分查找(非递归)
- * @param arry 递增数组
- * @param value 待查找数值
- * @param start 起始查找位置
- * @param end 末查找位置
- * @return
- */
- private static int binarySearchRecursionNon(int arry[],int value,int start,int end)
- {
- while(start <= end){
- int mid=start + (end-start)/2;
- if(arry[mid] == value)
- return mid;
- else if(value < arry[mid])
- {
- end = mid - 1;
- }
- else
- start = mid + 1;
- }
- return -1;
- }
- }
在轮转后的有序数组上应用二分查找法
之前我们说过二分法是要应用在有序的数组上，如果是无序的，那么比较和二分就没有意义了。
不过还有一种特殊的数组上也同样可以应用，那就是“轮转后的有序数组（Rotated Sorted Array）”。它是有序数组，取其中某一个数为轴，将其之前的所有数都轮转到数组的末尾所得。比如{7, 11, 13, 17, 2, 3, 5}就是一个轮转后的有序数组。非严格意义上讲，有序数组也属于轮转后的有序数组——我们取首元素作为轴进行轮转。
下边就是二分查找法在轮转后的有序数组上的实现（假设数组中不存在相同的元素）
- /**
- * 在轮转后的有序数组上应用二分查找法
- * @param array
- * @param low
- * @param high
- * @param target
- * @return
- */
- int searchInRotatedSortedArray(int array[], int low, int high, int target)
- {
- while(low <= high)
- {
- int mid = (low + high) / 2;
- if (target < array[mid])
- if (array[mid] < array[high]) // the higher part is sorted
- high = mid - 1; // the target would only be in lower part
- else // the lower part is sorted
- if(target < array[low]) // the target is less than all elements in low part
- low = mid + 1;
- else
- high = mid - 1;
- else if(array[mid] < target)
- if (array[low] < array[mid]) // the lower part is sorted
- low = mid + 1; // the target would only be in higher part
- else // the higher part is sorted
- if (array[high] < target) // the target is larger than all elements in higher part
- high = mid - 1;
- else
- low = mid + 1;
- else // if(array[mid] == target)
- return mid;
- }
- return -1;
- }
对比普通的二分查找法，为了确定目标数会落在二分后的哪个部分，我们需要更多的判定条件。但是我们还是实现了O(log n)的目标。
二分查找法的缺陷
二分查找法的O(log n)让它成为十分高效的算法。不过它的缺陷却也是那么明显的。就在它的限定之上：
必须有序，我们很难保证我们的数组都是有序的。当然可以在构建数组的时候进行排序，可是又落到了第二个瓶颈上：它必须是数组。
数组读取效率是O(1)，可是它的插入和删除某个元素的效率却是O(n)。因而导致构建有序数组变成低效的事情。
解决这些缺陷问题更好的方法应该是使用二叉查找树了，最好自然是自平衡二叉查找树了，自能高效的（O(n log n)）构建有序元素集合，又能如同二分查找法一样快速（O(log n)）的搜寻目标数。
注
我们知道在效率方面，传值调用要比传址调用来的低，因为传值调用要进行一次变量的拷贝，而传址调用则是直接对这个变量进行操作。因此在编程中我们应该尽量将参数改为传址调用。
（11）剑指Offer——贪心算法
一、基本概念
所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性。所谓无后效性是指：“下一时刻的状态只与当前状态有关，而和当前状态之前的状态无关，当前状态是对以往决策的总结”。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。
二、贪心算法的基本要素
1.贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
2.当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
三、贪心算法的基本思路
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的局部最优解合成原来解问题的一个解。
从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。
该算法存在的问题：
1. 不能保证求得的最后解是最佳的；
2. 不能用来求最大或最小解问题；
3. 只能求满足某些约束条件的可行解的范围。
四、贪心算法适用的问题
贪心策略适用的前提是：局部最优策略能导致产生全局最优解。
实际上，贪心算法适用的情况很少。一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。
五、贪心算法的实现框架
从问题的某一初始解出发；
while （能朝给定总目标前进一步）
{
利用可行的决策，求出可行解的一个解元素；
}
由所有解元素组合成问题的一个可行解；
六、贪心策略的选择
因为用贪心算法只能通过解局部最优解的策略来达到全局最优解，因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。
七、例题分析
[背包问题]
这是一个可以使用贪心算法解的题目，贪心解的确不错，可惜不是最优解。
有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A B C D E F G
重量 35 30 60 50 40 10 25
价值 10 40 30 50 35 40 30
分析：
目标函数： ∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150)
（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
（2）每次挑选所占重量最小的物品装入是否能得到最优解？
（3）每次选取单位重量价值最大的物品，成为解本题的策略。
值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后， 它就是一种高效的算法。
贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。
可惜的是，它需要证明后才能真正运用到题目的算法中。
一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：
（1）贪心策略：选取价值最大者。反例：
W=30
物品：A B C
重量：28 12 12
价值：30 20 20
根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。
（2）贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。
（3）贪心策略：选取单位重量价值最大的物品。反例：
W=30
物品：A B C
重量：28 20 10
价值：28 20 10
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选 择A，则答案错误。
［最大整数］
设有n个正整数，将它们连接成一排，组成一个最大的多位整数。
例如：n=3时，3个整数13，312，343，连成的最大整数为34331213。
又如：n=4时，4个整数7，13，4，246，连成的最大整数为7424613。
输入：n
N个数
输出：连成的多位数
算法分析：此题很容易想到使用贪心法，在考试时有很多同学把整数按从大到小的顺序连接起来，测试题目的例子也都符合，但最后测试的结果却不全对。按这种标准，我们很容易找到反例：12，121应该组成12121而非12112，那么是不是相互包含的时候就从小到大呢？也不一定，如12，123就是12312而非12123，这种情况就有很多种了。是不是此题不能用贪心法呢？
其实此题可以用贪心法来求解，只是刚才的标准不对，正确的标准是：先把整数转换成字符串，然后在比较a+b和b+a，如果a+b>=b+a，就把a排在b的前面，反之则把a排在b的后面。
java源程序：
- public static void main(String[] args){
- String str = "";
- ArrayList<String> array = new ArrayList<String>();
- Scanner in = new Scanner(System.in);
- System.out.println("Please input the number of data:");
- int n = in.nextInt();
- System.out.println("Please input the data:");
- while (n-- > 0) {
- array.add(in.next());
- }
- for(int i = 0; i < array.size(); i ++)
- for(int j = i + 1; j < array.size(); j ++){
- if((array.get(i) + array.get(j)).compareTo(array.get(j) + array.get(i)) < 0){
- String temp = array.get(i);
- array.set(i, array.get(j));
- array.set(j, temp);
- }
- }
- for(int i = 0; i < array.size(); i ++){
- str += array.get(i);
- }
- System.out.println("str=:"+str);
- }
- }
［均分纸牌］
有N堆纸牌，编号分别为1，2，…，n。每堆上有若干张,但纸牌总数必为n的倍数.可以在任一堆上取若干张纸牌,然后移动。移牌的规则为：在编号为1上取的纸牌，只能移到编号为2的堆上；在编号为n的堆上取的纸牌，只能移到编号为n-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如：n=4，4堆纸牌分别为：① 9 ② 8 ③ 17 ④ 6 移动三次可以达到目的：从③取4张牌放到④ 再从③取3张放到②然后从②去1张放到①。
输入输出样例：4
9 8 17 6
屏幕显示：3
算法分析：设a[i]为第i堆纸牌的张数（0<=i<=n），v为均分后每堆纸牌的张数，s为最小移动次数。
我们用贪心算法，按照从左到右的顺序移动纸牌。如第i堆的纸牌数不等于平均值，则移动一次（即s加1），分两种情况移动：
1．若a[i]>v，则将a[i]-v张从第i堆移动到第i+1堆；
2．若a[i]<v，则将v-a[i]张从第i-1堆移动到第i堆。
为了设计的方便，我们把这两种情况统一看作是将a[i]-v从第i堆移动到第i+1堆，移动后有a[i]=v; a[i+1]=a[i+1]+a[i]-v.
在从第i+1堆取出纸牌补充第i堆的过程中可能会出现第i+1堆的纸牌小于零的情况。
如n=3，三堆纸牌数为1 2 27 ，这时v=10，为了使第一堆为10，要从第二堆移9张到第一堆，而第二堆只有2张可以移，这是不是意味着刚才使用贪心法是错误的呢？
我们继续按规则分析移牌过程，从第二堆移出9张到第一堆后，第一堆有10张，第二堆剩下-7张，在从第三堆移动17张到第二堆，刚好三堆纸牌都是10，最后结果是对的， 我们在移动过程中，只是改变了移动的顺序，而移动次数不变，因此此题使用贪心法可行的。
Java源程序：
- public class Greed {
- public static void main(String[] args) {
- int n = 0, avg =0, s = 0;
- Scanner scanner = new Scanner(System.in);
- ArrayList<Integer> array = new ArrayList<Integer>();
- System.out.println("Please input the number of heaps:");
- n = scanner.nextInt();
- System.out.println("Please input heap number:");
- for (int i = 0; i < n; i++) {
- array.add(scanner.nextInt());
- }
- for(int i = 0; i < array.size(); i ++){
- avg += array.get(i);
- }
- avg = avg/array.size();
- System.out.println(array.size());
- System.out.println(avg);
- for(int i = 0; i < array.size()-1; i ++){
- s++;
- array.set(i+1, array.get(i+1)+array.get(i)-avg);
- }
- System.out.println("s:" + s);
- }
- }
贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪心算法与其他算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。
（12）剑指Offer——排序算法小结
前言
毕业季转眼即到，工作成为毕业季的头等大事，必须得认认真真进行知识储备，迎战笔试、电面、面试。
许久未接触排序算法了。平时偶尔接触到时自己会不假思索的百度，然后就是Ctrl+C、Ctrl+V，好点的话封装为一个排序工具供以后使用。这样的学习方法百害而无一益，只因自己缺少了思索，未能真正理解到算法的核心精髓所在。下面系统的对快速排序、堆排序、冒泡排序、插入排序、选择排序、归并排序、桶排序部分排序算法做一小结。望大家有所受益。
快速排序
介绍
快速排序采用的思想是分治思想。
快速排序是找出一个元素（理论上可以随便找一个）作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值都不小于基准值，如此作为基准的元素调整到排序后的正确位置。递归快速排序，将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正确位置，排序完成。所以快速排序算法的核心算法是分区操作，即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。
举例
移步博文《Java进阶(三十八)快速排序》。
编码
移步博文《Java进阶(三十八)快速排序》。
时间复杂度
最差O(N2),平均NlogN。
空间复杂度
N+1
堆排序
构建最大堆
介绍
利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。
操作过程如下：
1)初始化堆：将R[0..n-1]构造为堆；
2)将当前无序区的堆顶元素R[0]同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。
因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。
注意使用最小堆排序后是递减数组，要得到递增数组，可以使用最大堆。
举例
- public class HeapSortTest {
- public static void main(String[] args) {
- int[] data5 = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };
- print(data5);
- heapSort(data5);
- System.out.println("排序后的数组：");
- print(data5);
- }
- public static void swap(int[] data, int i, int j) {
- if (i == j) {
- return;
- }
- data[i] = data[i] + data[j];
- data[j] = data[i] - data[j];
- data[i] = data[i] - data[j];
- }
- public static void heapSort(int[] data) {
- for (int i = 0; i < data.length; i++) {
- createMaxdHeap(data, data.length - 1 - i);
- swap(data, 0, data.length - 1 - i);
- print(data);
- }
- }
- public static void createMaxdHeap(int[] data, int lastIndex) {
- for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
- // 保存当前正在判断的节点
- int k = i;
- // 若当前节点的子节点存在
- while (2 * k + 1 <= lastIndex) {
- // biggerIndex总是记录较大节点的值,先赋值为当前判断节点的左子节点
- int biggerIndex = 2 * k + 1;
- if (biggerIndex < lastIndex) {
- // 若右子节点存在，否则此时biggerIndex应该等于 lastIndex
- if (data[biggerIndex] < data[biggerIndex + 1]) {
- // 若右子节点值比左子节点值大，则biggerIndex记录的是右子节点的值
- biggerIndex++;
- }
- }
- if (data[k] < data[biggerIndex]) {
- // 若当前节点值比子节点最大值小，则交换2者得值，交换后将biggerIndex值赋值给k
- swap(data, k, biggerIndex);
- k = biggerIndex;
- } else {
- break;
- }
- }
- }
- }
- public static void print(int[] data) {
- for (int i = 0; i < data.length; i++) {
- System.out.print(data[i] + " ");
- }
- System.out.println();
- }
- }
时间复杂度
O(nlogn)
空间复杂度
O(1)
稳定性
不稳定
所属类别
简单选择排序的增强版，同属选择排序。
冒泡排序
介绍
临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,这样一趟过去后,最大或最小的数字被交换到了最后一位,然后再从头开始进行两两比较交换,直到倒数第二位时结束。
例子为从小到大排序,原始待排序数组| 6 | 2 | 4 | 1 | 5 | 9 |
第一趟排序(外循环)
第一次两两比较6 > 2交换(内循环)
交换前状态| 6 | 2 | 4 | 1 | 5 | 9 |
交换后状态| 2 | 6 | 4 | 1 | 5 | 9 |
第二次两两比较,6 > 4交换
交换前状态| 2 | 6 | 4 | 1 | 5 | 9 |
交换后状态| 2 | 4 | 6 | 1 | 5 | 9 |
第三次两两比较,6 > 1交换
交换前状态| 2 | 4 | 6 | 1 | 5 | 9 |
交换后状态| 2 | 4 | 1 | 6 | 5 | 9 |
第四次两两比较,6 > 5交换
交换前状态| 2 | 4 | 1 | 6 | 5 | 9 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |
第五次两两比较,6 < 9不交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |
第二趟排序(外循环)
第一次两两比较2 < 4不交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |
第二次两两比较,4 > 1交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |
第三次两两比较,4 < 5不交换
交换前状态| 2 | 1 | 4 | 5 | 6 | 9 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |
第四次两两比较,5 < 6不交换
交换前状态| 2 | 1 | 4 | 5 | 6 | 9 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |
第三趟排序(外循环)
第一次两两比较2 > 1交换
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |
第二次两两比较,2 < 4不交换
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |
第三次两两比较,4 < 5不交换
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |
第四趟排序(外循环)无交换
第五趟排序(外循环)无交换
排序完毕,输出最终结果1 2 4 5 6 9
举例
- package cn.edu.ujn.sort;
- public class bubbleSort {
- public static void main(String[] args) {
- int[] a = { 6, 2, 4, 1, 5, 9 };
- int n = a.length;
- for(int i = 0; i < n; i++)
- System.out.print(a[i] + " ");
- bubble_sort(a,n);
- System.out.println("");
- for(int i = 0; i < n ;i++)
- System.out.print(a[i] + " ");
- }
- static void bubble_sort(int[] unsorted, int n)
- {
- for (int i = 0; i < n; i++)
- {
- for (int j = i; j < n; j++)
- {
- if (unsorted[i] > unsorted[j])
- {
- int temp = unsorted[i];
- unsorted[i] = unsorted[j];
- unsorted[j] = temp;
- }
- }
- }
- }
- }
结果如下:
时间复杂度
最坏情况O(N2),平均O(N2)。
空间复杂度
O(1)
插入排序
介绍
插入排序非常类似于整扑克牌。
在开始摸牌时，左手是空的，牌面朝下放在桌上。接着，一次从桌上摸起一张牌，并将它插入到左手一把牌中的正确位置上。为了找到这张牌的正确位置，要将它与手中已有的牌从右到左地进行比较。无论什么时候，左手中的牌都是排好序的。
如果输入数组已经是排好序的话，插入排序出现最佳情况，其运行时间是输入规模的一个线性函数。如果输入数组是逆序排列的，将出现最坏情况。平均情况与最坏情况一样，其时间代价是O(n2)。
也许你没有意识到，但其实你的思考过程是这样的：现在抓到一张7，把它和手里的牌从右到左依次比较，7比10小，应该再往左插，7比5大，好，就插这里。为什么比较了10和5就可以确定7的位置？为什么不用再比较左边的4和2呢？因为这里有一个重要的前提：手里的牌已经是排好序的。现在我插了7之后，手里的牌仍然是排好序的，下次再抓到的牌还可以用这个方法插入。编程对一个数组进行插入排序也是同样道理，但和插入扑克牌有一点不同，不可能在两个相邻的存储单元之间再插入一个单元，因此要将插入点之后的数据依次往后移动一个单元。
与选择排序不同的是，插入排序将数据向右滑动，并且不会执行交换。
稳定
最差情况：反序，需要移动n*(n-1)/2个元素
最好情况：正序，不需要移动元素
数组在已排序或者是“近似排序”时，插入排序效率的最好情况运行时间为O(n)；
插入排序最坏情况运行时间和平均情况运行时间都为O(n2)。
通常，插入排序呈现出二次排序算法中的最佳性能。
对于具有较少元素（如n<=15）的列表来说，二次算法十分有效。
在列表已被排序时，插入排序是线性算法O(n)。
在列表“近似排序”时，插入排序仍然是线性算法。
在列表的许多元素已位于正确的位置上时，就会出现“近似排序”的条件。
通过使用O(nlog2n)效率的算法（如快速排序）对数组进行部分排序，
然后再进行选择排序，某些高级的排序算法就是这样实现的。
举例
- public static void InsertSort(int[] arr)
- {
- int i, j;
- int n = arr.Length;
- int target;
- // 假定第一个元素被放到了正确的位置上
- // 这样，仅需遍历1 - (n-1)
- for (i = 1; i < n; i++)
- {
- j = i;
- target = arr[i];
- while (j > 0 && target < arr[j - 1])
- {
- arr[j] = arr[j - 1];
- j--;
- }
- arr[j] = target;
- }
- }
时间复杂度
O(n2)
空间复杂度
O(1)
选择排序
介绍
选择排序的思想非常直接，不是要排序么？那好，我就从所有序列中先找到最小的，然后放到第一个位置。之后再看剩余元素中最小的，放到第二个位置……以此类推，就可以完成整个的排序工作了。可以很清楚的发现，选择排序是固定位置，找元素。相比于插入排序的固定元素找位置，是两种思维方式。不过条条大路通罗马，两者的目的是一样的。
举例
- public static void selectSort(int[] arr)
- {
- int index, tmp, i, j, min;
- int len = arr.length;
- for(i = 0; i < len; i++){
- index = i;
- min = arr[i];
- for(j = i + 1; j < len; j++){
- if(min > arr[j]){
- min = arr[j];
- index = j;
- }
- }
- tmp = arr[i];
- arr[i] = min;
- arr[index] = tmp;
- }
- }
时间复杂度
O(n2)
从选择排序的思想或者是上面的代码中，我们都不难看出，寻找最小的元素需要一个循环的过程，而排序又是需要一个循环的过程。因此显而易见，这个算法的时间复杂度也是O(n*n)的。这就意味值在n比较小的情况下，算法可以保证一定的速度，当n足够大时，算法的效率会降低。并且随着n的增大，算法的时间增长很快。因此使用时需要特别注意。
空间复杂度
O(1)
归并排序
介绍
归并排序是建立在归并操作上的一种有效排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
首先考虑下如何将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。
归并排序和堆排序、快速排序的比较
若从空间复杂度来考虑：首选堆排序，其次是快速排序，最后是归并排序。
若从稳定性来考虑，应选取归并排序，因为堆排序和快速排序都是不稳定的。
若从平均情况下的排序速度考虑，应该选择快速排序。
举例
- //将有二个有序数列a[first...mid]和a[mid...last]合并。
- private static void mergearray(int a[], int first, int mid, int last, int temp[])
- {
- int i = first, j = mid + 1;
- int m = mid, n = last;
- int k = 0;
- while (i <= m && j <= n)
- {
- if (a[i] <= a[j])
- temp[k++] = a[i++];
- else
- temp[k++] = a[j++];
- }
- while (i <= m)
- temp[k++] = a[i++];
- while (j <= n)
- temp[k++] = a[j++];
- for (i = 0; i < k; i++)
- a[first + i] = temp[i];
- }
- private static void mergesort(int a[], int first, int last, int temp[])
- {
- if (first < last)
- {
- int mid = (first + last) / 2;
- mergesort(a, first, mid, temp); // 左边有序
- mergesort(a, mid + 1, last, temp); // 右边有序
- mergearray(a, first, mid, last, temp); // 再将二个有序数列合并
- }
- }
- public static void mergeSort(int a[])
- {
- int len = a.length;
- int[] p = new int[len];
- mergesort(a, 0, len - 1, p);
- }
时间复杂度
O(nlog2n)
归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树可以得出它的时间复杂度是O(nlog2n)。
空间复杂度
O(n)
算法处理过程中，需要一个大小为n的临时存储空间用以保存合并序列。
桶排序
介绍
1,桶排序是稳定的
2,桶排序是常见排序里最快的一种,比快排还要快…大多数情况下
3,桶排序非常快,但是同时也非常耗空间,基本上是最耗空间的一种排序算法
希尔排序
介绍
希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，它是直接插入排序算法的一种威力加强版。因DL．Shell于1959年提出而得名。
该方法的基本思想是：把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到1时，整个数据合成为一组，构成一组有序记录，则完成排序。
举例
- public static void shellSort(int a[])
- {
- int j, gap;
- int n = a.length;
- for (gap = n / 2; gap > 0; gap /= 2)
- for (j = gap; j < n; j++) // 从数组第gap个元素开始
- if (a[j] < a[j - gap]) // 每个元素与自己组内的数据进行直接插入排序
- {
- int temp = a[j];
- int k = j - gap;
- while (k >= 0 && a[k] > temp)
- {
- a[k + gap] = a[k];
- k -= gap;
- }
- a[k + gap] = temp;
- }
- }
附 常用排序算法的时间复杂度、空间复杂度对比
附 内排序和外排序
内排序：指在排序期间数据对象全部存放在内存的排序。
外排序：指在排序期间全部对象太多，不能同时存放在内存中，必须根据排序过程的要求，不断在内，外存间移动的排序。
根据排序元素所在位置的不同,排序分: 内排序和外排序。
内排序：在排序过程中，所有元素调到内存中进行的排序，称为内排序。内排序是排序的基础。内排序效率用比较次数来衡量。按所用策略不同，内排序又可分为插入排序、选择排序、交换排序、归并排序及基数排序等几大类。
外排序：在数据量大的情况下，只能分块排序，但块与块间不能保证有序。外排序用读/写外存的次数来衡量其效率。
对于内排序来说，排序算法的性能主要是受3个方面影响：
1．时间性能
排序是数据处理中经常执行的一种操作，往往属于系统的核心部分，因此排序算法的时间开销是衡量其好坏的最重要的标志。在内排序中，主要进行两种操作：比较和移动。比较指关键字之间的比较，这是要做排序最起码的操作。移动指记录从一个位置移动到另一个位置，事实上，移动可以通过改为记录的存储方式来予以避免（这个我们在讲解具体的算法时再谈）。总之，高效率的内排序算法应该是具有尽可能少的关键字比较次数和尽可能少的记录移动次数。
2．辅助空间
评价排序算法的另一个主要标准是执行算法所需要的辅助存储空间。辅助存储空间是除了存放待排序所占用的存储空间之外，执行算法所需要的其他存储空间。
3．算法的复杂性
注意这里指的是算法本身的复杂度，而不是指算法的时间复杂度。显然算法过于复杂也会影响排序的性能。
根据排序过程中借助的主要操作，我们把内排序分为：插入排序、交换排序、选择排序和归并排序。可以说，这些都是比较成熟的排序技术，已经被广泛地应用于许许多多的程序语言或数据库当中，甚至它们都已经封装了关于排序算法的实现代码。因此，我们学习这些排序算法的目的更多并不是为了去在现实中编程排序算法，而是通过学习来提高我们编写算法的能力，以便于去解决更多复杂和灵活的应用性问题。