程序員數學經典題

A. 面試最常考的 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/

所有題目的地址如下：

前序遍歷

中序遍歷

層序遍歷

視圖

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

B. C/C++經典面試題

C/C++經典面試題

面試題 1：變數的聲明和定義有什麼區別

為變數分配地址和存儲空間的稱為定義，不分配地址的稱為聲明。一個變數可以在多個地方聲明，

但是只在一個地方定義。加入 extern修飾的是變數的聲明，說明此變數將在文件以外或在文件後面部分

定義。

說明：很多時候一個變數，只是聲明不分配內存空間，直到具體使用時才初始化，分配內存空間，

如外部變數。

面試題 2：寫出 bool 、int、 float、指針變數與「零值」比較的 if 語句

bool型數據：

if( flag )

{

A;

}

else

{

B;

}

int型數據：

if( 0 != flag )

{

A;

}

else

{

B;

}

指針型數：

if( NULL == flag )

{

A;

}

else

{

B;

}

float型數據：

if ( ( flag >= NORM ) && ( flag <= NORM ) )

{

A;

2

}

注意：應特別注意在 int、指針型變數和「零值」比較的時候，把「零值」放在左邊，這樣當把「==」

誤寫成「=」時，編譯器可以報錯，否則這種邏輯錯誤不容易發現，並且可能導致很嚴重的後果。

面試題 3：sizeof 和strlen的區別

sizeof和 strlen 有以下區別：

 sizeof是一個操作符，strlen是庫函數。

 sizeof的參數可以是數據的類型，也可以是變數，而 strlen只能以結尾為『『的字元串作參數。

 編譯器在編譯時就計算出了 sizeof 的結果。而 strlen 函數必須在運行時才能計算出來。並且 sizeof

計算的是數據類型占內存的大小，而 strlen計算的是字元串實際的長度。

 數組做sizeof的參數不退化，傳遞給strlen就退化為指針了。

注意：有些是操作符看起來像是函數，而有些函數名看起來又像操作符，這類容易混淆的名稱一定

要加以區分，否則遇到數組名這類特殊數據類型作參數時就很容易出錯。最容易混淆為函數的操作符就

是 sizeof。

面試題 4：C 語言的關鍵字 static 和 C++ 的關鍵字 static 有什麼區別

在C 中static 用來修飾局部靜態變數和外部靜態變數、函數。而 C++中除了上述功能外，還用來定

義類的成員變數和函數。即靜態成員和靜態成員函數。

注意：編程時 static的記憶性，和全局性的特點可以讓在不同時期調用的函數進行通信，傳遞信息，

而 C++的靜態成員則可以在多個對象實例間進行通信，傳遞信息。

面試題 5：C中的 malloc 和C++中的 new有什麼區別

malloc和 new有以下不同：

(1)new、 是操作符，可以重載，只能在 C++中使用。

(2)malloc、free是函數，可以覆蓋，C、C++中都可以使用。

(3)new 可以調用對象的構造函數，對應的 調用相應的析構函數。

(4)malloc僅僅分配內存，free 僅僅回收內存，並不執行構造和析構函數

(5)new、 返回的是某種數據類型指針，malloc、free 返回的是void指針。

注意：malloc申請的內存空間要用 free釋放，而 new申請的內存空間要用 釋放，不要混用。

因為兩者實現的機理不同。

面試題 6：寫一個「標准」宏 MIN

#define min(a,b)((a)<=(b)?(a):(b))

注意：在調用時一定要注意這個宏定義的副作用，如下調用：

