算法的简单概况

1. 字典树(单词搜索树)

Trie是个简单但实用的数据结构，通常用于实现字典查询。我们做即时响应用户输入的AJAX搜索框时，就是Trie开始。本质上，Trie是一颗存 储多个字符串的树。相邻节点间的边代表一个字符，这样树的每条分支代表一则子串，而树的叶节点则代表完整的字符串。和普通树不同的地方是，相同的字符串前 缀共享同一条分支。还是例子最清楚。给出一组单词，inn, int, at, age, adv, ant, 我们可以得到下面的Trie：

可以看出：

考察前缀"a"，发现边a已经存在。于是顺着边a走到节点a。考察剩下的字符串"dd"的前缀"d"，发现从节点a出发，已经有边d存在。于是顺着边d走到节点ad考察最后一个字符"d"，这下从节点ad出发没有边d了，于是创建节点ad的子节点add，并把边ad->add标记为d。

Trie树属于树形结构，查询效率比红黑树和哈希表都要快。假设有这么一种应用场景：有若干个英文单词，需要快速查找某个单词是否存在于字典中。使用Trie时先从根节点开始查找，直至匹配到给出字符串的最后一个节点。在建立字典树结构时，预先把带有相同前缀的单词合并在同一节点，直至两个单词的某一个字母不同，则再从发生差异的节点中分叉一个子节点。

节点结构：

每个节点对应一个最大可储存字符数组。假设字典只存26个小写英文字母，那么每个节点下应该有一个长度为26的数组。换言说，可存的元素类型越多，单个节点占用内存越大。如果用字典树储存汉字，那么每个节点必须为数千个常用汉字开辟一个数组作为储存空间，占用的内存实在不是一个数量级。不过Trie树就是一种用空间换时间的数据结构，鱼和熊掌往往不可兼得。

Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。 Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

它有3个基本性质：

根节点不包含字符，除根节点外每一个节点都只包含一个字符。从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。每个节点的所有子节点包含的字符都不相同。 题目：给你个长度不超过10的单词。对于每一个单词，我们要判断他出没出现过，如果出现了，求第一次出现在第几个位置。

分析：这题当然可以用hash来解决，但是本文重点介绍的是trie树，因为在某些方面它的用途更大。比如说对于某一个单词，我们要询问它的前缀是否出现过。这样hash就不好搞了，而用trie还是很简单。

现在回到例子中，如果我们用最傻的方法，对于每一个单词，我们都要去查找它前面的单词中是否有它。那么这个算法的复杂度就是O(n^2)。显然对于的范围难以接受。现在我们换个思路想。假设我要查询的单词是abcd，那么在他前面的单词中，以b，c，d，f之类开头的我显然不必考虑。而只要找以a开头的中是否存在abcd就可以了。同样的，在以a开头中的单词中，我们只要考虑以b作为第二个字母的，一次次缩小范围和提高针对性，这样一个树的模型就渐渐清晰了。

注：效率比哈希高 时间复杂度为线性

【1】查找概论

查找表是由同一类型是数据元素（或记录）构成的集合。

关键字是数据元素中某个数据项的值，又称为键值。

若此关键字可以唯一标识一个记录，则称此关键字为主关键字。

查找就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。

查找分为两类：静态查找表和动态查找表。

静态查找表：只作查找操作的查找表。主要操作：

（1）查询某个“特定的”数据元素是否在查找表中。

（2）检索某个“特定的”数据元素和各种属性。

动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经已经存在的某个数据元素。 主要操作：

（1）查找时插入数据元素。

（2）查找时删除数据元素。

好吧！两者的区别： 静态查找表只负责查找任务，返回查找结果。

而动态查找表不仅仅负责查找，而且当它发现查找不存在时会在表中插入元素（那也就意味着第二次肯定可以查找成功）

顺序表 说的是存储的数据在逻辑和内存中是按顺序存放的 不代表整个数据是有序的 比如使用顺序表存储 1,2,5,3,67,23 这个是顺序表 但不是有序顺序表

【2】顺序表查找

顺序表查找又称为线性查找，是最基本的查找技术。 它的查找思路是：

逐个遍历记录，用记录的关键字和给定的值比较：

若相等，则查找成功，找到所查记录； 反之，则查找不成功。

顺序表查找算法代码如下：

对于这种查找算法，查找成功最好就是第一个位置找到，时间复杂度为O(1)。

最坏情况是最后一个位置才找到，需要n次比较，时间复杂度为O(n) 显然，n越大，效率越低下。

【3】有序表查找

所谓有序表，是指线性表的数据有序排列。

（1）折半查找

关于这个算法不做赘述，代码如下：

