經典演算法面試

A. 測試開發面試必知演算法

測試開發的技能之一就是需要掌握一些開發的語言，而針對於考察開發語言，業界內比較容易採用的方式就是考察各種演算法。在此做一個簡單的總結（最近比較喜歡玩python，所以都是以Python為例子，其它的語言類推。）

冒泡排序

冒泡排序演算法的運作如下：（從後往前）
比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。
針對所有的元素重復以上的步驟，除了最後一個。
持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。

實例：對列表 [2, 8, 4, 7, 5, 9, 0]進行冒泡排序

遞歸

遞歸過程一般通過函數或子過程來實現。遞歸方法：在函數或子過程的內部，直接或者間接地調用自己的演算法。

實例：要計算1-10的10位數字的乘積，直觀的演算法是1 2 3 4 5 6 7 8 9，利用遞歸則思路是循環執行n*n-1,直到n=1時

二叉樹遍歷演算法
從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作：
⑴訪問結點本身（N），
⑵遍歷該結點的左子樹（L），
⑶遍歷該結點的右子樹（R）。
以上三種操作有六種執行次序：
NLR、LNR、LRN、NRL、RNL、RLN。

二叉樹的節點表示可以使用

前序遍歷：根節點->左子樹->右子樹
中序遍歷：左子樹->根節點->右子樹
後序遍歷：左子樹->右子樹->根節點

實例：求二叉樹深度和寬度
求深度用遞歸；求寬度用隊列，然後把每層的寬度求出來，找出最大的就是二叉樹的寬度

字元串倒序輸出

思路一：索引的方法

思路二：借組列表進行翻轉

後續還有的話會繼續添加的。

B. 經典C語言面試演算法題

經典C語言面試演算法題

1.寫一個函數,它的原形是int continumax(char *outputstr,char *intputstr)

功能：

在字元串中找出連續最長的數字串，並把這個串的長度返回，並把這個最長數字串付給其中一個函數參數outputstr所指內存。例如："abcd12345ed125ss123456789"的首地址傳給intputstr後，函數將返回

9，outputstr所指的值為123456789。

#include

#include

#include

int FindMax_NumStr(char *outputstr,char *inputstr)