((++*p)<=(x)?(++*p):(x)。

p指針就自加了兩次，違背了 MIN的本意。

面試題 7：一個指針可以是 volatile 嗎

可以，因為指針和普通變數一樣，有時也有變化程序的不可控性。常見例：子中斷服務子程序修改

一個指向一個 buffer的指針時，必須用 volatile來修飾這個指針。

說明：指針是一種普通的變數，從訪問上沒有什麼不同於其他變數的特性。其保存的數值是個整型

數據，和整型變數不同的是，這個整型數據指向的是一段內存地址。

面試題 8：a 和&a 有什麼區別

請寫出以下代碼的列印結果，主要目的是考察 a和&a的區別。

#include

void main( void )

{

int a[5]={1,2,3,4,5};

int *ptr=(int *)(&a+1);

printf(「%d,%d」,*(a+1),*(ptr-1));

return;

}

輸出結果：2，5。

注意：數組名 a可以作數組的首地址，而&a是數組的指針。思考，將原式的 int *ptr=(int *)(&a+1);

改為 int *ptr=(int *)(a+1);時輸出結果將是什麼呢?

面試題 9：簡述 C、C++程序編譯的.內存分配情況

C、C++中內存分配方式可以分為三種：

(1)從靜態存儲區域分配：

內存在程序編譯時就已經分配好，這塊內存在程序的整個運行期間都存在。速度快、不容易出錯，

因為有系統會善後。例如全局變數，static變數等。

(2)在棧上分配：

在執行函數時，函數內局部變數的存儲單元都在棧上創建，函數執行結束時這些存儲單元自動被釋

放。棧內存分配運算內置於處理器的指令集中，效率很高，但是分配的內存容量有限。

(3)從堆上分配：

即動態內存分配。程序在運行的時候用 malloc 或 new 申請任意大小的內存，程序員自己負責在何

時用free 或 釋放內存。動態內存的生存期由程序員決定，使用非常靈活。如果在堆上分配了空間，

就有責任回收它，否則運行的程序會出現內存泄漏，另外頻繁地分配和釋放不同大小的堆空間將會產生

堆內碎塊。

一個C、C++程序編譯時內存分為 5大存儲區：堆區、棧區、全局區、文字常量區、程序代碼區。

4

面試題 10：簡述 strcpy、sprintf 與 memcpy的區別

三者主要有以下不同之處：

(1)操作對象不同，strcpy的兩個操作對象均為字元串，sprintf的操作源對象可以是多種數據類型，

目的操作對象是字元串， memcpy 的兩個對象就是兩個任意可操作的內存地址，並不限於何種數據類型。

(2)執行效率不同，memcpy最高，strcpy次之，sprintf的效率最低。

(3)實現功能不同，strcpy主要實現字元串變數間的拷貝，sprintf 主要實現其他數據類型格式到字

符串的轉化，memcpy主要是內存塊間的拷貝。

說明：strcpy、sprintf 與memcpy都可以實現拷貝的功能，但是針對的對象不同，根據實際需求，來

選擇合適的函數實現拷貝功能。

C. c++經典面試題及答案

1. C++的類和C裡面的struct有什麼區別?

struct成員默認訪問許可權為public，而class成員默認訪問許可權為private

2. 析構函數和虛函數的用法和作用

析構函數是在對象生存期結束時自動調用的函數，用來釋放在構造函數分配的內存。

虛函數是指被關鍵字virtual說明的函數，作用是使用C++語言的多態特性

3. 全局變數和局部變數有什麼區別?是怎麼實現的?操作系統和編譯器是怎麼知道的?

1) 全局變數的作用用這個程序塊,而局部變數作用於當前函數

2) 前者在內存中分配在全局數據區,後者分配在棧區

3) 生命周期不同：全局變數隨主程序創建和創建，隨主程序銷毀而銷毀，局部變數在局部函數內部，甚至局部循環體等內部存在，退出就不存在

4) 使用方式不同：通過聲明後全局變數程序的各個部分都可以用到，局部變數只能在局部使用

4. 有N個大小不等的自然數(1–N)，請將它們由小到大排序.要求程序演算法：時間復雜度為O(n)，空間復雜度為O(1)。

void sort(int e[], int n)