#include 
using namespace std;// 折半查找算法（二分查找） 
int Binary_Search(int* a,int n,int key)
{int low = 1, high = n, mid = 0;  // 初始化while (low <= high)    // 注意理解这里还有等于条件{mid = (low + high)/2; // 折半if (key < a[mid])high = mid -1;    // 最高小标调整到中位小一位else if (key > a[mid])low = mid + 1;    // 最低下标调整到中位大一位elsereturn mid;         // 相等说明即是}return 0;
}void  main ()
{int a[11] = {0,9,23,45,65,88,90,96,100,124,210};int n = Binary_Search(a,10, 9);if (n != 0)cout << "Yes:" << n << endl;elsecout << "No:" << endl;
}

折半查找算法的时间复杂度为O(logn)。

（2）插值查找

考虑一个问题：为什么是折半？而不是折四分之一或者更多呢？ 好吧，且看分解：

大家记不记得斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….（从第三个数开始，后边每一个数都是前两个数的和）

然后我们会发现，随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，利用这个特性，我们就可以将黄金比例运用到查找技术中。

大家请看：

4. 通过上面知道：数组a现在的元素个数为F[k]-1个，即数组长为F[k]-1。

mid把数组分成了左右两部分，左边的长度为：F[k-1]-1

那么右边的长度就为（数组长-左边的长度-1）： （F[k]-1）-（F[k-1]-1）= F[k]-F[k-1]-1 = F[k-2] - 1

5. 斐波那契查找的核心是：

a: 当key == a[mid]时，查找成功；

b:当key

即数组左边的长度，所以要在[low, F[k - 1] - 1]范围内查找；

c: 当key>a[mid]时，新的查找范围是第mid+1个到第high个，此时范围个数为F[k-2] - 1个，

即数组右边的长度，所以要在[F[k - 2] - 1]范围内查找。

关于斐波那契查找， 如果要查找的记录在右侧，则左侧的数据都不用再判断了，不断反复进行下去。

对处于中间的大部分数据，其工作效率要高一些。

所以尽管斐波那契查找的时间复杂度也为O(logn)，但就平均性能来说，斐波那契查找要优于折半查找。

可惜如果是最坏的情况，比如这里key=1，那么始终都处于左侧在查找，则查找效率低于折半查找。

还有关键一点：折半查找是进行加法与除法运算的（mid=(low+high)/2）

插值查找则进行更复杂的四则运算（mid = low + (high - low) * ((key - a[low]) / (a[high] - a[low]))）

而斐波那契查找只进行最简单的加减法运算（mid = low + F[k-1]-1）

在海量数据的查找过程中，这种细微的差别可能会影响最终的效率。

与二分查找相比，斐波那契查找算法的明显优点在于它只涉及加法和减法运算，而不用除法。因为除法比加减法要占去更多的机时，因此，斐波那契查找的平均性能要比折半查找好。

#include 
#include 
using namespace std;#define  MAXSIZE  11// 斐波那契非递归
void Fibonacci(int *f)
{f[0] = 0;f[1] = 1;for (int i = 2; i < MAXSIZE; ++i){f[i] = f[i-1] + f[i-2];}
}
// 斐波那契数列
/*---------------------------------------------------------------------------------|  0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  |  10  |  11  |  12  |----------------------------------------------------------------------------------|     0  |  1  |  1  |  2  |  3  |  5  |  8  |  13 |  21 |  34 |  55  |  89  |  144 |-----------------------------------------------------------------------------------*/
// 斐波那契数列查找
int Fibonacci_Search(int *a, int n, int key)
{int low = 1;  // 定义最低下标为记录首位int high = n; // 定义最高下标为记录末位（一般输入的参数n必须是数组的个数减一）int F[MAXSIZE];Fibonacci(F); // 确定斐波那契数列int k = 0, mid = 0;// 查找n在斐波那契数列中的位置，为什么是F[k]-1，而不是F[k]？while (n > F[k]-1){k++;}// 将不满的数值补全for (int i = n; i < F[k]-1; ++i){a[i] = a[high];}// 查找过程while (low <= high){mid = low + F[k-1] - 1; // 为什么是当前分割的下标？if (key < a[mid])  // 查找记录小于当前分割记录{high = mid - 1;k = k - 1;     // 注意:思考这里为什么减一位？}else if (key > a[mid]) // 查找记录大于当前分割记录{low = mid + 1;k = k - 2;  // 注意:思考这里为什么减两位？}else{return (mid <= high) ? mid : n;  // 若相等则说明mid即为查找到的位置； 若mid > n 说明是补全数值，返回n}}return -1;
}
void main()
{int a[MAXSIZE] = {0,1,16,24,35,47,59,62,73,88,99};  int k = 0;  cout << "请输入要查找的数字:" << endl;  cin >> k;int pos = Fibonacci_Search(a, MAXSIZE-1, k);  if (pos != -1)  cout << "在数组的第"<< pos+1 <<"个位置找到元素:" << k; else  cout << "未在数组中找到元素:" << k; 
}

首先要明确：如果一个有序表的元素个数为n,并且n正好是（某个斐波那契数 - 1），即n=F[k]-1时，才能用斐波那契查找法。 如果有序表的元素个n不等于（某个斐波那契数 - 1），即n≠F[k]-1，这时必须要将有序表的元素扩展到大于n的那个斐波那契数 - 1才行，这段代码：

