一、数组

1、查找数组中第2小的元素

（1）堆排序

（2）遍历找第一小的，第一小的存下来再遍历找第二小的

2、查找第一个没有重复的数组元素

（1）使用两个循环。外循环遍历，内循环检查有误重复

（2）哈希，将值映射到哈希数组中，若发生0->1->0的改变则说明是第一个重复的数组元素

3、合并两个排序的数组

（1）暴力

·创建大小为n1 + n2的数组arr3 []。

·将arr1 []的所有n1个元素复制到arr3 []

·遍历arr2 []和arr3 []到arr1 [] 的一对一插入元素（如插入排序）。此步骤需要O（n1 * n2）时间。

（2）Merge Sort函数

·创建大小为n1 + n2的数组arr3 []。

·同时遍历arr1 []和arr2 []。

·在arr1 []和arr2 []中拾取较小的当前元素，将此较小的元素复制到arr3 []中的下一个位置，然后在arr3 []中向前移动，并拾取其元素的数组。

·如果arr1 []或arr2 []中还有剩余元素，请将它们也复制到arr3 []中。

（3）使用STL  map

·将两个数组的元素插入映射中作为键。

·打印地图键。

4、重新排列数组中的正数和负数

先使用QuickSort的分区过程将正数和负数分开。在分区过程中，将0视为枢轴元素的值，以便将所有负数放在正数之前。一旦负数和正数分开，我们就从第一个负数和第一个正数开始，然后将每个备用负数与下一个正数交换。

二、栈

（1）使用栈计算后缀表达式

1）创建一个堆栈来存储操作数（或值）。

2）扫描给定的表达式，然后对每个扫描的元素执行以下操作。

…..a）如果元素是数字，则将其推入堆栈

…..b）如果元素是运算符，则从堆栈中弹出该运算符的操作数。评估运算符并将结果推回堆栈

3）表达式结束时，堆栈中的数字是最终答案

示例：

假定给定表达式为“ 2 3 1 * + 9-”。我们一一扫描所有元素。

1）扫描'2'，它是一个数字，因此将其压入堆栈。堆栈包含“ 2”

2）扫描“ 3”，再次是一个数字，将其推入堆栈，堆栈现在包含“ 2 3”（从下至上）

3）扫描“ 1”，再次是一个数字，将其推入堆栈，堆栈现在包含'2 31'

4）扫描'*'，它是一个运算符，从堆栈中弹出两个操作数，对操作数应用*运算符，得到3 * 1，结果为3。将结果'3'推入堆栈。堆栈现在变为'2 3'。

5）扫描'+'，它是一个运算符，从堆栈中弹出两个操作数，将+运算符应用于操作数，我们得到3 + 2，结果为5。将结果'5'推入堆栈。堆栈现在变为“ 5”。

6）扫描'9'，它是一个数字，我们将其压入堆栈。堆叠现在变为“ 5 9”。

7）扫描'-'，它是一个运算符，从堆栈中弹出两个操作数，将–运算符应用于操作数，我们得到5 – 9，结果为-4。我们将结果“ -4”压入堆栈。堆叠现在变为'-4'。

8）没有更多要扫描的元素，我们从堆栈中返回顶部元素（这是堆栈中剩下的唯一元素）。

（2）使用栈计算中缀表达式

1）使用两个栈，stack0用于存储操作数，stack1用于存储操作符

2)从左往右扫描，遇到操作数入栈stack0

…..a）遇到操作符时，如果优先级低于或等于栈顶操作符优先级，则从stack０弹出两个元素进行计算，并压入stack0，继续与栈顶操作符的比较优先级

…..b）如果遇到操作符高于栈顶操作符优先级，则直接入栈stack1

…..c）遇到左括号，直接入栈stack1，遇到右括号，则直接出栈并计算，直到遇到左括号

（https://zhuanlan.zhihu.com/p/60609567）

（3）中缀表达式转后缀表达式

先把中缀表达式转为后缀表达式，再入栈计算。

转化主要遵循以下原则：

1.遇到操作数，直接输出；

2.栈为空时，遇到运算符，入栈；

3.遇到左括号，将其入栈；

4.遇到右括号，执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出， 左括号也要弹出；

5.遇到其他运算符’+”-”*”/’时，弹出所有优先级大于或等于该运算符的栈顶元素，然后将该运算符入栈， 遇到左括号时不能再弹出；

6.最终将栈中的元素依次出栈，输出。

经过上面的步骤，得到的输出既是转换得到的后缀表达式。

（4）栈实现队列

....a)双栈

当调用 push 让元素入队时，只要把元素压入 s1 即可

那么如果这时候使用 peek 查看队头的元素怎么办呢？按道理队头元素应该是 1，但是在 s1 中 1 被压在栈底，现在就要轮到 s2 起到一个中转的作用了：当 s2 为空时，可以把 s1 的所有元素取出再添加进 s2，这时候 s2 中元素就是先进先出顺序了。