{

char *in = inputstr,*out = outputstr,*temp;

char *final;

int count = 0;

int maxlen = 0;

int i;

while(*in!='')

{

if(*in > 47 && *in < 58)

{

for(temp = in;*in> 47 && *in <58;in++)

count++;

}

else

in++;

if(maxlen < count)

{

maxlen = count;

count = 0;

final = temp;

}

}

for(i =0;i

{

*out = *final;

out++;

final++;

}

*out = '';

return maxlen;

}

void main(void)

{

char input[]="abc123def123456eec123456789dd";

char output[50] = {0};

int maxlen;

maxlen = FindMax_NumStr(output,input);

printf("the str %s ",output);

printf("the maxlen is %d ",maxlen);

}

2.求1000!的未尾有幾個0;

求出1->1000里,能被5整除的數的個數n1,能被25整除的數的個數n2,能被125整除的'數的個數n3,能被625整除的數的個數n4.1000!末尾的零的個數=n1+n2+n3+n4;

只要是末尾是5的數它乘以一個偶數就會出現一個0，而末尾是0的數乘以任何數也都會出現0

而末尾是0的如果是一個0肯定能被5整除，兩個0肯定能被25整數，以此類推3個0就能被5的三次方整除，也就是125

1000!就是1-1000數的相乘，能被5整除的所有數分別乘以一個偶數就會出現這些個的0，而例如100，既能被5整除，也能被25整除，所以就是兩個0

1000，既能被5，25，也能被125整除，所以算三個0

例如是10!=1*2*3*4*5*6*7*8*9*10，裡面有兩個數能被5整除，就是10和5，而

5隨便乘以一個偶數就出現一個0，而10乘以其它數也會出現一個0，所以10!會有兩個0

#include

#define NUM 1000

int find5(int num)

{

int ret = 0;

while(num%5==0)

{

num/=5;

ret++;

}

return ret;

}

int main(void)

{

int result = 0;

int i;

for(i=5;i<=NUM;i+=5)

result +=find5(i);

printf("the total zero number is %d ",result);

return 0;

}

3。編寫一個 C 函數，該函數在一個字元串中找到可能的最長的子字元串，且該字元串是由同一字元組成的。

char * search(char *cpSource, char ch)

{

char *cpTemp=NULL, *cpDest=NULL;

int iTemp, iCount=0;

while(*cpSource)

{

if(*cpSource == ch)

{

iTemp = 0;

cpTemp = cpSource;

while(*cpSource == ch)

++iTemp, ++cpSource;

if(iTemp > iCount)

iCount = iTemp, cpDest = cpTemp;

if(!*cpSource)

break;

}

++cpSource;

}

return cpDest;

}

C. 大公司筆試面試有哪些經典演算法題目

1、二維數組中的查找

具體例題：如果一個數字序列逆置之後跟原序列是一樣的就稱這樣的數字序列為迴文序列。例如：{1, 2, 1}, {15, 78, 78, 15} , {112} 是迴文序列, {1, 2, 2}, {15, 78, 87, 51} ,{112, 2, 11} 不是迴文序列。現在給出一個數字序列，允許使用一種轉換操作：選擇任意兩個相鄰的數，然後從序列移除這兩個數，並用這兩個數字的和插入到這兩個數之前的位置(只插入一個和)。現在對於所給序列要求出最少需要多少次操作可以將其變成迴文序列？

D. 面試必會八大排序演算法（Python）

一、插入排序

介紹

插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據。

演算法適用於少量數據的排序，時間復雜度為O(n^2)。

插入排演算法是穩定的排序方法。

步驟

①從第一個元素開始，該元素可以認為已經被排序

②取出下一個元素，在已經排序的元素序列中從後向前掃描

③如果該元素（已排序）大於新元素，將該元素移到下一位置

④重復步驟3，直到找到已排序的元素小於或者等於新元素的位置

⑤將新元素插入到該位置中

⑥重復步驟2

排序演示

演算法實現

二、冒泡排序

介紹

冒泡排序（Bubble Sort）是一種簡單的排序演算法，時間復雜度為O(n^2)。

它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。

這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。

原理

循環遍歷列表，每次循環找出循環最大的元素排在後面；

需要使用嵌套循環實現：外層循環控制總循環次數，內層循環負責每輪的循環比較。

步驟

①比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。

②對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。

③針對所有的元素重復以上的步驟，除了最後一個。

④持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。

演算法實現：

三、快速排序

介紹

快速排序（Quicksort）是對冒泡排序的一種改進，借用了分治的思想，由C. A. R. Hoare在1962年提出。

基本思想

快速排序的基本思想是：挖坑填數 + 分治法。

首先選出一個軸值(pivot，也有叫基準的)，通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。

實現步驟

①從數列中挑出一個元素，稱為 「基準」（pivot）；

②重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）；

③對所有兩個小數列重復第二步，直至各區間只有一個數。

排序演示

演算法實現

四、希爾排序

介紹

希爾排序（Shell Sort）是插入排序的一種，也是縮小增量排序，是直接插入排序演算法的一種更高效的改進版本。希爾排序是非穩定排序演算法，時間復雜度為：O(1.3n)。

希爾排序是基於插入排序的以下兩點性質而提出改進方法的：

·插入排序在對幾乎已經排好序的數據操作時， 效率高， 即可以達到線性排序的效率；

·但插入排序一般來說是低效的， 因為插入排序每次只能將數據移動一位。

基本思想

①希爾排序是把記錄按下標的一定量分組，對每組使用直接插入演算法排序；

②隨著增量逐漸減少，每組包1含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，演算法被終止。

排序演示

演算法實現

五、選擇排序

介紹

選擇排序(Selection sort)是一種簡單直觀的排序演算法，時間復雜度為Ο(n2)。

基本思想

選擇排序的基本思想：比較 + 交換。

第一趟，在待排序記錄r1 ~ r[n]中選出最小的記錄，將它與r1交換；

第二趟，在待排序記錄r2 ~ r[n]中選出最小的記錄，將它與r2交換；

以此類推，第 i 趟，在待排序記錄ri ~ r[n]中選出最小的記錄，將它與r[i]交換,使有序序列不斷增長直到全部排序完畢。

排序演示

選擇排序的示例動畫。紅色表示當前最小值，黃色表示已排序序列，藍色表示當前位置。

演算法實現

六、堆排序

介紹

堆排序（Heapsort）是指利用堆積樹（堆）這種數據結構所設計的一種排序演算法，它是選擇排序的一種。

利用數組的特點快速指定索引的元素。

基本思想

堆分為大根堆和小根堆，是完全二叉樹。

大根堆的要求是每個節點的值不大於其父節點的值，即A[PARENT[i]] >=A[i]。

在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。

排序演示

演算法實現

七、歸並排序

介紹

歸並排序（Merge sort）是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

基本思想

歸並排序演算法是將兩個（或兩個以上）有序表合並成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然後再把有序子序列合並為整體有序序列。

演算法思想

自上而下遞歸法（假如序列共有n個元素）

① 將序列每相鄰兩個數字進行歸並操作，形成 floor(n/2)個序列，排序後每個序列包含兩個元素；

② 將上述序列再次歸並，形成 floor(n/4)個序列，每個序列包含四個元素；

③ 重復步驟②，直到所有元素排序完畢。

自下而上迭代法

① 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列；

② 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；

③ 比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置；

④ 重復步驟③直到某一指針達到序列尾；

⑤ 將另一序列剩下的所有元素直接復制到合並序列尾。

排序演示

演算法實現

八、基數排序

介紹

基數排序（Radix Sort）屬於「分配式排序」，又稱為「桶子法」。

基數排序法是屬於穩定性的排序，其時間復雜度為O (nlog(r)m) ，其中 r 為採取的基數，而m為堆數。

在某些時候，基數排序法的效率高於其他的穩定性排序法。

基本思想

將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然後，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後，數列就變成一個有序序列。

基數排序按照優先從高位或低位來排序有兩種實現方案：

MSD（Most significant digital） 從最左側高位開始進行排序。先按k1排序分組, 同一組中記錄, 關鍵碼k1相等,再對各組按k2排序分成子組, 之後, 對後面的關鍵碼繼續這樣的排序分組, 直到按最次位關鍵碼kd對各子組排序後. 再將各組連接起來,便得到一個有序序列。MSD方式適用於位數多的序列。

LSD （Least significant digital）從最右側低位開始進行排序。先從kd開始排序，再對kd-1進行排序，依次重復，直到對k1排序後便得到一個有序序列。LSD方式適用於位數少的序列。

排序效果

演算法實現

九、總結

各種排序的穩定性、時間復雜度、空間復雜度的總結：

平方階O(n²)排序：各類簡單排序：直接插入、直接選擇和冒泡排序；

從時間復雜度來說：

線性對數階O(nlog₂n)排序：快速排序、堆排序和歸並排序；

O(n1+§))排序，§是介於0和1之間的常數：希爾排序 ；