{

int i;

int t;

for (i=1; i {

t = e[e[i]];

e[e[i]] = e[i];

e[i] = t;

}

}

5. 堆與棧的去區別

A. 申請方式不同

Stack由系統自動分配，而heap需要程序員自己申請，並指明大小。

B. 申請後系統的響應不同

Stack：只要棧的剩餘空間大於申請空間，系統就為程序提供內存，否則將拋出棧溢出異常

Heap：當系統收到程序申請時，先遍歷操作系統中記錄空閑內存地址的鏈表，尋找第一個大於所申請空間的堆結點，然後將該結點從空間結點鏈表中刪 除，並將該結點的空間分配給程序。另外，大多數系統還會在這塊內存空間中的首地址處記錄本次分配的大小，以便於delete語句正確釋放空間。而且，由於 找到的堆結點的大小不一定正好等於申請的大小，系統會自動將多餘的那部分重新放入空閑鏈表。

C. 申請大小限制的不同

Stack：在windows下，棧的大小是2M(也可能是1M它是一個編譯時就確定的常數)，如果申請的空間超過棧的剩餘空間時，將提示overflow。因此，能從棧獲得的空間較小。

Heap：堆是向高地址擴展的數據結構，是不連續的內存區域。這是由於系統是用鏈表來存儲的空閑內存地址的，自然是不連續的，而鏈表的遍歷方向是由低地址向高地址。堆的大小受限於計算機系統中有效的虛擬內存。由此可見，堆獲得的空間比較靈活，也比較大。

D. 申請效率的比較：

棧由系統自動分配，速度較快。但程序員是無法控制的。

堆是由new分配的內存，一般速度比較慢，而且容易產生內存碎片,不過用起來最方便。

另外，在WINDOWS下，最好的方式是用VirtualAlloc分配內存，他不是在堆，也不是在棧是直接在進程的地址空間中保留一快內存，雖然用起來最不方便。但是速度快，也最靈活。

E. 堆和棧中的存儲內容

棧：在函數調用時，第一個進棧的是主函數中後的下一條指令(函數調用語句的下一條可執行語句)的地址，然後是函數的各個參數，在大多數的C編譯器 中，參數是由右往左入棧的，然後是函數中的局部變數。注意靜態變數是不入棧的。當本次函數調用結束後，局部變數先出棧，然後是參數，最後棧頂指針指向最開 始存的地址，也就是主函數中的下一條指令，程序由該點繼續運行。

堆：一般是在堆的.頭部用一個位元組存放堆的大小。堆中的具體內容有程序員安排。

6. 含參數的宏與函數的優缺點

宏： 優點：在預處理階段完成，不佔用編譯時間，同時，省去了函數調用的開銷，運行效率高

缺點：不進行類型檢查，多次宏替換會導致代碼體積變大，而且由於宏本質上是字元串替換，故可能會由於一些參數的副作用導致得出錯誤的結果。

函數： 優點：沒有帶參數宏可能導致的副作用，進行類型檢查，計算的正確性更有保證。

缺點：函數調用需要參數、返回地址等的入棧、出棧開銷，效率沒有帶參數宏高

PS：宏與內聯函數的區別

內聯函數和宏都是在程序出現的地方展開，內聯函數不是通過函數調用實現的，是在調用該函數的程序處將它展開(在編譯期間完成的);宏同樣是;

不同的是：內聯函數可以在編譯期間完成諸如類型檢測，語句是否正確等編譯功能;宏就不具有這樣的功能，而且宏展開的時間和內聯函數也是不同的(在運行期間展開)

7. Windows程序的入口是哪裡?寫出Windows消息機制的流程

Windows程序的入口是WinMain()函數。

Windows應用程序消息處理機制：

A. 操作系統接收應用程序的窗口消息，將消息投遞到該應用程序的消息隊列中

B. 應用程序在消息循環中調用GetMessage函數從消息隊列中取出一條一條的消息，取出消息後，應用程序可以對消息進行一些預處理。

C. 應用程序調用DispatchMessage，將消息回傳給操作系統。

D. 系統利用WNDCLASS結構體的lpfnWndProc成員保存的窗口過程函數的指針調用窗口過程，對消息進行處理。

8. 如何定義和實現一個類的成員函數為回調函數

A.什麼是回調函數?

簡而言之，回調函數就是被調用者回頭調用調用者的函數。

使用回調函數實際上就是在調用某個函數(通常是API函數)時，將自己的一個函數(這個函數為回調函數)的地址作為參數傳遞給那個被調用函數。而該被調用函數在需要的時候，利用傳遞的地址調用回調函數。

回調函數，就是由你自己寫的，你需要調用另外一個函數，而這個函數的其中一個參數，就是你的這個回調函數名。這樣，系統在必要的時候，就會調用你寫的回調函數，這樣你就可以在回調函數里完成你要做的事。

B.如何定義和實現一個類的成員函數為回調函數

要定義和實現一個類的成員函數為回調函數需要做三件事：

a.聲明;

b.定義;

c.設置觸發條件，就是在你的函數中把你的回調函數名作為一個參數，以便系統調用

如：

一、聲明回調函數類型

typedef void (*FunPtr)(void);

二、定義回調函數

class A

{

public:

A();

static void callBackFun(void) //回調函數，必須聲明為static

{

cout<<"callBackFun"<

}

virtual ~A();

};

三、設置觸發條件

void Funtype(FunPtr p)

{

p();

}

void main(void)

{

Funtype(A::callBackFun);

}

C. 回調函數與API函數

回調和API非常接近，他們的共性都是跨層調用的函數。但區別是API是低層提供給高層的調用，一般這個函數對高層都是已知的;而回調正好相反， 他是高層提供給底層的調用，對於低層他是未知的，必須由高層進行安裝，這個安裝函數其實就是一個低層提供的API，安裝後低層不知道這個回調的名字，但它 通過一個函數指針來保存這個回調函數，在需要調用時，只需引用這個函數指針和相關的參數指針。

其實：回調就是該函數寫在高層，低層通過一個函數指針保存這個函數，在某個事件的觸發下，低層通過該函數指針調用高層那個函數。