…..b）用两个堆栈实现一个队列

进列：直接在堆栈A后添加

出列：判断堆栈B是否为空，若为空，则将堆栈A中元素出栈后，压栈进入堆栈B。若栈B不为空，则直接出栈。

三、队列   

1、使用队列实现栈

可以使用两个队列来实现堆栈。

进栈：直接在队列A后添加元素

出栈：若队列A为空，则出栈元素为空。当队列A中只有1个元素直接出栈，否则将队列A中的元素出列压入队列B中，当A只剩下一个元素是出栈。再将AB队列交换，重复前面的操作，达到堆栈的效果。

2、倒换队列的前k个元素

使用辅助堆栈。

（1）创建一个空堆栈。Create an empty stack.

（2）从给定队列中逐一出队各个元素，并将出队元素推入堆栈。One by one dequeue items from given queue and push the dequeued items to stack.

（3）将堆栈的内容排入队列的后面。Enqueue the contents of stack at the back of the queue

（4）从前面使（size-k）元素出队，并将它们一个一地排入同一队列。Dequeue (size-k) elements from the front and enque them one by one to the same queue.

3、使用队列将1-n转换为二进制（运行一个从1到n的循环，在循环内调用十进制到二进制。）

使用队列数据结构来打印二进制数字。

1）创建一个空字符串队列。Create an empty queue of strings

2）将第一个二进制数字“ 1”排队。Enqueue the first binary number “1” to queue.

3）现在运行一个循环，以生成和打印n个二进制数。Now run a loop for generating and printing n binary numbers.

……a）出队并打印队头元素。 Dequeue and Print the front of queue.

……b）在队头元素后面添加“ 0”并将其入队。Append “0” at the end of front item and enqueue it.

……c）在队头元素后面添加“ 1”并将其排队。Append “1” at the end of front item and enqueue it.

四、链表

1、倒转一个链表

迭代

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

（1）将三个指针prev初始化为NULL，将curr初始化为head，将next初始化为NULL。

（2）遍历链表。循环执行以下操作。

//在更改当前

下一个节点之前，//存储下一个节点

next = curr-> next

//现在更改当前位置的下一个

// //这是实际反转发生的位置

curr-> next = prev

//移动分组和CURR一步向前

先前= CURR

CURR =下一个

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------

程序员小灰图解：

从链表头部开始，建立三个临时节点的引用，分别为p1，p2，p3。它们分别指向头节点、第二个节点、第三个节点。

1.以p2节点为视角，把p2节点原本指向p3的next指针倒转，指向p1。

2.三个临时节点引用p1，p2，p3分别向后移动一格位置。

3.重复第1步的工作，以p2节点为视角，把p2节点原本指向p3的next指针倒转，指向p1。

4.重复第2步的工作，三个临时节点引用p1，p2，p3分别向后移动一格位置。

5.继续像这样子迭代下去，一直到p2是空为止。

6.最后，把head节点的next指向空，成为逆序链表的尾节点。并且把p1赋值给head，让p1所在的节点成为逆序链表的头节点。

2、检查链表中是否存在循环

（1）哈希

遍历链表，并将节点地址始终放在哈希表中。在任何时候，如果达到NULL，则返回false，如果当前节点的下一个指向Hash中先前存储的任何节点，则返回true。

（2）通过修改链表数据结构，无需哈希图即可解决此问题。（此解决方案需要修改基本的链表数据结构）

每个节点都有一个访问标志。

遍历链接列表并继续标记访问的节点。

如果您再次看到一个访问过的节点，那么就会有一个循环。该解决方案适用于O（n），但每个节点都需要其他信息。

此解决方案的一种变体不需要修改基本数据结构，可以使用哈希来实现，只需将访问的节点的地址存储在哈希中，如果您看到哈希中已经存在的地址，则存在一个循环。

3、返回链表第n个元素

（1）使用链表的长度

 1）计算链表的长度。让长度为len。

2）从链接列表的开头打印第（len – n + 1）个节点。

（2）使用两个指针

双指针概念：

第一个指针用于存储变量的地址，第二个指针用于存储第一个指针的地址。如果我们希望通过函数更改变量的值，则将指针传递给它。并且，如果我们希望更改指针的值（即，它应该开始指向其他对象），则将指针传递给指针。

维护两个指针–参考指针和主指针。初始化引用和主指向head的指针。首先，将参考指针从头移到n个节点。现在将两个指针一一移动，直到参考指针到达终点为止。现在，主指针将从末尾指向第n个节点。返回主指针。

4、移除链表中的重复元素

（1）使用两个循环

这是使用两个循环的简单方法。外循环用于一一拾取元素，内循环将拾取的元素与其余元素进行比较。

（2）使用排序