線性階O(n)排序：基數排序，此外還有桶、箱排序。

E. 面試最常考的 100 道演算法題分類整理

大家好，我是 「負雪明早沖燭」 ，一位用 7 年寫槐毀了 1000 篇 LeetCode 演算法題題解的程序員。歡迎關注。

粉絲常說： LeetCode 演算法題太多了，准備面試該刷哪些題目 ？

我之前根據 LeetCode 上面的點贊量分享過： LeetCode 上最經典的 100 道演算法題 。

這 100 道題目都屬於經典題目了，面試也常考，不過我還是不放心呢，畢竟 經典題 ≠ 面試題 呀！

但如果想知道面試常考的 100 道演算法題的話，需要至少整理 1000 篇面經吧？這個工作量可不小啊！

還好，網上有個開源項目，幫我們做了這件事情，這個項目就是 CodeTop ！

這是網站的界面（地址： https://codetop.cc/home ），展示的就是每個面試題目出現的頻度情況，甚至區分了公司和崗位：

這是開源項目的 GitHub 主頁，已經 11.5k star ⭐️ 了：

這個項目中的題目來源是牛客網的面經、網友投票等，而且持續更新中，所以還是比較可靠的。

我對這個項目做了陸明殲整理，分類整理出來面試常考的 100 道演算法題。

在整理之後，我對結果還是有點 驚訝 的！因為一些常見的數據結構與演算法，竟然沒有在常考面試中出現過！

比如前綴和、前綴樹、並查集、圖，這些都沒有出現……

最常考面試題還是很基本的鏈表、二叉樹、動態規劃等等，是不是符合你的認知呢？

強烈建議大家在面試前把這 100 道題目搞懂！

作為寵粉達人，我提供了 3 種方式查看這 100 道題目：

沒有任何套路，直接分享給大家！

在線查看地址： https://www.mubucm.com/doc/7jiBYKCKqet

在線查看地址： https://leetcode-cn.com/problem-list/q3iOID0B/