for (int i = n; i < F[k] - 1; i++)

a[i] = a[high];

便是这个作用。

下面回答

第一个问题：看完上面所述应该知道①是为什么了吧。 查找n在斐波那契数列中的位置，为什么是F[k] - 1,而不是F[k]，是因为能否用斐波那契查找法是由F[k]-1决定的，而不是F[k]。如果暂时不理解，继续看下面。

第二个问题：a的长度其实很好估算，比如你定义了有10个元素的有序数组a[20]，n=10，那么n就位于8和13，即F[6]和F[7]之间，所以k=7，此时数组a的元素个数要被扩充，为：F[7] - 1 = 12个； 再如你定义了一个b[20]，且b有12个元素，即n=12,那么很好办了，n = F[7]-1 = 12, 用不着扩充了； 又或者n=8或9或11，则它一定会被扩充到12； 再如你举的例子，n=13，最后得出n位于13和21，即F[7]和F[8]之间，此时k=8，那么F[8]-1 = 20,数组a就要有20个元素了。 所以，n = x（=p;

p->pre=s;

删除：

删除 p 节点

p->pre->next=p->next;

p->next->pre=p->pre;

free(p)；

深度优先遍历

属于图的遍历，使用栈

广度优先遍历

属于图的遍历，使用队列

树

由若干节点组成的一个有层次关系的数据结构，比如说二叉树，可以有0个，1个，2个子节点，最多有两个节点。

二叉树的遍历

先序遍历: DLR 相当于深度优先遍历，

递归实现:

如果结点指针不为NULL,先打印结点值，然后分别递归左子结点和右子节点

非递归实现：

当前节点进栈并打印，进入该结点的左子树，重复直到当前节点为空

如果栈不为空，则出栈，访问该结点的右子树

中序遍历: LDR

递归实现:

如果结点指针不为NULL,先递归左节点，然后分别打印节点值和递归右子节点

非递归实现：

当前节点进栈，进入其左子树，重复直到当前节点为空

如果栈不为空，出栈，打印该节点，遍历该结点的右子树

后序遍历: LRD

递归实现:

如果结点指针不为NULL,先递归左节点，再递归右子节点，最后打印节点值

非递归实现：

当前节点进栈，进入其左子树，重复直到当前节点为空

如果栈不为空， 判断栈顶元素的右子树是否为空，如不为空，则访问，为空栈顶节点出栈

层次遍历: 从根节点开始按层遍历 相当于广度优先遍历

递归实现:

先求树的深度，然后使用循环，以根节点和深度作为参数，调用递归函数，递归函数里，深度小于1，就结束，深度等于1时，才可以打印，大于1，进行递归，分别对根节点的做孩子和右孩子进行递归。

非递归实现:

使用队列，遍历节点，然后将根结点加入队列，判断队列是否为空，不为空，将队列首个结点取出，分别将该结点的左右孩子结点加入队里，依次实现

递归与循环的区别:

递归:

方便了程序员，难为了机器

优点: 代码简洁，清晰，代码可读性好

缺点: 1. 递归是函数调用，函数调用是有时间和空间的消耗，每一次函数的调用，都需要在用户栈(我们编写的程序属于用户程序)中保存参数、函数的返回地址及临时变量，而且往栈里压数据是需要时间的，导致递归效率不高

2. 递归有很多重复的计算，递归的本质就是将一个问题分解成多个小问题，如果多个小问题存在相互重叠的部分，那就存在重复计算的部分

3. 栈溢出，如果函数调用的层级太多，，就会超出栈的容量(或者如果没加控制，将会造成栈溢出)

递归的优化: 使用尾递归，尾递归和递归本质的区别是:递归入栈后再进行收缩，而尾递归占用恒量的内存

尾递归就是一般递归必须等到下一级的函数调用返回后，本级函数才能得到结果，比如 f(n)依赖 f(n-1)，尾递归不需要依赖，尾递归将要返回的数据放在参数里，直到遇到结束条件，一层一层返回，不需要栈操作，所以速度快也不会造成栈溢出

循环

优点: 速度快

缺点: 代码可读性可能较差

两者效率比较:

一般是循环快，因为不需要函数调用和入栈操作，但现在使用尾递归后，效率差不多

两者的选用:

循环比较容易实现时，优先选循环，当很难建立循环方法时，使用递归(比如说:斐波那契数列用数列更简单，代码更简洁)

浮点数相加结果为什么有误差？

因为二进制代码无法准确表示浮点数的十进制数据，十进制浮点数转成二进制会有精度缺失，float转成二进制后，整数和小数部分的二进制代码只能包含23位，即使最多只能存储52位

目前无法从根本解决这个问题，但是可以曲线解决这个问题

先将小数乘以10或100转成整数，进行运算，然后除以10或100等获得结果

对一个空的对象，求,值为多少？