通常，合并排序是最有效地对链表进行排序的最合适的排序算法。

1）使用合并排序对元素进行排序。

2）使用删除排序链表中的重复项的算法在线性时间内删除重复项

请注意，此方法不会保留元素的原始顺序。

时间复杂度：O（nLogn）

（3）使用散列

我们从头到尾遍历链接列表。对于每个新遇到的元素，我们检查它是否在哈希表中：如果是，则将其删除；否则，将其删除。否则我们将其放在哈希表中。

5、合并两个有序链表

分别用指针 head1，head2 来遍历两个链表，如果当前 head1 指向的数据小于 head2 指向的数据，则将 head1 指向的结点归入合并后的链表中，否则，将 head2 指向的结点归入合并后的链表中。如果有一个链表遍历结束，则把未结束的链表连接到合并后的链表尾部。

由于链表按升序排列，首先通过比较链表第一个结点中元素的大小来确定最终合并后链表的头结点；接下来每次都找两个链表中剩余结点的最小值链接到被合并的链表后面，如上图中的虚线所示。

五、图

1、广度优先搜索

2、深度优先搜索

3、检查图是否为树

（1）如果无向图具有以下属性，则它是树。

1）无环

……a）求出图中所有顶点的度，

……b）删除图中所有度<=1的顶点以及与该顶点相关的边，把与这些边相关的顶点的度减一

……c）如果还有度<=1的顶点重复步骤2

……d）最后如果还存在未被删除的顶点，则表示有环；否则没有环

2）连通

从任何顶点开始BFS或DFS，并检查是否所有顶点都是可到达的。如果所有顶点都是可到达的，则图已连接，否则未连接。

(也可以用有向图强连通分支的Tarjan算法 )

4、统计图中边的个数

遍历所有顶点，计算其邻接点列表（边）的大小之和sum，最后返回sum / 2。

5、使用Dijstra算法查找两个节点之间的最短距离

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------

•已经求出到V0点的最短路的点的集合为T

•维护Dist数组，Dist[i]表示目前Vi到V0的“距离”

•开始Dist[0] = 0, 其他Dist[i] = 无穷大, T为空集

•1) 若|T| = N，算法完成，Dist数组就是解。否则取Dist[i]最

小的不在T中的点Vi, 将其加入T，Dist[i]就是Vi到V0的最短

路长度。

•2) 更新所有与Vi有边相连且不在T中的点Vj的Dist值：

•Dist[j] = min(Dist[j],Dist[i]+W(Vi,Vj))

•3) 转到1）

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------

1）创建一个set sptSet（最短路径树集合），该集合跟踪最短路径树中包含的顶点，即，其与源的最小距离已被计算并确定。最初，此集合为空。

2）为输入图中的所有顶点分配一个距离值。将所有距离值初始化为INFINITE。将源顶点的距离值指定为0，以便首先选择它。

3）虽然sptSet不包括所有顶点

…。a）选择一个在sptSet中不存在的顶点u并具有最小距离值。

…。b）将 u包含到sptSet中。

…。c）更新u的所有相邻顶点的距离值。要更新距离值，请遍历所有相邻的顶点。对于每个相邻顶点v，如果u（距源）的距离值和边缘uv的权重之和小于v的距离值，则更新v的距离值。

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------

Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。

然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点，

然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。

然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。

五、树

1、计算树的高度

maxDepth（）

1).如果树为空，则返回0

2).其他 

（a）递归获得左子树的最大深度，即 调用maxDepth（tree-> left-subtree） 

 （b）递归获得右子树的最大深度，即 调用maxDepth（tree-> right-subtree） 

 （c）获取左右最大深度中的最大值 子树并为当前节点添加1。 max_depth = max（左子树的最大深度， 右子树的最大深度） +1 

 （d）返回max_depth

2、查找二叉平衡树中第K大的元素

二叉搜索树的中序遍历结果是一个有序的数组，所以如果能够求得二叉搜索树的中序遍历结果，那么就可以求得其第K大的节点

3、查找树中与根节点距离为k的节点

void printKDistant(node *root , int k) 

{      

    if(root == NULL)          

        return;      

    if( k == 0 )     

     { 

        cout << root->data << " ";          

        return ;      

    }      

    else   

     {          

        printKDistant( root->left, k - 1 ) ;          

        printKDistant( root->right, k - 1 ) ;      

     } 

} 

4、查找二叉树中某个节点的所有祖先节点

boolprintAncestors(structnode *root, inttarget)

{

      /* base cases */

      if(root == NULL)

             return    false;

      if(root->data == target)

             return    true;

  /* If target is present in either left or right subtree of this node,     then print this node */

      if( printAncestors(root->left, target)  ||       printAncestors(root->right, target) )

  {

        cout << root->data << " ";

        return    true;

  }

  /* Else return false */

      return    false;

}