所有題目的地址如下：

前序遍歷

中序遍歷

層序遍歷

視圖

如果你覺得對你有幫助的話，求贊、求分享、求收藏。你的每一點鼓勵都是對我的最大幫助！

F. 面試官常問十大經典演算法排序（用Python實現）

演算法是一種與語言無關的東西，更確切地說就算解決問題的思路，就是一個通用的思想的問題。代碼本身不重要，演算法思想才是重中之重

我們在面試的時候總會被問到一下演算法，雖然演算法是一些基礎知識，但是難起來也會讓人非常頭疼。

排序演算法應該算是一些簡單且基礎的演算法，但是我們可以從簡單的演算法排序鍛煉我們的演算法思維。這里我就介紹經典十大演算法用python是怎麼實現的。

十大經典演算法可以分為兩大類：

比較排序： 通過對數組中的元素進行比較來實現排序。

非比較排序： 不通過比較來決定元素間的相對次序。

演算法復雜度

冒泡排序比較簡單，幾乎所有語言演算法都會涉及的冒泡演算法。

基本原理是兩兩比較待排序數據的大小 ，當兩個數據的次序不滿足順序條件時即進行交換，反之，則保持不變。

每次選擇一個最小（大）的，直到所有元素都被輸出。

將第一個元素逐個插入到前面的有序數中，直到插完所有元素為止。

從大范圍到小范圍進行比較-交換，是插入排序的一種，它是針對直接插入排序演算法的改進。先對數據進行預處理，使其基本有序，然後再用直接插入的排序演算法排序。

該演算法是採用 分治法 對集合進行排序。

把長度為n的輸入序列分成兩個長度為n/2的子序列，對這兩個子序列分別採用歸並排序，最終合並成序列。

選取一個基準值，小數在左大數在在右。

利用堆這種數據結構所設計的一種排序演算法。

堆是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。利用最大堆和最小堆的特性。

採用字典計數-還原的方法，找出待排序的數組中最大和最小的元素，統計數組中每個值為i的元素出現的次數，對所有的計數累加，將每個元素放在新數組依次排序。

設置一個定量的數組當作空桶；遍歷輸入數據，並且把數據一個一個放到對應的桶里去；對每個不是空的桶進行排序；從不是空的桶里把排好序的數據拼接起來。

元素分布在桶中：

然後，元素在每個桶中排序：

取得數組中的最大數，並取得位數；從最低位開始取每個位組成新的數組；然後進行計數排序。

上面就是我整理的十大排序演算法，希望能幫助大家在演算法方面知識的提升。看懂之後可以去試著自己到電腦上運行一遍。最後說一下每個排序是沒有調用數據的，大家記得實操的時候要調用。

參考地址：https://www.runoob.com/w3cnote/ten-sorting-algorithm.html

G. 面試經典數據結構和演算法匯總

如果說數據結構是骨架，那麼演算法就是靈魂。沒了骨架，靈魂沒有實體寄託；沒了靈魂，骨架也是個空殼。兩者相輔相成，缺一不可，在開發中起到了砥柱中流的作用。

現在我對各種數據結構和演算法做一總結，對比一下它們的效率

1.數據結構篇
1. 如果讓你手寫個棧和隊列，你還會寫嗎？
2. 開發了那麼多項目，你能自己手寫個健壯的鏈表出來嗎？
3. 下次面試若再被問到二叉樹，希望你能對答如流！
4. 面試還在被紅-黑樹虐？看完這篇輕松搞定面試官 ！

2.排序演算法篇
1. 幾個經典的基礎排序演算法，你還記得嗎？
2. 手把手教你學會希爾排序，很簡單！
3. 快速排序演算法到底有多快？
4. 五分鍾教你學會歸並排序
5. 簡單說下二叉樹排序
6. 學會堆排序只需要幾分鍾
7. 圖，這個玩意兒竟然還可以用來排序！

掌握了這些經典的數據結構和演算法，面試啥的基本上沒什麼問題了，特別是對於那些應屆生來說。接下來再總結一下不同數據結構和演算法的效率問題，做一下對比，這也是面試官經常問的問題。

數據結構常用操作效率對比：

常用排序演算法效率的對比：

關於經典的數據結構和演算法，就總結到這，本文建議收藏，利用等公交、各種排隊之時提升自己。這世上天才很少，懶蛋卻很多，你若對得起時間，時間便對得起你。

