笔试面试算法-白红宇

笔试面试算法

阅读量：5140 次

发布时间：2019-06-13

本文共 16328 字，大约阅读时间需要 54 分钟。

算法题

排序算法

选择排序

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法。

插入排序

插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。

希尔排序

希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

冒泡排序

冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。

快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

归并排序

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

归并操作的工作原理如下：

第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置

第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

重复步骤3直到某一指针达到序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

堆排序

每一个节点都比他的子节点大（或都小），在调整堆中始终会将最大的（或最小的）换到末尾，换后再调整堆。

注意

①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。

②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止

特点

堆排序（HeapSort）是一树形选择排序。堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系（参见二叉树的顺序存储结构），在当前无序区中选择关键字最大（或最小）的记录

堆排序与直接选择排序的区别

直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。

堆排序可通过树形结构保存部分比较结果，可减少比较次数。

算法分析

堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。

堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。

由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。

堆排序是就地排序，辅助空间为O(1），

它是不稳定的排序方法。

二叉排序树

二叉排序树（Binary Sort Tree）又称二叉查找树。它或者是一棵空树；或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

二叉平衡书

单向右旋转（LL型）--在*a的左子树根节点的左子树上插入节点，*a的平衡因子1变成2。

单向左旋转（RR型）--在*a的右子树根节点的右子树上插入节点，*a的平衡因子由-1变成-2。

双向旋转（先左后右）（LR型）--在*a的左子树根节点的右子树上插入节点，*a的平衡因子由1变成2。

双向旋转（先右后左）（RL型）--在*a的右子树根节点的左子树上插入节点，*a的平衡因子由-1变成-2。

旋转操作的正确性由：保持二查顺序树的特性—中序遍历所得关键字序列自小到大有序。

最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci数列 1是根节点 F(n-1)是左子树的节点数量 F(n-2)是右子数的节点数量。

平衡二叉搜索树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。常用算法有红黑树、AVL、Treap、伸展树等。在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在O（log2n），大大降低了操作的时间复杂度。

http://baike.baidu.com/view/593144.htm

B-树

1.定义任意非叶子结点最多只有M个儿子；且M>2；

2.根结点的儿子数为[2, M]；

3.除根结点以外的非叶子结点的儿子数为[M/2, M]；

4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字,根节点至少一个关键字）；

5.非叶子结点的关键字个数=指向儿子的指针个数-1；

6.非叶子结点的关键字：K[1], K[2], …, K[m-1]，m<M+1；且K[i]< K[i+1] ；

7.非叶子结点的指针：P[1], P[2], …, P[m]；其中P[1]指向关键字小于K[1]的子树，P[m]指向关键字大于K[m-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；

8.所有叶子结点位于同一层；

B-树包括两个基本操作：（1）在B-树中找结点；（2）在结点中找关键字。前一查找在磁盘上进行的，后一查找在内存中进行。因此在磁盘上进行查找的次数、即待查关键字所在结点在B-书上的层次数，是决定B-树查找效率的首要因素。

B+树

B+树是应文件系统所需而出的一种B-树的变型树。一棵m阶的B+树和m阶的B-树的差异在于：

1.有n棵子树的结点中含有n-1个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点。

2.所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

3.所有的非终端结点可以看成是索引部分，结点中仅含其子树（根结点）中的最大（或最小）关键字。

通常在B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。

B+树的查找

对B+树可以进行两种查找运算：

1.从最小关键字起顺序查找；

2.从根结点开始，进行随机查找。

在查找时，若非终端结点上的剧组机等于给定值，并不终止，而是继续向下直到叶子结点。因此，在B+树中，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。其余同B-树的查找类似。

从B 树、B+ 树、B* 树谈到R 树

你有四个装药丸的罐子，每个药丸都有一定的重量，被污染的药丸是没被污染的药丸的重量+1。只称量一次，如何判断哪个罐子的药被污染了?

第一个药瓶拿1个

第二个药瓶拿2个

第三个药瓶拿3个

第四个药瓶拿4个

计算标准的10颗药重量，与现在的10颗药比较

如果重量多1，就是第一个药瓶污染了

如果重量多2，就是第二个药瓶污染了

如果重量多3，就是第三个药瓶污染了

如果重量多4，就是第四个药瓶污染了

一道关于飞机加油的问题，已知：每个飞机只有一个油箱，飞机之间可以相互加油（注意是相互，没有加油机）一箱油可供一架飞机绕地球飞半圈，问题：为使至少一架飞机绕地球一圈回到起飞时的飞机场，至少需要出动几架飞机？（所有飞机从同一机场起飞，而且必须安全返回机场，不允许中途降落，中间没有飞机场）

共5架飞机 1，2，3，4，5

1，2，3号飞机从起点A起飞逆时针飞到全程8分之1加油点D，3号机为其他两架加满油返航。

1，2号继续飞到全程4分之1加油点B，2号机为1号机加满油返航。

1号飞机继续飞行到全程一半F点时，4号飞机从起点A起飞顺时针飞到加油点C，正好接到1号飞机，将自己油箱的油分给1号机一半后掉头与1号机一起往E点飞。

同时5号飞机在起点起飞顺时针飞到E点与1，4号会合将自己油箱剩的油平分，全部回到起点。

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶，请问这只青蛙跳上n级的台阶总共有多少种跳法？

问题分析:

设青蛙跳上n级台阶的跳法为f(n)种.

设Fibonacci数列的第x项值为fibo(x).

(1)当n=1时,f(n)=1

(2)当n=2时,f(n)=2

(3)当n>2时,分析可知,在跳上第n级台阶前一步,必然是在第(n-1)或(n-2)级台阶,故有f(n) =f(n-1) + f(n-2); 依此类推...

则有:

f(n)

= f(n-1) + f(n-2)

= 2f(n-2) + f(n-3)

= 3f(n-3) + 2f(n-4)

= 5 f(n-4) + 3f(n-5)

= 8f(n-5) + 5f(n-6)

= ...

= fibo(x+1)f(n-x)+fibo(x)f(n-(x+1))

=...

= fibo(n-1)f(n-(n-2)) + fibo(n-2)f(n-(n-1))

= fibo(n-1)f(2) + fibo(n-2)f(1)

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分

1. 维护两个指针，P1指向数组的第一个数字，向后移动; P2指向数组的最后一个数字，向前移动。

2. 在指针相遇前，若P1指向数字是偶数，P2指向数字是奇数，则交换这两个数字

3. 把比较的逻辑部分抽取出来，实现解耦，以满足更多的比较，如把所有的负数放在非负数前面，能被3整除的数放在不能被3整除的数前面

4. 代码扩展性，可重用性

一个整数数组中除了两个数字外，其它数字都出现了两次，请找出这两个只出现了一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)

/**

* 任何一个数字异或它自己都等于０

* eg: {2,4,3,6,3,2,5,5}，异或得到的结果为0010，把数组拆分，按照倒数第二位是不是1，会拆分为{2,3,6,3,2}和{4,5,5}，再求异或即可得到结果

一个数组中，除了一个数字，其他数字都出现了两次，我们如何找出那个不同的数字，

我们想到了异或运算的性质：任何一个数字异或它自己都等于0 。也就是说，如果我们从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现一次的数字，因为那些出现两次的数字全部在异或中抵消掉了。

很简单，将所有的数字都异或，那么最终结果就是要找的数字，因为相同的数字异或结果就是0

那么现在来思考这个题目：

《编程之美》一书提供了一种方法，即将所有的数字进行一个异或，得到一个数字，然后以该数字的某非0为作为过滤位，将数组分为两个部分，此时出现一次的数字会分到不同的部分，现在的问题就已经转换为出现一次的情况：

算法如下：

[java] view plaincopyprint?

public int[]findTwoDiff(int[]a)

{

int[]result=new int[2];

inttemp=0;

intflag=1;

for(intt:a)

{

temp^=t;

}

while((temp&flag)==0)

{

flag<<=1;

}

for(intt:a)

{

if((t&flag)==1)

{

result[0]^=t;

}else

{

result[1]^=t;

}

returnresult;

}

输入一个字符串，打印出该字符串中字符的所有排列。如输入abc,则输出acb,bac,bca,cab,cba

将字符串分为两部分，一部分是字符串的第一个字符,另一部分是第一个字符外所有字符

用递归

输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的

public LinkNode merge(LinkNode linkNode1,LinkNodelinkNode2) {

if(linkNode1==null) {

return linkNode2;

}

if(linkNode2==null ) {

return linkNode1;

}

LinkNodemergedNode = null;

if(linkNode1.value < linkNode2.value ) {

mergedNode = linkNode1;

mergeNode.next = merge(linkNode1.next,linkNode2);

}

else {

mergedNode = linkNode2;

mergeNode.next = merge(linkNode1,linkNode2.next);

}

如何检查一个单向链表上是否有环?

1、最简单的方法, 用一个指针遍历链表, 每遇到一个节点就把他的内存地址(java中可以用object.hashcode())做为key放在一个hashtable中. 这样当hashtable中出现重复key的时候说明此链表上有环. 这个方法的时间复杂度为O(n), 空间同样为O(n).

2、使用反转指针的方法, 每过一个节点就把该节点的指针反向

看上去这是一种奇怪的方法: 当有环的时候反转next指针会最终走到链表头部; 当没有环的时候反转next指针会破坏链表结构(使链表反向), 所以需要最后把链表再反向一次. 这种方法的空间复杂度是O(1), 实事上我们使用了3个额外指针;而时间复杂度是O(n), 我们最多2次遍历整个链表(当链表中没有环的时候).

这个方法的最大缺点是在多线程情况下不安全, 当多个线程都在读这个链表的时候, 检查环的线程会改变链表的状态, 虽然最后我们恢复了链表本身的结构, 但是不能保证其他线程能得到正确的结果.

3、这是一般面试官所预期的答案: 快指针和慢指针

设置两个指针(fast, slow)，初始值都指向头，slow每次前进一步，fast每次前进二步，如果链表存在环，则fast必定先进入环，而slow后进入环，两个指针必定相遇。(当然，fast先行头到尾部为NULL，则为无环链表)

如果链表为存在环，如果找到环的入口点？

当fast若与slow相遇时，slow肯定没有走遍历完链表，而fast已经在环内循环了n圈(1<=n)。假设slow走了s步，则fast走了2s步（fast步数还等于s 加上在环上多转的n圈），设环长为r，则：2s = s +nr ; s= nr设整个链表长L，入口环与相遇点距离为x，起点到环入口点的距离为a。

a + x = nr ;

a + x = (n – 1)r +r = (n-1)r + L – a ;

a = (n-1)r + (L – a – x)(L – a – x)

为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点，于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。

判断两个单链表是否相交，如果相交，给出相交的第一个点（两个链表都不存在环）。

1.将其中一个链表首尾相连，检测另外一个链表是否存在环，如果存在，则两个链表相交，而检测出来的依赖环入口即为相交的第一个点。

2.如果两个链表相交，那个两个链表从相交点到链表结束都是相同的节点，我们可以先

遍历一个链表，直到尾部，再遍历另外一个链表，如果也可以走到同样的结尾点，则两个链表相交。这时我们记下两个链表length，再遍历一次，长链表节点先出发前进(lengthMax-lengthMin)步，之后两个链表同时前进，每次一步，相遇的第一点即为两个链表相交的第一个点。

实现一个函数，输入一个无符号整数，输出该数二进制中的1的个数。例如把9表示成二进制是1001，有2位是1，因此如果输入9，该函数输出2

解法1：利用十进制和二进制相互转化的规则，依次除余操作的结果是否为1 代码如下：

int Count1(unsigned int v)

{

int num = 0;

while(v)

{

if(v % 2 ==1)

{

num++;

}

v = v/2;

}

return num;

}

解法2：向右移位操作同样可以达到相同的目的，唯一不同的是，移位之后如何来判断是否有1存在。对于这个问题，举例：10100001，在向右移位的过程中，我们会把最后一位丢弃，因此需要判断最后一位是否为1，这个需要与00000001进行位“与”操作，看结果是否为1，如果为1，则表示当前最后八位最后一位为1，否则为0，解法代码实现如下，时间复杂度为O(log2v)。

int Count2(unsigned int v)

{

unsigned int num= 0;

while(v)

{

num += v& 0x01;

v >>=1;

}

return num;

}

解法3：利用"与"操作，不断清除n的二进制表示中最右边的1，同时累加计数器，直至n为0，这种方法速度比较快，其运算次数与输入n的大小无关，只与n中1的个数有关。如果n的二进制表示中有M个1，那么这个方法只需要循环k次即可，所以其时间复杂度O(M)，代码实现如下：

int Count3(unsigned int v)

{

int num = 0;

while(v)

{

v &=(v-1);

num++;

}

return num;

}

平行算法，思路：将v写成二进制形式，然后相邻位相加，重复这个过程，直到只剩下一位。以217（11011001）为例，有图有真相，下面的图足以说明一切了。217的二进制表示中有5个1。

代码如下：

int Count6(unsigned int v)

{

v = (v &0x55555555) + ((v >> 1) & 0x55555555) ;

v = (v &0x33333333) + ((v >> 2) & 0x33333333) ;

v = (v &0x0f0f0f0f) + ((v >> 4) & 0x0f0f0f0f) ;

v = (v &0x00ff00ff) + ((v >> 8) & 0x00ff00ff) ;

v = (v &0x0000ffff) + ((v >> 16) & 0x0000ffff) ;

return v ;

}

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。实现一个函数实现字符串左旋转操作的功能。eg 输入"abcdefg"和2，则结果为"cdefgab"

/**

* 先翻转成 ba + gfedc

* 再翻转bagfedc，即得cdefgab

请写出归并排序

package com.javamm.al.sort;

/**

* 算法复杂度O(nlogn),冒泡，插入，选择都需要O(n2),若n为10000,n平方100000000，nlogn为40000,若归并需要40s,

* 则插入排序需要28h 缺点：需要在存储器有另一个大小等于被排序的数据项目的数组,即要足够的空间思想：归并两个有序的数组

* 注意：类名请写成MergeSort

public class MergeSort {

public staticvoid recSort(int[] data, int left, int right) {

System.out.println("recSort,left:"+ left + " right:" + right);

if(left == right) {

return;

}

intcenter = (left + right) / 2;

// 递归左边

recSort(data,left, center);

// 递归右边

recSort(data,center + 1, right);

//merge

merge(data,left, center, right);

}

public staticvoid merge(int[] data, int left, int center, int right) {

System.out.println("merge,left:"+ left + " center: " + center

+" right: " + right);

int[]tmpData = new int[data.length];

int mid= center + 1;

intthird = left;

int tmp= left;

while(left <= center && mid <= right) {

if(data[left] <= data[mid]) {

tmpData[third++]= data[left++];

}else {

tmpData[third++]= data[mid++];

}

while(mid <= right) {

tmpData[third++]= data[mid++];

}

while(left <= center) {

tmpData[third++]= data[left++];

}

// 将tmpData中的内容复制回原数组

while(tmp <= right) {

data[tmp]= tmpData[tmp++];

}

public staticvoid main(String[] args) {

int[]data = { 3, 2, 1, 6, 0, 8 };

recSort(data,0, data.length - 1);

for(int i = 0; i < data.length; i++) {

System.out.print(data[i]+ " ,");

}

在英语中，如果两个单词中出现的字母相同，并且每个字母出现的次数也相同，那么这两个单词互为变位词(Anagram),如silent与listen,evil与live, 请完成一个函数，判断输入的两个字符串是不是互为变位词

/**

* 字符hash,扫描第一个字符串，每扫描到一个字符串，对应的值加1，然后再扫描第二个字符串，对应的值-1,最后若hash中的所有的值都为0,那么互为变位词

定义一个函数，删除字符串中所有重复出现的字符。如输入google,输出为gole

/**

* boolean型的字符hash,当扫描到g时，将g的ascii码103下标的标为true,下次再扫描到g时，即知重复

在字符串中找出第一个只出现一次的字符。eg: 输入“abaccdeff“，输出b

/**

* 根据ASCII码值作为数组下标，构造字符Hash

数组al[0,mid-1]和 al[mid,num-1]，都分别有序。将其merge成有序数组al[0,num-1]，要求空间复杂度O(1)

思路：由于要求空间复杂度为O(1)，故不能使用归并排序

1、遍历0～mid -1，将其与a[mid]相比较，若 a[mid] < a[i]; 则将其交换，进入2

2、循环遍历a[mid~length]，如果1中交换后a[mid] > a[mid+1] 则进行交换，进行插入排序，将a[mid]插入到正确位置

#include<iostream>

usingnamespace std;

voidInsertSort(int a[], int index, int length){

int temp;

for(int i = index; i<length; i++){

if(a[i] >= a[i+1]){

temp=a[i];

a[i]=a[i+1];

a[i+1]=temp;

}

void sort(int a[], int mid, int length){

int temp;

for(int i=0; i<=mid-1; i++){

if(a[mid] < a[i]){

temp = a[i];

a[i] = a[mid];

a[mid] = temp;

InsertSort(a, mid, length - 1);

}

intmain()

{

int a[11] ={1, 4, 6, 7, 10, 2, 3, 8, 9, 15,16};

sort(a,5,11);

for(int i=0;i <11; i++)

cout << a[i]<<" ";

return 0;

}

？？？深度搜索、广度搜索

？？？最短路径算法

字符串查找，文件大小超过内存，比如10G文件，怎样把效率提高？

可以用hashmap，这样比较的时候或者查找便会效率很高，对于超内存可以用文件分段。HashMap 的实例有两个参数影响其性能：初始容量和加载因子。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，通过调用 rehash 方法将容量翻倍。

有a和b两种试剂，a和b透明，a试剂和b试剂相遇会变色，同种试剂相遇不会变色，现在n只a试剂里混有一只b试剂，试剂变色检测要一小时，问你用最少的试管在一个小时内检测出那只b试剂。

取1、2、3三个，两个试管一个加1、2一个加2、3。若只有第一个变色则说明是a，若只有第二个说明是3，若两个都变色说明是2.所以需要试管的总数是2/3n向上取整个试管。

有一个二叉树，将它保存在一个文件里，如何存放，可以通过这个文件恢复二叉树。

1. 二叉树补全法，将这课二叉树补全，变成一颗完全二叉树，再使用数组进行存储，写入文件中。这样做需要在节点中增加一个属性，标记是否为补全的节点。

这种方法不太合理，因为使用了补全操作，对于一颗很不规则的二叉树，将会占用非常大的存储空间，并且修改了二叉树的属性。

2. 游标实现法。定义一个新的结构体，其中的left和right指针修改为结构体在数组中的位置。

就像下面这样，数组的第一个位置表示NULL位置，剩余的存放节点，left和right分别指向左右子节点所在数组索引。这是前序遍历递归调用得到的数组。

3. 二叉树位置描述实现。同2类似，不过这里没有左右子节点的指针，而是用一个整形来描述当前节点在一颗完全二叉树中的位置。显然，在上图这样的二叉树中，节点1的位置为1,节点2的位置为2，节点3的位置为3，节点4的位置为4，节点5的位置为6，依次类推。。。

依次，可以定义一个新的结构体描述节点信息，用于存储。

于是可以前序遍历递归调用，得到这样的一个数组。

恢复的时候，查找左右子节点，只需要查找p值2倍于自身以及2倍+1于自身的节点。

有n个集合，集合的元素都是整数，设计个算法找到这n个集合的交集。

redis里的set数据结构本质就是个dict(hash表), 所以可以利用本身就做过hash这点，交集算法主要步骤u如下：

1、对多个set集合根据集合大小排序，最小的排最前面，下标0，

2、得到最小set集合的迭代器，后面需要

3、遍历第二步得到的迭代器，本质上就是遍历最小的set集合中所有的元素，然后把每一步遍历得到的元素去其他set集合里查看是否存在，只要发现在一个集合中不存在就直接跳出，因为对其他集合(下标0到N)比较是按前面排序的顺序，即从第二小的集合比较，到最大集合。这样可以最大程度的提前跳出比较。当这个元素在其他集合都存在的时候，说明这个元素是交集中的值。

设计一个系统，实现用户收发不同公司blog的消息。

垃圾邮件过滤的算法。

1)收集大量的垃圾邮件和非垃圾邮件，建立垃圾邮件集和非垃圾邮件集。

2) 提取邮件主题和邮件体中的独立字串例如 ABC32，￥234等作为TOKEN串并统计提取出的TOKEN串出现的次数即字频。按照上述的方法分别处理垃圾邮件集和非垃圾邮件集中的所有邮件。

3) 每一个邮件集对应一个哈希表，hashtable_good对应非垃圾邮件集而hashtable_bad对应垃圾邮件集。表中存储TOKEN串到字频的映射关系。

4) 计算每个哈希表中TOKEN串出现的概率P=（某TOKEN串的字频）/（对应哈希表的长度）

5) 综合考虑hashtable_good和hashtable_bad，推断出当新来的邮件中出现某个TOKEN串时，该新邮件为垃圾邮件的概率。

6)建立新的哈希表hashtable_probability存储TOKEN串ti到P（A|ti）的映射

7) 至此，垃圾邮件集和非垃圾邮件集的学习过程结束。根据建立的哈希表 hashtable_probability可以估计一封新到的邮件为垃圾邮件的可能性。

有一些关键词点击次数的文件，如何输出最多点击的一百个

1)对于大文件，一般是分段读取的。

2)有很多关键字，又要统计关键字出现的次数，那么用键值对的方式，键是关键字，值是出现的次数，来保存比较合适。

3)识别关键字，要看你怎么定义【一个关键字】，一般没有空白字符分割的字符串就可以当做一个关键字了。

有些文件，频繁访问在磁盘里头的，现在要放到内存中了。采用什么策略来决定哪些放到内存中？如果是一些url文件，放在内存后，如何快速的找到某个url的位置（采用字典序或者b树之类树状结构来组织）如何快速找到哪些文件太久没人访问了，把他替换出去？

（再那一棵树，记录树里每个位置url的访问时间；同时，那个url树的节点，也有这个时间树的对应的位置信息。时间树采用最大堆组织。要替换出去时，就从树顶取走节点，并且从中获得这个节点在url树对应位置，把他从url树中取走。当url被访问时，由于url树节点有时间树的位置信息，所以也很快找到对应节点在时间树的位置，然后把他的访问时间更新，然后做堆调整，每次堆调整为logN）

2.5亿个int数，可能有相同的。统计出这里头不同的数有多少个？只有2g内存。

统计数-用hash，key是数，value是1或0，标记是否出现。

如果key就是那个数，那么找一个数的时候，要遍历hash才知道有没有，慢（就是如果hash紧凑，慢）。

解决方案：把key作为连续的（就是hash是稀疏的，有个key值没有存在这2.5亿个数中），像数组下标一样，那么要访问第n个数，直接到第n个去看，复杂度是O(1)

但是，如果连续，2.5亿个数，范围很广，而每个key用int存，会很大量，内存不一定够。

解决方案：每个key用一位bit来标志。即数字1放在第一个bit上，数字2放在第二个bit上。看第n位在不在，就找一下第n个bit是1，还是0

具体方法：char a[] 数组。假设找3，那么3在3/8--0...3,所以在a[0]中，找第3个bit，如果是0，就设置为1。最后看看a[]的二进制表示有多少个1就有多少个数

n个无序int，（有正有负），给一个数v，如何找出其中的a+b=v的两个数。

（我的答案是：排序 O(nlogn)，记录序列中，0，大于v，小于v的3位。

尝试最小的和最大的，最大不行，次大。。。，找到某个，加起来小于v了，停止尝试次小的，从上次大头停止的位置开始尝试---尝试范围两头不断缩小，复杂度为n）

设当前最小的数为a[0]最大数位a[n]

（1）先从最小数a[0]开始，如a[0]+ a[n]=v。得结果

（2）如果a[0]+ a[n]>v。比较a[0]+a[n-1].

（3） a[0]+a[n]<v。比较a[1]+ a[n]

先排序，将数组分为大于v和小于v的两段，比较两端数据的多少，从少端的第一个x开始，如果用y=v-x，查看y是否在数组中（折半查找）。

或者构建一棵树，根为v，左边为小于v的数，右边为大于v的数。

一个排好序的数组，找出两数之和为m的所有组合

设两个指针，左指针指向最小的数为a[0] ，右指针指向最大数位a[n]

（1）先从最小数a[0]开始，如a[0]+ a[n]=v。将这个结果记录下来，移动左指针（或又指针）

（2）如果a[0]+ a[n]>v。右指针左移一个数

（3） a[0]+a[n]<v。左指针右移一个数

知道右指针指向的数与左指针相同就退出

自然数序列，找出任意连续之和等于n的所有子序列

初始化两个指针，一个f；一个n。首先f指向序列的第一个元素，n指向第二个元素

判断f.data+n.data 与n的大小关系

（1）f.data+n.data = n将这个结果记录下来，将n右移到下一个数（不能移动f，因为有可能f移动到下一个指向的与n相同，造成结果不正确）。

（2）f.data+n.data > n 将f右移到下一个数,计算从f到n的数的和

（3）f.data+n.data < n将n右移到下一个数,计算从f到n的数的和

期间循环判断f和n的位置，f不能超过n当n为f的下一个时，约定n右移一位。

1到1亿的自然数，求所有数的拆分后的数字之和，如286 拆分成2、8、6，如1到11拆分后的数字之和 => 1 + ... + 9 + 1 + 0 + 1 + 1。

思路：递推方法求解：

*1.0-9的和为 a1=(0+9)*10/2

*2.0-99时：分析共有100个数，十位上有10对0-9，个位上也是10对0-9(讲个位数上填0补充)，

* 此时a2=2*10*(0+9)*10/2；

*3.0-999时：共有1000个数，百位上有10对0-9，十位上有10对0-9，个位上也是10对0-9，

* 此时a3=3*100*(0+9)*10/2;

* 依次类推：当位数为n时，有an=n*（10的n-1次方）*(0+9)*10/2;

N个bit，如和判断其中有多少个1.（时间复杂度小于N）

预存一个2的8次方大小的数组，每个数组值是，这个下标的数的二进制的1的个数，例如：

a[0]=0,a[1]=1, a[2]=1,a[3]=2....a[2^8-1]=7 （以空间换时间）

然后一个byte一个byte的读，看看他的值，直接以这个值为下标去数组看他的1的个数

查表。

另一个方法：

while(v){

v&= (v-1);

num++;

}

1000& 0111 = 0, 所以每&一次，不为0，说明有1个1，&到为0为止，num就是1的个数。复杂度为1的个数。

float型与0的比较

浮点数的表示是不精确的，不能直接比较两个数是否完全相等，一般都是在允许的某个范围内认为像个浮点数相等，如有两个浮点数a,b，允许的误差范围为1e-6，则abs(a-b)<=1e-6，即可认为a和b相等。还有一种方法就是扩大再取整，比如a=5.23,b=5.23,直接比较 a==b一般为false，但是a和b都扩大一百倍，然后强制转换为int类型，再用==比较就可以了

const float EPSINON = 0.00001;

if((x >= - EPSINON) && (x <= EPSINON))

EPSINON是允许的误差（即精度）

所以不可将float变量用“==”或“!=”与数字比较，应该设法转化成“>=”或“<=”形式。如果写成if （x == 0.0），则是错误的。