一个空对象，不包含任何信息，本来应该是0，但是对象占用占用一定的内存空间，占多大内存由编译器决定，在 VC中，一个 c++对象值为1字节，在 xocde 中，OC 对象值为8(指针大小为16字节)

如果在该类中添加一个构造函数和析构函数，求 ,值为多少？

还是1，调用这两个函数只需要知道地址就行，编译器不会因为有这两个函数在实例内添加额外的信息

那如果把析构函数标记为虚函数呢？

复制构造函数的参数不可为自身对象，因为实参对象传递给形参会调用复制构造函数，这样会造成死递归，而导致栈溢出

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序，请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数

因为二维数组中的数据排列是有规律的，所以将要查找的数与数组右上角的数进行比较，如果比右上角的数小，则去除该数所在的列，如果比右上角的数大，则去除该数所在列，如果相等，即找到

测试用例: 数组中没有要查找的数，输入空指针，数组中有要查找的数

(二维数组在内存中是顺序存储的)

字符串

c/c++的所有字符串都是以’\0’结尾的，所以要注意，这块容易越界

为了节省内存，字符串在内存的常量区，当多个指针指向用一个字符串时，该指针的地址是相同的，

一个算法要考虑哪些？

时间效率

是否会有内存覆盖

解决问题的方案

特殊的测试用例(是否为空指针等)

替换空格

请实现一个函数，把字符串中的每个空格替换成”%20”,例如输入”we are happy”,则输出”we%20are%"

空格的ASCII码是32，即十六进制的0x20,因此空格被替换为%20

解决方案: 时间复杂度O(n)

在原字符串的基础上替换，原字符串有足够的空间，先统计字符串中的空格个数，计算出替换之后字符串的长度，用到两个指针，第一个指针指向原字符串的尾部，第二个指针指向替换后字符串的首部，两个指针同时从后向前移动，直到第一个指针碰到空格，将空格替换成%20，第一个指针向前移动一格，第二个指针向后移动3格，重复这个步骤，直到第一个指针为 NULL。只需要一层循环，

测试用例: 输入的字符串没有空格，字符串是个NULL指针，字符串是个空字符串，字符串中有多个连续的空格

有两个排序的数组A1和A2，内存在A1的末尾有足够多的控件容纳A2, 请实现一个函数，把A2中的所有数字插入到A1中并且所有的数字是排序的

先计算 A2的大小，找到排序后的数组长度，需要三个指针，从后向前比较两个数组中的数字,大的插入到 A1的尾部，直到两个数组中的值都排完

时间复杂度: 线性

测试用例: 数组首地址是否为 NULL,数组是否为空，对相同的数字的处理

解决方案: 从后向前比较两个数组，将大的数字放在尾部

内存覆盖: 没有

输入一个链表的头结点，从尾到头打印出链表节点的每一个值

首先要看能不能改变链表结构，如果可以的话，先对链表进行逆序，再打印，如果不可以，就使用栈和递归都可以

栈: 遍历链表，将链表的所有节点入栈，再出栈打印

递归: 递归本质就是栈结构，所以可以用栈，就可以使用递归，每次访问一个节点时，先递归它的后一个节点，待它递归返回后，再打印本节点

时间复杂度: 线性

测试用例: 链表首地址为NULL, 链表只有一个节点

解决方案: 使用栈和递归

重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树，例如，前序遍历序列{1,2,4,7,3,5,6,8},中序遍历序列{4,7,2,1,5,3,8,6}

先找前序遍历的第一个节点，该结点为根节点，通过根节点，将中序遍历的节点分为左右子树，然后递归构建

时间复杂度:

测试用例: 二叉树是完全二叉树(倒数第二层必须是满的，最后一层，必须从左到右排列)，满二叉树(没一层都必须是满的)

解决方案: 每次寻找根节点+递归

用两个栈实现一个队列，并实现出队、入队函数

栈1存放插入进来的数据，栈2负责出队，入队都从栈1入栈，出队，查看栈2是否为空，不为空就弹出栈顶元素，为空就将栈1的所有数据，逐个压入栈2.

时间复杂度: 常数级 O(1)

测试用例: 两个栈都为空出队，两个栈都满入队，

解决方案: 两个栈

用两个队列实现一个栈

先将数据加入队列1，出栈就队1的数据除了最后一个数，其他的都出队，加入队2，队1的数据出队，如果继续出栈，就将队2的数据除了最后一个，全部出队加入队1，队2的数据出队，再入栈数据时，看哪个队列中有数据，就在哪个队里中入队。

时间复杂度：常数级 O(1)

测试用例: 栈为空时出栈，栈满时入栈

解决方案: 两个队列(也可以使用数组，链表)

旋转数组的最小数字

把一个数组最开始的若干元素搬到数组的末尾，称为数组的旋转，输入一个递增排序的数组的旋转，输出旋转数组的最小元素，例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1

