一、數(shù)組
1、查找數(shù)組中第2小的元素
（1）堆排序
（2）遍歷找第一小的，第一小的存下來再遍歷找第二小的
2、查找第一個沒有重復的數(shù)組元素
（1）使用兩個循環(huán)。外循環(huán)遍歷，內(nèi)循環(huán)檢查有誤重復
（2）哈希，將值映射到哈希數(shù)組中，若發(fā)生0->1->0的改變則說明是第一個重復的數(shù)組元素
3、合并兩個排序的數(shù)組
（1）暴力
·創(chuàng)建大小為n1 + n2的數(shù)組arr3 []。
·將arr1 []的所有n1個元素復制到arr3 []
·遍歷arr2 []和arr3 []到arr1 []?的一對一插入元素（如插入排序）。此步驟需要O（n1 * n2）時間。
（2）Merge Sort函數(shù)
·創(chuàng)建大小為n1 + n2的數(shù)組arr3 []。
·同時遍歷arr1 []和arr2 []。
·在arr1 []和arr2 []中拾取較小的當前元素，將此較小的元素復制到arr3 []中的下一個位置，然后在arr3 []中向前移動，并拾取其元素的數(shù)組。
·如果arr1 []或arr2 []中還有剩余元素，請將它們也復制到arr3 []中。
（3）使用STL? map
·將兩個數(shù)組的元素插入映射中作為鍵。
·打印地圖鍵。
4、重新排列數(shù)組中的正數(shù)和負數(shù)
先使用QuickSort的分區(qū)過程將正數(shù)和負數(shù)分開。在分區(qū)過程中，將0視為樞軸元素的值，以便將所有負數(shù)放在正數(shù)之前。一旦負數(shù)和正數(shù)分開，我們就從第一個負數(shù)和第一個正數(shù)開始，然后將每個備用負數(shù)與下一個正數(shù)交換。
二、棧
（1）使用棧計算后綴表達式
1）創(chuàng)建一個堆棧來存儲操作數(shù)（或值）。
2）掃描給定的表達式，然后對每個掃描的元素執(zhí)行以下操作。
…..a）如果元素是數(shù)字，則將其推入堆棧
…..b）如果元素是運算符，則從堆棧中彈出該運算符的操作數(shù)。評估運算符并將結(jié)果推回堆棧
3）表達式結(jié)束時，堆棧中的數(shù)字是最終答案
示例：
假定給定表達式為“ 2 3 1 * + 9-”。我們一一掃描所有元素。
1）掃描'2'，它是一個數(shù)字，因此將其壓入堆棧。堆棧包含“ 2”
2）掃描“ 3”，再次是一個數(shù)字，將其推入堆棧，堆?，F(xiàn)在包含“ 2 3”（從下至上）
3）掃描“ 1”，再次是一個數(shù)字，將其推入堆棧，堆棧現(xiàn)在包含'2 31'
4）掃描'*'，它是一個運算符，從堆棧中彈出兩個操作數(shù)，對操作數(shù)應用*運算符，得到3 * 1，結(jié)果為3。將結(jié)果'3'推入堆棧。堆棧現(xiàn)在變?yōu)?2 3'。
5）掃描'+'，它是一個運算符，從堆棧中彈出兩個操作數(shù)，將+運算符應用于操作數(shù)，我們得到3 + 2，結(jié)果為5。將結(jié)果'5'推入堆棧。堆?，F(xiàn)在變?yōu)椤?5”。
6）掃描'9'，它是一個數(shù)字，我們將其壓入堆棧。堆疊現(xiàn)在變?yōu)椤?5 9”。
7）掃描'-'，它是一個運算符，從堆棧中彈出兩個操作數(shù)，將–運算符應用于操作數(shù)，我們得到5 – 9，結(jié)果為-4。我們將結(jié)果“ -4”壓入堆棧。堆疊現(xiàn)在變?yōu)?-4'。
8）沒有更多要掃描的元素，我們從堆棧中返回頂部元素（這是堆棧中剩下的唯一元素）。
（2）使用棧計算中綴表達式
1）使用兩個棧，stack0用于存儲操作數(shù)，stack1用于存儲操作符
2)從左往右掃描，遇到操作數(shù)入棧stack0
…..a）遇到操作符時，如果優(yōu)先級低于或等于棧頂操作符優(yōu)先級，則從stack０彈出兩個元素進行計算，并壓入stack0，繼續(xù)與棧頂操作符的比較優(yōu)先級
…..b）如果遇到操作符高于棧頂操作符優(yōu)先級，則直接入棧stack1
…..c）遇到左括號，直接入棧stack1，遇到右括號，則直接出棧并計算，直到遇到左括號
（https://zhuanlan.zhihu.com/p/60609567）
（3）中綴表達式轉(zhuǎn)后綴表達式
先把中綴表達式轉(zhuǎn)為后綴表達式，再入棧計算。
轉(zhuǎn)化主要遵循以下原則：
1.遇到操作數(shù)，直接輸出；
2.棧為空時，遇到運算符，入棧；
3.遇到左括號，將其入棧；
4.遇到右括號，執(zhí)行出棧操作，并將出棧的元素輸出，直到彈出棧的是左括號，左括號不輸出， 左括號也要彈出；
5.遇到其他運算符’+”-”*”/’時，彈出所有優(yōu)先級大于或等于該運算符的棧頂元素，然后將該運算符入棧， 遇到左括號時不能再彈出；
6.最終將棧中的元素依次出棧，輸出。
經(jīng)過上面的步驟，得到的輸出既是轉(zhuǎn)換得到的后綴表達式。
（4）棧實現(xiàn)隊列
....a)雙棧
當調(diào)用?push?讓元素入隊時，只要把元素壓入?s1?即可
那么如果這時候使用?peek?查看隊頭的元素怎么辦呢？按道理隊頭元素應該是 1，但是在?s1?中 1 被壓在棧底，現(xiàn)在就要輪到?s2?起到一個中轉(zhuǎn)的作用了：當?s2?為空時，可以把?s1?的所有元素取出再添加進?s2，這時候?s2?中元素就是先進先出順序了。
…..b）用兩個堆棧實現(xiàn)一個隊列
進列：直接在堆棧A后添加
出列：判斷堆棧B是否為空，若為空，則將堆棧A中元素出棧后，壓棧進入堆棧B。若棧B不為空，則直接出棧。
三、隊列? ?
1、使用隊列實現(xiàn)棧
可以使用兩個隊列來實現(xiàn)堆棧。
進棧：直接在隊列A后添加元素
出棧：若隊列A為空，則出棧元素為空。當隊列A中只有1個元素直接出棧，否則將隊列A中的元素出列壓入隊列B中，當A只剩下一個元素是出棧。再將AB隊列交換，重復前面的操作，達到堆棧的效果。
2、倒換隊列的前k個元素
使用輔助堆棧。
（1）創(chuàng)建一個空堆棧。Create an empty stack.
（2）從給定隊列中逐一出隊各個元素，并將出隊元素推入堆棧。One by one dequeue items from given queue and push the dequeued items to stack.
（3）將堆棧的內(nèi)容排入隊列的后面。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轉(zhuǎn)換為二進制（運行一個從1到n的循環(huán)，在循環(huán)內(nèi)調(diào)用十進制到二進制。）
使用隊列數(shù)據(jù)結(jié)構(gòu)來打印二進制數(shù)字。
1）創(chuàng)建一個空字符串隊列。Create an empty queue of strings
2）將第一個二進制數(shù)字“ 1”排隊。Enqueue the first binary number “1” to queue.
3）現(xiàn)在運行一個循環(huán)，以生成和打印n個二進制數(shù)。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、倒轉(zhuǎn)一個鏈表
迭代
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
（1）將三個指針prev初始化為NULL，將curr初始化為head，將next初始化為NULL。
（2）遍歷鏈表。循環(huán)執(zhí)行以下操作。
//在更改當前
下一個節(jié)點之前，//存儲下一個節(jié)點
next = curr-> next
//現(xiàn)在更改當前位置的下一個
// //這是實際反轉(zhuǎn)發(fā)生的位置
curr-> next = prev
//移動分組和CURR一步向前
先前= CURR
CURR =下一個
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
程序員小灰圖解：
從鏈表頭部開始，建立三個臨時節(jié)點的引用，分別為p1，p2，p3。它們分別指向頭節(jié)點、第二個節(jié)點、第三個節(jié)點。
1.以p2節(jié)點為視角，把p2節(jié)點原本指向p3的next指針倒轉(zhuǎn)，指向p1。
2.三個臨時節(jié)點引用p1，p2，p3分別向后移動一格位置。
3.重復第1步的工作，以p2節(jié)點為視角，把p2節(jié)點原本指向p3的next指針倒轉(zhuǎn)，指向p1。
4.重復第2步的工作，三個臨時節(jié)點引用p1，p2，p3分別向后移動一格位置。
5.繼續(xù)像這樣子迭代下去，一直到p2是空為止。
6.最后，把head節(jié)點的next指向空，成為逆序鏈表的尾節(jié)點。并且把p1賦值給head，讓p1所在的節(jié)點成為逆序鏈表的頭節(jié)點。
2、檢查鏈表中是否存在循環(huán)
（1）哈希
遍歷鏈表，并將節(jié)點地址始終放在哈希表中。在任何時候，如果達到NULL，則返回false，如果當前節(jié)點的下一個指向Hash中先前存儲的任何節(jié)點，則返回true。
（2）通過修改鏈表數(shù)據(jù)結(jié)構(gòu)，無需哈希圖即可解決此問題。（此解決方案需要修改基本的鏈表數(shù)據(jù)結(jié)構(gòu)）
每個節(jié)點都有一個訪問標志。
遍歷鏈接列表并繼續(xù)標記訪問的節(jié)點。
如果您再次看到一個訪問過的節(jié)點，那么就會有一個循環(huán)。該解決方案適用于O（n），但每個節(jié)點都需要其他信息。
此解決方案的一種變體不需要修改基本數(shù)據(jù)結(jié)構(gòu)，可以使用哈希來實現(xiàn)，只需將訪問的節(jié)點的地址存儲在哈希中，如果您看到哈希中已經(jīng)存在的地址，則存在一個循環(huán)。
3、返回鏈表第n個元素
（1）使用鏈表的長度
?1）計算鏈表的長度。讓長度為len。
2）從鏈接列表的開頭打印第（len – n + 1）個節(jié)點。
（2）使用兩個指針
雙指針概念：
第一個指針用于存儲變量的地址，第二個指針用于存儲第一個指針的地址。如果我們希望通過函數(shù)更改變量的值，則將指針傳遞給它。并且，如果我們希望更改指針的值（即，它應該開始指向其他對象），則將指針傳遞給指針。
維護兩個指針–參考指針和主指針。初始化引用和主指向head的指針。首先，將參考指針從頭移到n個節(jié)點?，F(xiàn)在將兩個指針一一移動，直到參考指針到達終點為止?，F(xiàn)在，主指針將從末尾指向第n個節(jié)點。返回主指針。
4、移除鏈表中的重復元素
（1）使用兩個循環(huán)
這是使用兩個循環(huán)的簡單方法。外循環(huán)用于一一拾取元素，內(nèi)循環(huán)將拾取的元素與其余元素進行比較。
（2）使用排序
通常，合并排序是最有效地對鏈表進行排序的最合適的排序算法。
1）使用合并排序?qū)υ剡M行排序。
2）使用刪除排序鏈表中的重復項的算法在線性時間內(nèi)刪除重復項
請注意，此方法不會保留元素的原始順序。
時間復雜度：O（nLogn）
（3）使用散列
我們從頭到尾遍歷鏈接列表。對于每個新遇到的元素，我們檢查它是否在哈希表中：如果是，則將其刪除；否則，將其刪除。否則我們將其放在哈希表中。
5、合并兩個有序鏈表
分別用指針 head1，head2 來遍歷兩個鏈表，如果當前 head1 指向的數(shù)據(jù)小于 head2 指向的數(shù)據(jù)，則將 head1 指向的結(jié)點歸入合并后的鏈表中，否則，將 head2 指向的結(jié)點歸入合并后的鏈表中。如果有一個鏈表遍歷結(jié)束，則把未結(jié)束的鏈表連接到合并后的鏈表尾部。
由于鏈表按升序排列，首先通過比較鏈表第一個結(jié)點中元素的大小來確定最終合并后鏈表的頭結(jié)點；接下來每次都找兩個鏈表中剩余結(jié)點的最小值鏈接到被合并的鏈表后面，如上圖中的虛線所示。
五、圖
1、廣度優(yōu)先搜索
2、深度優(yōu)先搜索
3、檢查圖是否為樹
（1）如果無向圖具有以下屬性，則它是樹。
1）無環(huán)
……a）求出圖中所有頂點的度，
……b）刪除圖中所有度<=1的頂點以及與該頂點相關(guān)的邊，把與這些邊相關(guān)的頂點的度減一
……c）如果還有度<=1的頂點重復步驟2
……d）最后如果還存在未被刪除的頂點，則表示有環(huán)；否則沒有環(huán)
2）連通
從任何頂點開始BFS或DFS，并檢查是否所有頂點都是可到達的。如果所有頂點都是可到達的，則圖已連接，否則未連接。
(也可以用有向圖強連通分支的Tarjan算法 )
4、統(tǒng)計圖中邊的個數(shù)
遍歷所有頂點，計算其鄰接點列表（邊）的大小之和sum，最后返回sum / 2。
5、使用Dijstra算法查找兩個節(jié)點之間的最短距離
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
?已經(jīng)求出到V0點的最短路的點的集合為T
?維護Dist數(shù)組，Dist[i]表示目前Vi到V0的“距離”
?開始Dist[0] = 0, 其他Dist[i] = 無窮大, T為空集
?1) 若|T| = N，算法完成，Dist數(shù)組就是解。否則取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) 轉(zhuǎn)到1）
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
1）創(chuàng)建一個set?sptSet（最短路徑樹集合），該集合跟蹤最短路徑樹中包含的頂點，即，其與源的最小距離已被計算并確定。最初，此集合為空。
2）為輸入圖中的所有頂點分配一個距離值。將所有距離值初始化為INFINITE。將源頂點的距離值指定為0，以便首先選擇它。
3）雖然sptSet不包括所有頂點
…。a）選擇一個在sptSet中不存在的頂點u并具有最小距離值。
…。b）將?u包含到sptSet中。
…。c）更新u的所有相鄰頂點的距離值。要更新距離值，請遍歷所有相鄰的頂點。對于每個相鄰頂點v，如果u（距源）的距離值和邊緣uv的權(quán)重之和小于v的距離值，則更新v的距離值。
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------
Dijkstra算法采用的是一種貪心的策略，聲明一個數(shù)組dis來保存源點到各個頂點的最短距離和一個保存已經(jīng)找到了最短路徑的頂點的集合：T，初始時，原點 s 的路徑權(quán)重被賦為 0 （dis[s] = 0）。若對于頂點 s 存在能直接到達的邊（s,m），則把dis[m]設為w（s, m）,同時把所有其他（s不能直接到達的）頂點的路徑長度設為無窮大。初始時，集合T只有頂點s。
然后，從dis數(shù)組選擇最小值，則該值就是源點s到該值對應的頂點的最短路徑，并且把該點加入到T中，OK，此時完成一個頂點，
然后，我們需要看看新加入的頂點是否可以到達其他頂點并且看看通過該頂點到達其他點的路徑長度是否比源點直接到達短，如果是，那么就替換這些頂點在dis中的值。
然后，又從dis中找出最小值，重復上述動作，直到T中包含了圖的所有頂點。
五、樹
1、計算樹的高度
maxDepth（）
1).如果樹為空，則返回0
2).其他?
（a）遞歸獲得左子樹的最大深度，即 調(diào)用maxDepth（tree-> left-subtree）?
?（b）遞歸獲得右子樹的最大深度，即 調(diào)用maxDepth（tree-> right-subtree）?
?（c）獲取左右最大深度中的最大值 子樹并為當前節(jié)點添加1。 max_depth = max（左子樹的最大深度， 右子樹的最大深度） +1?
?（d）返回max_depth
2、查找二叉平衡樹中第K大的元素
二叉搜索樹的中序遍歷結(jié)果是一個有序的數(shù)組，所以如果能夠求得二叉搜索樹的中序遍歷結(jié)果，那么就可以求得其第K大的節(jié)點
3、查找樹中與根節(jié)點距離為k的節(jié)點
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、查找二叉樹中某個節(jié)點的所有祖先節(jié)點
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;
}