H. 阿裡面試官：恕我直言，搞懂這10道演算法題，輕松拿20K不是問題

01打怪獸

難度：容易

現在有3隻怪獸，他們的都有自己的血量a,b,c(1<=a,b,c<=100)，當Tom打死第一怪獸的時候花費的代價為0，其餘的怪獸的代價為當前的怪獸的血量減去上一個怪獸的血量的絕對值。問Tom打死這些怪獸所需要的最小代價

02數組變換

難度：中等

給出一個長度為 n 的數組，和一個正整數 d。 你每次可以選擇其中任意一個元素 a[i] 將其變為 a[i] + d 或 a[i] - d，這算作一次操作。你需要將所有的元素全部變成相等元素，如果有解，請輸出最小操作次數，如果無解請輸出-1。

01超級區間

難度：中等

Tom現在有一個長度為n的數組，Jerry給Tom定義了一種超級區間，如果區間[l,r]滿足(a[l]+…+a[r])>=k,則區間[l,r]被稱為超級區間，現在Jerry想讓Tom告訴他數組中有多纖岩少個超級區間。

02能量半徑

難度：中等

codancer來到了一個能量平面上的中心，坐標為(0,0)，接下來巫師Tom會在q個坐標上放置能量點，每個信凳能量點的能量值為1，為了打敗哥斯拉，他需要至少k點的能量，因此他想確定一個最小的整數半徑r使得codancer能夠從這個圓心為(0,0)，半徑為r的圓形區域內得到至少k個能量值，請你幫他確定最小的整數半徑r。

01找出二叉搜索樹的第2大的數

難度：容易

給定一個二叉搜索樹，找出其第二大的數。

02字元配對

難度：中等

給你一個字元串，字元串中僅包含"A","B",現在有四種字元串"AA","AB","BA","BB"，每種字元串都有他們的權值，問從給出的字元串中能夠得到的最大權值為多少(一個字元只能屬於一個子字元串)？

01斐波那契字元串

難度：中等

Tom發現了一種神奇的字元串-斐波那契字元串,定義f[1]=0,f[2]=1,對於所有的i>2都有f[i]=f[i-2]+f[i-1]，其中「+」代表拼接，比如01+10=0110，現在對於字元串f[n]，請判斷f[n]的第k項是0，還是1？

01Hikari and Interstellar Experience

難度：容易

在無垠的宇宙中，有 n 個星球，第 i 個星球有權值vi 。由於星球之間距離極遠，因此想在有限的時間內在星際間旅行，就必須要在星球間建立傳送通道。 任意兩個星球之間均可以建立傳送通道毀坦御，不過花費並不一樣。 第 i 個星球與第 j 個星球的之間建立傳送通道的花費是lowbit(vi ⊕ vj) ，其中⊕為二進制異或，而lowbit(x)為 x 二進制最低位的值，例如lowbit(5) = 1,lowbit(8) = 8 。 特殊地，lowbit(0) = 0。 Hikari 想在這 n 個星球間穿梭，於是――你需要告訴 Hikari，要使這 n 個星球相互可達，需要的花費最少是多少？

02二進制字元串

難度：中等

Tom得到了一個二進制字元串s,即s只由Ɔ'和Ƈ'組成，現在令d(t)代表二進制字元串t在十進制下的值。 那麼d(「011」)=3,d(「0001000」)=4,如果t的長度等於d(t),那麼就稱t是奇妙串，現在Tom想知道s中有多少個子串是奇妙串？

01小明的數學作業

難度：容易

眾所周知，小明是一個數學小能手，有一天數學老師給了小明一個長度為n（2<=n<=5000）的序列，其中第i個數是ai（0<=ai<=1e9）,數學老師想知道這個序列排序後，其中最長的等差子序列的長度是多長，聰明的你能幫小明解決這個問題嗎？

02Codancer上樓

codancer來到了一棟大樓前，現在他要上樓。

如果codancer從第x層走樓梯到第y層(y>x)，那麼他所花費的時間是a[x]+a[x+1]+…+a[y]；

如果他從x層坐電梯到第y層，那麼他所花費的時間是c+(b[x]+b[x+1]+…+b[y])，因為他等電梯的時間為c。

現在codancer想知道從第1層到第n層需要最少需要多長時間？

01變換的秘鑰

難度：中等