需要两个指针，第一指针指向数组首，第二指针指向数组尾，求p1与p2的中间元素，如果中间元素大于p1指向的元素，说明中间元素在前面的数组中， 将p1指向中间元素，然后再求p1,p2的中间元素，如果中间元素小于p2指向的元素，说明中间元素在后面数组中，p2指向中间元素，直到p1,p2相邻，指向相邻的元素，则p2就是最小的元素

如果有0个元素旋转，怎么办？

在开始处判断，如果第一个元素小于最后一个元素，则第一个元素就是最小的元素

如果p1,p2,中间元素指向的元素相同，怎么处理？

顺序查找

时间复杂度: 常数级 O(1), 顺序查找为线性 O(n)

测试用例: 数组为空，数组首指针为NULL,旋转0个元素，p1,p2,p3指针指向的元素相同

解决方案: 求p1,p2的中间元素，与p1或 p2进行比较，让 p1,p2指向中间元素，重复这个步骤，

斐波那契数列

写一个函数，输入n,求斐波那契数列的第n项

一般的递归效率太低了，重复计算太多了，所以使用循环可以解决

扩展: 还可使用数学公式计算矩阵的乘方

时间复杂度: 线性 O(n)

测试用例： 功能测试

一只青蛙一次可以跳上1级台阶，也可以跳2级台阶，求该青蛙跳上一个n级的台阶总共有多少跳法

当第一次跳一级，则有f(n-1)种跳法，当第一次跳两级，则有f(n-2)种跳法，则f(n)=f(n-1)+f(n-2)

一只青蛙一次可以跳上1级台阶，也可以跳2级台阶，也可以跳n级台阶，求该青蛙跳上一个n级的台阶总共有多少跳法

f(n)=f(n-1)+ f(n-2)+f(n-3)+…f(1);

而 f(n-1)=f(n-2)+f(n-3)+…f(1);

所以 f(n)=2f(n-1) 所以由数学归纳法: f(n)=2^(n-1)

我们可以用2*1的小矩形横着或竖着去覆盖更大的矩形，请问用8个2*1的小矩形五重复地覆盖一个2*8的大矩形。总共有多少方法？

覆盖时有两种方式要不横着放要不竖着放，如果横着放，下面得横着放个，右边是2*6矩形，竖着放右边有个2*7的矩形，因此 f(8)=f(7)+f(6),这是斐波那契数列

二进制中1的个数

数值与比它小1的数值相与，就会相当于去掉该值的二进制的最后一位1，那我只要统计循环次数就行了

int (int n)

int count=0;

while(n)

count++;

n=n&(n-1);

时间复杂度: 线性 O(n)

测试用例: 正数，负数，0.

解决方案: 将数与该数减一的值求与

用一条语句判断一个整数是不是2的整数次方

如果一个整数是2的整数次方，则该数的二进制只有一位1，只需要将该值与该值-1的值相与，结果为0，就是

输入两个整数m，n，计算需要改变m 的二进制中的多少位才能得到 n

将两个数进行异或运算，计算机计算结果中二进制1的位数

数值的整数次方

比如说: a^n=a^n/2* a^n/2 n为偶数

a^n=a^n-1/2* a^n-1/2*a n为奇数

根据这个公式，递归求解即可，

注意: 用右移运算符(>>1)代替除以2，用与运算符(&0x1==1)代替了求余，位运算效率比乘除的效率要高得多(位运算有底层的cpu指令支持)

底数不能为0，如果指数为-1，则0会成为分母(判断底数是不是0时，不能写base==0,在计算机内对浮点数的存储有误差，float只有23位， 只有52位，所以求两个小数的差的绝对值小于10^-7)

如果指数为负数，则先对负值进行求指数求绝对值，计算完结果再求倒数

测试用例: 底数和指数分别为正数，负数，0

打印1到最大的 n 位数

输入数字n,按顺序打印从1到最大的 n 位十进制数，比如输入3，则打印出1、2、3一直到最大的999

不能盲目打印，要考虑大数问题

在 O(1)时间删除链表结点

给定单向链表头指针和一个节点指针，定义一个函数在O(1)时间删除该结点，

将该结点的下一个节点的内容全部复制到该节点中，然后将该结点的next的指针指向下下一个节点，就会被删除

如果要删除的节点位是最后一个节点，怎么处理？

只能顺序查找

如果链表中只有一个节点，删除节点后，要将链表头指针置为NULL

测试用例：链表头指针为 NULL，给的节点指针为NULL，链表只有一个节点，给的节点是最后一个节点

调整数组顺序是奇数位于偶数前面

使用两个指针，第一个指针指向第一个元素，第二个指针指向最后一个元素，如果p1指向的是偶数，则看p2，p2指向是奇数的话，则交换如果 p1指向的是奇数，则向后移动 p1,直到p1指向偶数，如何p2指向的是偶数的话，向前移动直到p2指向奇数，p2在p1的前面时，结束，表示已经排好

扩展: 如果改为负数位于非负数的前面，怎么办？ 如果能被3整除的在前面，不能被整除的在后面，怎么处理呢？