Tom最開始有一個密鑰s1，s1是長度為n的由小寫字母組成的字元串。Jerry也有一個長度為n的由小寫字母組成的密鑰s2。現在有m組關系，每組關系由兩個數字[u,v]構成(1<=u,v<=26)，表示26個字母表中的第u個小寫字母可以直接轉換為第v個小寫字母。假設u=1，v=2,那麼說明字母'a'可以直接轉換為字母'b'。現在Tom對於s1的每個字母使用無數次轉換，請判斷s1能否轉換為s2？

01最大邊權和

難度：簡單

現在有n個點(1<=n<=1000)，每個點都有一個值稱為點權ai(ai為偶數，1<=ai<=1000)，現在可以將任意兩個點相連，連起來以後這條邊也有一個值稱為邊權，這個邊的邊權為這兩個點的點權之和的一半。現在需要你添加n-1條邊，問將這n個點連通以後(連通是指任意兩個點都能互相到達)的最大的邊權和是多少？

02錢庄

難度：中等

錢庄每天能夠收到很多散錢，第i個散錢的值2 wi。為了便於管理，錢庄每天都會向中央銀行申請兌換錢幣，假設錢庄有一些散錢使得2 k1+2 k2+...+2 km=2^x（x為非負整數），那麼就可以將這些散錢兌換成一個大錢幣，問在錢庄收到的這些散錢最終最少能變成幾個錢幣？

01codancer的旅行

難度：困難

期末考試終於結束啦，Codancer開始了他的旅行，現在整個地圖上有n個城市，這些城市之間有n-1條道路相連，每條道路都有一個距離，並且保證整個圖是連通的，即這個地圖可以看作是一棵樹，現在假設Codancer要從城市A到城市B，那麼他的路費就是從A-B的路徑上邊權最大的邊的權值wmaxx元。現在Codancer有k元，他想知道他能選擇那些(A,B)並且A<B使得codancer能夠到達？

HashMap是一個用於存儲Key-Value鍵值對的集合，每一個鍵值對也叫做Entry。這些個鍵值對（Entry）分散存儲在一個數組當中，這個數組就是HashMap的主幹。

01全奇數組

難度：中等

codancer現在有n個正整數a[1],a[2]…a[n]，Tom告訴codancer他可以進行下列操作，選擇某個偶數x，把這n個數中全部等於x的數字除2，Tom想知道把這n個數字全部變成奇數最少需要幾次這樣的操作？

以上十道演算法題你都能搞定嘛？備戰大廠每日刷一道演算法題來提升自己，堅持堅持再堅持，必然會有收獲。為大家整理一份781頁的高分寶典，知識較為全面，可分享給想要學習提升自己的朋友。

領取方式：私信【面試寶典】或點擊右方鏈接： https://shimo.im/docs/QVy8HrQgPYkx9Ddg/ 即可免費領取，喜歡本文不妨關注+轉發支持一下~~

I. 面試會出哪些經典演算法題

如下：

1、排序演算法∶快速排序、歸並排序、計數排序

2、搜索演算法∶回溯、遞歸、剪枝技巧

3、圖論∶最短路、最小生成樹、網路流建模

4、動態規劃：背包問題、最長子序列、計數問題

5、基礎技巧：分治、倍增、二分、貪心

6、數組與鏈表：單/雙向鏈表、跳舞鏈

7、棧與隊列

8、樹與圖：最近公共祖先、並查集

9、哈希表

10、堆：大/小根堆、可並堆

11、字元串∶字典樹、後綴樹

演算法簡介：

演算法（Algorithm）是指解題方案的准確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制。也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。

如果一個演算法有缺陷，或不適合於某個問題，執行這個演算法將不會解決這個問題。不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間復雜度與時間復雜度來衡量。

演算法中的指令描述的是一個計算，當其運行時能從一個初始狀態和（可能為空的）初始輸入開始，經過一系列有限而清晰定義的狀態，最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化演算法在內的一些演算法，包含了一些隨機輸入。

形式化演算法的概念部分源自嘗試解決希爾伯特提出的判定問題，並在其後嘗試定義有效計算性或者有效方法中成形。

這些嘗試包括庫爾特·哥德爾、Jacques Herbrand和斯蒂芬·科爾·克萊尼分別於1930年、1934年和1935年提出的遞歸函數，阿隆佐·邱奇於1936年提出的λ演算，1936年Emil Leon Post的Formulation 1和艾倫·圖靈1937年提出的圖靈機。即使在當前，依然常有直覺想法難以定義為形式化演算法的情況。