将原来的的奇偶数的判断条件，改为函数指针，通过函数指针返回值判断，每次只需要修改函数即可

时间复杂度: 线性 O(n)

测试用例: 数组手地址为 NULL,全部都是偶数或奇数，奇数都在偶数前面，偶数都在奇数前面，数组只有一个元素

链表中倒数第K个节点

1. 使用栈

2. 使用两个指针，第一个指针指向首地址，第二个节点指向第k个节点，两个指针同时向后移动，第二个指针指向NULL时,第一指针就是倒数第k个节点

时间复杂度:O(n)

测试用例: 首地址为 NULL,k 为负数，节点的个数小于 k,

求链表的中间节点

如果节点个数为奇数，返回中间节点，如果节点个数为偶数，返回中间节点的任一个

用两个指针，第一个指针一次走一步，第二指针一次走两步，当第二个指针指向链表末尾时，第一个指针刚好走向中间节点(奇偶数都满足)

判断一个单向链表是否形成一个环形结构

我们用一个指针解决不了问题时，就用两个指针解决

反转链表

定义三个指针，分别指向当前的节点，当前节点的前一个和后一个节点，将该该结点的next指针指向前一个节点，保存后一个节点的地址

时间复杂度: O(n)

测试用例: 首地址为NULL，只有一个节点，有多个节点

合并两个排序的链表

用一个新的链表，分别将两个链表的节点进行比较，小的就加入新链表中，

时间复杂度: O(n)

测试用例: 链表的首地址为NULL，一个链表只有一个节点，节点的值相同

输入两颗二叉树A和B，判断B是不是A的子结构

第一步：在A树中找和 B树根节点一样的节点

第二步： 找到后，判断树 A中是否有和 B 树一样的结构

测试用例: 两棵树的根节点为 NULL,二叉树的所有节点只有左子树或者右子树

二叉树的镜像:

交换根节点的左右节点，只要遍历遇到节点就交换该节点的左右节点即可

测试用例: 根节点为 NULL,只有一个节点，只有左节点或只有右节点

判断一个数组是不是某二叉搜索树的后续遍历

在后续遍历的序列中，最后一个数字是根节点，根据根几点将数组氛围两部分，因为二叉搜索树，左边的节点都比右边的结点小，然后进行递归，左部分的最后一个数是做子树的根节点，继续分，在分的过程中，遇到不满足条件的就直接返回 false

测试用例：根结点为NULL,只有一个节点，

二叉树中和为某一值的路径

前序遍历，遇到的每个节点都入栈，遍历到叶子结点，栈的值总和还是不能满足，就出栈，直到栈的值总和满足某一值

可以用栈就可以用递归

测试用例: 根节点为NULL,只有一条满足条件，有多条满足条件，没有符合的条件

复杂链表的复制

每个结点除了有个 next 指针外，还有个指向任意结点的指针

1. 在原始链表上复制每个节点，用next连起来

2. 用哈希表存起来关系(A的mnext指向C,则 A’的mnext指向的就是C')

3. 将长链表拆分成两个链表(将奇数的节点用 next 连接起来， 将偶数的节点用 next 连接起来 )

测试用例: 链表的首地址为NULL，只有一个节点，mnext 指向自身

将二叉搜索树转换成双向链表，转成的双向链表是排好序的

对二叉搜索树进行中序遍历，对根节点的左子树先进行连接(此时左子树已经是排好序的双向链表了)，再对根节点的右子树再进行连接，再连接上根节点，使用递归

测试用例：根结点为NULL, 只有一个节点，只有左子树或右子树

数组中出现次数超过数组长度一半的数字

1. 对数组进行排序(快排)，中间数一定是出现超过一半的数字

2. 遍历数组时保存两个值，一个是数组中的数字，一个是次数，默认次数为1，当下一个数字与前一个数字相同时，次数+1，不相同时，如果次数为不为0， 则次数减1， 如果次数为0 ， 则将数字替换为下一个数字 ，次数为1.重复这个步骤，最后对应的次数就是1的数

时间复杂度: O(logn),O(n)

测试用例: 数组首地址为NULL，数组中只有一个数，数组中的值全部相同，不存在超过一半数字

连续子数组的最大和

如输入数组为{1,-2,3,10,-4,7,2,-5},

比如说第一个数字与第二数字的和小于0，将前面的和遗弃，从第三个数值开始，如果加上的值为负数，因为不知道后面的值是怎么样的，所以先将数值保存下来，有可能是最大的，只要和不小于0，就一直加，如果后面的值大于保存下来的值，就替换(只能保存一个最大值)

时间复杂度: 线性 O(n)

测试用例: 数组首地址为NULL，数组中只有一个元素，数组中全是证书或负数

第一个只出现一次的字符

如输入””，则输出’b'

先使用哈希表，将遍历的字符的次数存在value中,第二次遍历时，首先找到次数为1的字符就是第一个出现一次的字符

哈希表的大小为256，因为有256个字符

时间复杂度: O(n)

测试用例: 字符串地址为NULL，字符串中只有一个字符，字符串中只存在一次的字符，字符串中不存在只出现一次的字符

输入两个字符串，从第一个字符串删除第二个字符串中出现过的所有字符

用哈希表将第二个字符串的所有的所有字符，当我们遍历字符串1时，只需要O(1)就可以判断是否在字符串2中，即可删除

时间复杂度: O(n)

测试用例: 字符串地址为NULL，字符串2与1中的字符相同，字符串2与1中的字符全不同

删除字符串中的所有重复出现的字符，如：输入””,结果为”gole"

用哈希表，将遍历过的字符的 value设为1，后面的字符发现该字符 value 为1后，相同的字符删除

时间复杂度: O(n)

测试用例：字符串地址为NULL，没有重复的字符，全部重复，

在英语中，如果两个词中出现的字母相同，并且每个字母出现的次数相同，那么这两个单词互为变位词，例如 与 ,判断两个英语单词是否为变位词

使用哈希，为扫描到的字符的次数+1，第二次扫描时，对对应的字符的次数-1，最后如果字符的次数全部为0，则互为变为词

时间复杂度: O(n)

测试用例: 字符串地址为NULL，两个单词完全相同，两个单词长度不一样长

数组的逆序对

在数组中的两个数如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对，输入一个数组，求出这个数组中逆序对的总数

输入两个链表，找出它们的第一个公共节点

两种方式：

1. 使用栈，考虑到链表不一样长，使用栈很合适，每次从两个栈顶取出元素，直到取出的两个元素不一样，则前一个就是第一个公共节点 ，这种方式用空间换时间，时间复杂度为 O(n)

2. 先遍历两个链表，统计链表中节点的个数，将较长的链表先走两个链表长度差的步数，然后两个节点依次进行比较，直到遇到节点相同，则找到，时间复杂度：O(n) 这种方式不需要辅助栈，提高了空间利用率，

数字在排序数组中出现的次数

输入排序数组{1，2，3，3，3，3，4，5}和3，由于这个数字出现了4次，输出4

两种方式:

1. 哈希 (空间换时间)

2. 使用二分查找，因为数组是有序的，如果中间数大于k,则说明k在左子树，如果中间树小于k,说明 k 在右子树，如果相等，则判断中间数前一个数是不是与中间数相等，不相等说明中间数是第一个出现的数，相等说明，中间数不是第一个出现的数，则递归在左子树上找第一个数，右子树重复这个步骤(就是找第一个数和最后一个数)

时间复杂度: O(n)

测试用例: 数组地址为 NULL,数组中不存在这个数，数组中只有一个数，数组中只有一个这个数

二叉树的深度

输入一棵二叉树的根节点，从根节点到叶子节点依次经过的节点形成树的一条路径，最长的路径的长度为树的深度

二叉树的深度为左右子树中深度较大的值+1，

int ( *root)

if(root==NULL)

0;

int left=(root->left);

int right=(root->right);

(left>right)?(left+1):(right+1);

测试用例：根节点指针为 NULL，二叉树只有一个节点，只有左子树或右子树

判断一个二叉树是不是平衡二叉树

使用后续遍历效率高，因为每个节点只被遍历一次，从下向上遍历

一般的思路是:前序遍历到一个节点，求左右子树的深度，依次递归遍历节点，这种方式是从上向下遍历，遍历的节点不会重复

测试用例: 根节点指针为NULL,该树是平衡二叉树，不是平衡二叉树，所有子树没有右子树

数组中只出现一次的数字

一个整数数组除了两个数字外，其他数字都出现了两次，请写出程序找出只出现一次的数字，要求时间复杂度为O(n),空间复杂度为 O(1)

时间复杂度: 运行算法所需要的时间 空间 复杂度: 算法所需要的空间的大小 ,O(1)表示所占的空间不变

每个数字对自身求异或为0，基于这个思路，

1. 我们对这个数组内的所有数据相异或，因为是两个两个出现的，所以最后剩下两个只出现一次的数，最后得到的值比如说为0010

2. 说明最后两个数在第二位上的值不一样，根据第二位值，将数组的值分为两部分，再分别对各部分的值进行异或，最后各部分剩下的数就是只出现一次的数

翻转单词顺序

输入一个英文句子，翻转句子中单词的顺序，但单词内容顺序不会变，例如输入:”I am a .”,则输出”. a am I "

思路: 先翻转句子，再翻转句子中的单词

实现一个函数专门用于翻转字符串，先调用函数翻转整个句子，参数为句子的开始地址和结束地址，然后

=pend=pdata;

while(pend)

if(*==‘')

++;

pend++;

else if(*pend==‘‘||*pend==‘\0')

rever(,—pend);

=++pend;

else{

pend++;

测试用例: 字符串指针为NULL,字符串为空，句子中只有一个单词，句子中有多个单词

字符串的左旋转操作是字符串前面的若干字符转移到字符串的尾部，输入字符串””和数字2，该函数将返回左旋2位得到结果”"

也是通过翻转操作，先将数组分为两部分，一部分是ab，另一部分是cdefg，先对单词内部进行翻转，然后对整个字符串进行翻转

测试用例: 字符串指针为 NULL,字符串为空串，给出的数字越界(访问的内存不属于字符串)，

约瑟夫环

0,1,….n-1这 n 个数排列成一个圆圈，从数字0开始每次从这个圆圈里删除第 m 个数字，求出这个圆圈里剩下的最后一个数字

1. 使用循环链表，走m-1步删除一个结点(这种方式会造成重复的计算，时间复杂度为O(mn),每删除一个数需要m步运算，有 n 个数)

2. 使用递归公式，

f(n,m)={

0 (n=1)

(f(n-1,m)+m)%n (n>1)

1. 定义函数f(n,m),n 为剩下的总数，m为删除第m个元素，f(n,m)表示剩下的数字

2. 删除k后，序列从 k+1开始到k-1,k+1...n-1,0...k-1,映射的序列0,1,2...n-2

3. 记x为原来的序列，y 为映射后的数组，y=(x-k-1)%n,则 x=(y+k+1)%n

4. 所以f(n,m)=(f(n-1,m)+m)%n 在n>1时

时间复杂度: 线性 O(n)

求1+2+3...+n，要求不能使用乘除法，for,while,if,else,,case 等关键字及条件判断语句(A？B:C)

1. 使用静态变量，创建一个 n大的对象数组，会调用 n 次构造函数(++n,sum+=n), n,sum都是静态的

2. 使用函数指针，使用两个函数，一个起递归作用，一个起终止作用，递归函数中数组大小为2，存放的是函数指针，下标0，1分别调用终止函数，递归函数，使用!!n转换成0，1

不用加减乘除做加法

1. 对两个进行异或

2. 对两个数相与(只有两个位都为1，相与才为1，所以会有进位)，为异或值根据与的有1的位左移一位

时间复杂度: O(n)

将字符串转为整数(主要考虑健壮性)

对每位字符进行转换：‘0’为48

=*10+*-‘0’

注意: 1. 字符串地址为NULL(空指针) 0；

2. 字符串为空串(串里有’\0’), 0；

3. 如果为负数(判断第一个字符是否为负号，如果为负号将数字转换后，改为负数)

4. 在数字遍历中遇到’0’~’9’之外的字符， -1；

5. 两者都 0；怎么区分是哪个返回的，设置全局标志位flag即可

树中两个结点的最低公共祖先

1. 如果这个树是平衡二叉树，当两个节点与树的节点比较，树中的节点位于两个节点的范围内，则这个节点就是这两个树的公共祖先(因为这两个节点为该节点的左右子树上)，

注意: 如果两个节点一个是另一个的孩子时，当遍历到的节点是其中一个节点时，则就是这种情况，它的先序的前一个节点就是他们的公共祖先

2. 如果这个树不是二叉平衡树但是一颗二叉树，有指向父节点的指针，相当于双向链表,转换为两个链表求第一个公共节点

3. 如果这棵就是普通的树，先判断两个节点是否在根节点的子树中，如果是true,则继续判断是否在树的孩子节点的子树中，就这样一层一层找下去，直到返回false,则父节点就是最低公共祖先

这种方法会造成节点的重复计算，有更快的吗？（还有链表的最后公共节点）

找到从根节点到要找的两个节点的两条路径，路径存放在栈里(辅存)，统计路径的长度，大的减小的的差值，从较大的栈里先取出差值个树，然后两个两个节点进行比较，如果相同就是最低的公共节点

在一个无序的数组中，找第K大的数

1. 堆排(大数据量时，比如100亿，用堆排)

2. 选择冒泡(因为求第K大，比较 k趟就可以,所以时间复杂为O(NK)与NlogN相比，用哪个？ 如果k 较小的时候(k

3. 快排(大数据时){

1. 找到关键字，将数组分为两部分，右边的部分的值比左边的部分的值大

2. 如果k的值大于右边部分的大小，有两种可能,第一种是 k==+1，则是基准，第二种是k>+1，则第k大的数在左部分，求出左部分的第k-(+1)个数，使用快排思想+递归

3. 如果k的值小于右部分的大小，则继续使用递归在右部分找

4. 计数排序(线性排序，适合大数据量处理)

十进制转八进制

整数部分对8求余，按从上到下排列，直到整数部分为0，小数部分乘8，取整数，直到小数为0

整数部分: 入栈=N%8，N=N/8

小数部分: 入队(K取整数)=K*8，(k-整数)*8

如果整数为

不需要临时变量交换两个数

只针对数字，如果指针交换，必须用临时变量

1. a=a^b(异或)，b=a^b,a=a^b,

2. a=a+b,b=a-b,a=a-b.

3、 a=a*b,b=a/b,a=a/b;

快排的优化，