可以毫無諱言的說：算法能力是進入名企和獲得高薪的最重要的能力。有一個著名的等式就是：程式設計語言 + 算法 = 軟體。是以程式員要想提高自己的程式設計能力，寫出優秀的軟體，必須具備紮實的程式設計語言應用能力，靈活的算法設計能力，此外還應具備豐富的某個專業領域技能和經驗（這一點對于非應屆的朋友來說，非常重要。如果你之前沒有搜尋引擎開發經驗，那麼很少有搜尋公司對你的履歷感興趣；如果你沒有過安全軟體開發，系統核心開發經驗，那麼也很少有安全公司對你的履歷感興趣），但歸根結底還是算法設計。算法設計是計算機軟體設計與開發的核心。程式設計語言與開發領域可以變化，你可以今天用C，明天用Java，你也可以今天做Web開發，明天做底層安全開發，但是算法設計以及資料結構卻是相通的。
實際上，從筆者多年的開發經驗來講，筆者總結出了這麼一個等式：程式 = 算法（包括資料結構）+ API調用 + “Hello world” + 字元串處理 + 記憶體管理（部分語言如java,python等無記憶體管理）。其中算法是程式的核心和靈魂。API是程式調用開發庫中的接口，用來實作特定的功能和任務。一個程式不可能不調用API來完成功能。無論學哪個方面的程式設計，我們都可以從最簡單的“Hello world”開始，學習它的開發環境搭建，程式結構架構，調試以及編譯執行。剩下就是可能的大量字元串的處理和記憶體的操作，其中字元串處理會占程式代碼中至少10%以上，這也是為什麼很多企業（包括微軟）會特别喜歡考查與字元串相關的算法題。
算法說白了，就是指程式員的程式設計能力，它是IT新手最需要訓練和提高的地方，算法問題也是IT面試中的最具挑戰性的問題，這直接反應了程式員的基本素質，是以答不好算法問題（一般就是在紙上或者黑闆上甚至上機寫代碼解決問題），一般很難通過面試，那麼離名企和高薪就會很遙遠。為了有效提高大家的算法能力（也就是程式設計能力），麥洛克菲在長期的算法教學中不斷積累了寶貴的教學經驗，獲得了滿意的教學效果，不少同學算法得到了明顯的提高，反映寫程式不再吃力。
現在麥洛克菲将這些經驗公開，為程式員朋友提供了如下9點經驗總結，供程式員朋友們參考：
1，确定函數名字與原型
一旦拿到有關算法的問題，那麼就應該分析問題，找到對應的輸入輸出，進而确定出算法的函數原型。我們寫算法，其實就是寫一個或者若幹個普通的函數（而不是main函數）。是以，需要分析出，應該傳什麼參數給函數（作為輸入參數），函數處理完後，應該把什麼資料作為結果傳回（作為輸出參數）。最後還要給函數取一個符合算法意義的名字，名字最好用英語表示，如果用拼音，會顯得特别山寨的感覺。函數的命名方式與變量的命名方式都有相關的約定，比如匈牙利命名法，Linux命名法或者駝峰命名法等。
比如，有這麼一個典型的算法問題：将一個字元串逆置，比如:”hello world”-->”dlrow olleh”
對于這道題，我們分析之後，應該知道，輸入是一個普通的字元串，輸出是将這個字元串逆置之後的字元串，是以，可以确定函數的原型：
void reverse_str(char *str);//str既是輸入，也是輸出
{
}
或者
void reverse_str(char *str, size_t len)//str既是輸入又是輸出，len是字元串的長度
{
}
很多初學者在這裡容易犯的錯誤包括：隻對字元串“hello world”進行了逆置而忽視了算法解決的是通用的一般性問題，或者把相關的代碼直接寫在了main（）函數裡。
此外，就是需要有子產品化的思想。一個函數隻單獨完成一個單一的功能，函數的代碼行數一般很少超過100行，加上注釋不會超過300行。 是以，要把那些頻繁使用而功能又比較單一的代碼放在一個獨立的函數裡。不要在一個函數裡完成N個功能，這不利于調試和維護，也和子產品化是相背離的。
2，嚴進寬出
确定好了函數的原型之後，緊接着在完成這個函數的功能一開始的地方，就需要嚴格判斷函數輸入參數的合法性，我們稱之為：嚴進寬出。具體點說，就是要判斷函數參數中的指針是否為NULL，函數參數中緩存的長度是否在合理範圍。這一點非常的重要。
比如同樣對于第1點裡的函數原型，那麼我們就需要作出如下的判斷：
void reverse_str(char *str, size_t len)
{
if(str== NULL || *str=='\0'|| len==0 || len==1)
{
return;
}
//程式如果執行到這裡，那麼參數檢測就完成了并合法了。是以可以繼續完成相應的功能了。
......
}
嚴進寬出是寫程式的一個非常好的習慣，可以避免程式在運作中出錯，甚至避免各種嚴重漏洞的産生。比如曾經十分嚴重的SSL協定中的心髒流血漏洞，就是因為服務端程式在處理的時候，沒有驗證來自用戶端對應的緩存長度的有效性，而造成了該漏洞的産生。
3，邊界考慮
邊界考慮就是要考慮程式中各種各樣的特殊情況，而不是隻考慮其中的一種情況。我們在寫算法的時候，經常會忘記多種情況的周全考慮，而忽略了很多特殊的情況，對程式的健壯性帶來影響。
1．邊界條件是指軟體計劃的操作界限所在的邊緣條件。資料類型：數值、字元、位置、數量、速度、位址、尺寸等，都會包含确定的邊界。應考慮的特征：第一個/最後一個、開始/完成、空/滿、最慢/最快、相鄰/最遠、最小值/最大值、超過/在内、最短/最長、最早/最遲、最高/最低。這些都是可能出現的邊界條件。邊界條件測試通常是對最大值簡單加1或者很小的數和對最小值減少1或者很小的數，例如：
l 第一個減1/最後一個加1；
l 開始減1/完成加1；
l 空了再減/滿了再加；
l 慢上加慢/快上加快；
l 最大數加1/最小數減1；
l 最小值減1/最大值加1；
l 剛好超過/剛好在内；
l 短了再短/長了再長；
l 早了更早/晚了更晚；
l 最高加1/最低減1。
另一些該注意的輸入：預設，空白，空值，零值和無；非法，錯誤，不正确和垃圾資料。根據邊界來選擇等價配置設定中包含的資料。然而，僅僅測試邊界線上的資料點往往不夠充分。提出邊界條件時，一定要測試臨近邊界的合法資料，即測試最後一個可能合法的資料，以及剛超過邊界的非法資料。
2．預設值測試（預設、空白、空值、零值和無）
好的軟體會處理這種情況，常用的方法：一是将輸入内容預設為合法邊界内的最小值，或者合法區間内某個合理值；二是傳回錯誤提示資訊。
這些值在軟體中通常需要進行特殊處理。是以應當建立單獨的等價區間。在這種預設下，如果使用者輸入0或－1作為非法值，就可以執行不同的軟體處理過程。
3．破壞測試（非法、錯誤、不正确和垃圾資料）
資料測試的這一類型是失敗測試的對象。這類測試沒有實際規則，隻是設法破壞軟體。不按軟體的要求行事，發揮創造力吧。
舉一個例子：實作C庫中的memmove函數。
很多程式員可能會很快寫出如下程式：
void memcpy(void *pDst,const void *pSrc, size_t size)
{
assert(pDst != NULL);
assert(pSrc != NULL);
char *pstrSrc= (char *)pSrc ;
char *pstrDst = (char *)pDst ;
while(size--)
*pstrDst++ = *pstrSrc++;
}
但是，這裡忽略了一個很重要的情況就是：pDst和pSrc指定的記憶體有可能是重疊的。如果按照這樣拷貝的話，那麼如果：
(pSrc<pDst) && ((char*)pSrc+size > pDst)
那麼，按照上面的程式代碼拷貝，将會把pSrc尾巴部分的資料覆寫污染了。
是以，必須清楚的考慮pSrc和pDst二者之間的關系，采取不同的算法,實際上，pSrc和pDst的位置關系有如下圖4種情況，其中第2種情況，需要特殊處理。
如上圖的位置關系所示，在第2種位置中，也就是當 (pSrc<pDst) && ((char*)pSrc+size > pDst)時，從前往後拷會有問題。必須從後往前面拷貝：
void memcpy(void *pDst,const void *pSrc, size_t size)
{
assert(pDst != NULL);
assert(pSrc != NULL);
if((pSrc<pDst) && ((char*)pSrc+size > pDst))
{
char *pstrSrc= (char *)pSrc + size -1;
char *pstrDst = (char *)pDst + size -1;
/ * 從尾部逆向拷貝 */
while(size--)
*pstrDst -- = *pstrSrc--;
}
else
{
char *pstrSrc= (char *)pSrc ;
char *pstrDst = (char *)pDst ;
while(size--)
*pstrDst++ = *pstrSrc++;
}
}
4，出錯處理
出錯處理，是指當代碼在執行過程中，如果發生了異常或者錯誤，就必須要處理，否則程式就無法繼續執行了，如果強制繼續執行，往往可能會導緻程式或者系統崩潰。
比如我們在打開檔案的時候，如果檔案不存在或者打開失敗了；在配置設定記憶體的時候，傳回記憶體為NULL，這些情況都需要及時處理。一般處理程式錯誤或者異常的方法有goto err或者try_except等方式。
出錯處理的方式方式很多，也很靈活。隻要不遺漏對錯誤的處理就行。現在介紹兩種錯誤處理方式：
1） goto error方式
語句goto是大家不大喜歡使用的，也是程式設計專家建議不要使用的一句話。是以goto語句似乎就要退出曆史的舞台。但幸好它找到了一個用武之地，那就是用goto error方式來處理出錯。下面是一個例子：
NTSTATUS QueryObjectName(HANDLE h)
{
int ret;
NTSTATUS st;
char *str = "Hello, how are u?";
char *pstr = (char *)malloc(256);
if (pstr == NULL)
{
printf("No more memory\n");
goto Error;
}
int len = strlen(str)>255?255:strlen(str);
strncpy(pstr, str, len);
pstr[len+1] = '\0';
char *namebuf = (char *)malloc(1024);
if (buf == NULL)
{
printf("No more memory\n");
goto Error;
}
st = NtQueryObject(h, FileNameInformation, namebuf, ret, NULL);
if (!NT_SUCCESS(st))
{
printf("No more memory\n");
goto Error;
}
...
Error:
if (buf)
{
free(buf);
}
if (pstr)
{
free(pstr);
}
return st;
}
goto error方式把錯誤進行了集中處理，防止了在分支複雜的程式中錯誤情況的遺漏。
2） SHE：__try__leave__exception方式
SEH( structured exception handling )，即結構化異常處理方式，它是Windows系統獨有的異常處理模型，主要由try-except語句來完成，與标準的try-catch相似。C++異常處理模型使用catch關鍵字來定義異常處理子產品，而SEH是采用except關鍵字來定義；catch關鍵字後面像接受一個函數參數一樣，可以是各種類型的異常資料對象，except關鍵字則不同，它後面跟的是一個表達式。
NTSTATUS QueryObjectName(HANDLE h)
{
int ret;
NTSTATUS st;
__try
{
char *str = "Hello, how are u?";
char *pstr = (char *)malloc(256);
if (pstr == NULL)
{
printf("No more memory\n");
__leave;
}
int len = strlen(str)>256?256:strlen(str);
strncpy(pstr, str, len);
pstr[strlen(str)] = '\0';
char *namebuf = (char *)malloc(1024);
if (buf == NULL)
{
printf("No more memory\n");
__leave;
}
st = NtQueryObject(h, FileNameInformation, namebuf, ret, NULL);
if (!NT_SUCCESS(st))
{
printf("NtQueryObject failed\n");
__leave;
}
}
__except(EXCEPTION_EXECUTE_HANDLER)
{
//獲得異常代碼
st = GetExceptionCode();
}
if (buf)
{
free(buf);
}
if (pstr)
{
free(pstr);
}
return st;
}
5，性能優化（時間複雜度，空間複雜度）
大家有時候去參加面試，自我感覺良好，面試官出的算法題，自己感覺也做出來了，也做對了，可為什麼面試結束後，遲遲等不來Offer呢？那就很可能是因為你的算法題雖然做出來了，但不是最優的。
總的來說，衡量算法的優劣有2種标準：時間複雜度和空間複雜度。簡單的來說，所謂時間複雜度，就是嵌套的循環越少越好，比如一層循環優于二層循環，面試中一般很少有三層循環的算法；而所謂空間複雜度，就是盡量不要調用malloc或者new來配置設定額外的記憶體。複雜度可以用O（）來表示，它們之間的效率關系為：
O(1)>O(n)>O(nlogn)>O(n²)>O(2^n)
對于第1點中的字元串逆置的問題，有如下2種解決方法：
//算法1：直接基于str所在記憶體進行逆置
void reverse_str(char* str, size_t len)
{
if (NULL == str || '\0' == *str || 0==len || 1==len)
{
return;
}
char *p1=str;
char *p2=str+len-1;
while(p1<p2)
{
char c = *p1;
*p1 = *p2;
*p2 = c;
p1++;
p2--;
}
}
//算法2，配置設定一個額外的記憶體，把字元串從後往前拷貝到記憶體中
char *reverse_str(char* str, size_t len)
{
if (NULL == str || '\0' == *str || 0==len || 1==len)
{
return;
}
char *buf=malloc(len+1);
char *p2=str +len-1;
char *p1=buf;
if(buff == NULL)
{
return NULL;
}
memset(buf, 0,len+1);
while(len--)
{
*p1++=*p2--;
}
return buf;
}
2種解法都能夠完成把字元串逆置的任務。但是，第二種算法，額外配置設定了記憶體（複雜度為O(n)），空間複雜度上第一種占據了優勢。
空間複雜度很好了解。而時間複雜度，想要容易的寫出O(n)或者O(1)的算法，就需要仔細思考問題和設計算法了，并且還應該學習一些常見的算法技巧。比如：2個指針跑步，比如hash算法，比如遞歸等，詳見下面的方法總結。
思考題：用盡量高效的方法（比如O(1)）來删除單向非循環連結清單中的某個結點。
原型：bool delete_node(node *&head, node *p)
6，循環的掌握
一個再複雜的算法程式，都是由循環，條件，順序三種語句構成的（switch語句也可以轉化為條件語句）。而這三種語句中，循環語句的使用是其中的關鍵。循環語句用來周遊和操作對應的資料結構。前幾節中，幾乎每個算法都用到了循環語句。以循環語句為核心，循環語句把其他語句聯系起來。是以，算法中，最重要的地方就是對循環的熟練掌握與使用。
下面把常用的各種資料結構的循環語句列出，友善大家在程式設計的時候使用：
1．數組
for (int i = 0; i < n; i++)
{
printf(“%d\n”, a[i]);
}
2．字元串
while (*str !=’\0’)
{
str++;
}
3．連結清單
while (p)
{
p = p->next;
}
4．棧空/棧滿/隊空/隊滿
while(棧非空)
{
出棧；
操作出棧元素
}
5．指針大小比較
while (pStart < pEnd)
{
pStart++;
}
6．數為正
while (size--)
{
}
do
{
}while(size--)
7．反複循環直到條件成熟
while(1)
{
if (something is true)
break;
}
熟練各種循環語句的寫法，為實作各種複雜的算法奠定了基礎。是以，要在各種循環語句上下功夫，達到熟練書寫，靈活運用的程度。
7，遞歸的應用
對于一些複雜的算法問題，還可以通過遞歸的思想來解決。有的問題，用傳統的方法來解決，顯得很複雜。這個時候，可以考慮是不是可以用遞歸來解決。因為用遞歸的思想解決問題，既簡單，又清晰，往往讓看似複雜的問題得到簡單解決的可能。
筆者曾經在面試微軟的時候遇到考官考查了一道樹的結點和它的兄弟之間的關系問題。開始我試着用隊列結合樹的周遊去解決這個問題，但是發現如果那樣去解決會顯得很麻煩，最後能否行得通也還是一個問題。而當時面試官也提醒我，一旦确定了思路，就不能再改變。于是我發現原來的想法顯得很複雜，還有可能陷入死胡同。
于是我決定放棄原來的思路，重新分析問題。經過我的重新分析，結合以往的經驗，對于樹的問題，幾乎都可以考慮用遞歸的方法去實作，筆者按照遞歸的方法，首先分析了這個問題最簡單的情況（即遞歸的出口），然後再對複雜的情況利用遞歸方法調用它自身。思路越來越清晰，我便開始動手寫在紙上寫起代碼來。沒過多久，代碼就完成了，并交給了面試官。面試官看完代碼後，很滿意的點點頭。問題最終得到圓滿的解決。
題目：用一條語句，不聲明臨時變量，實作strlen來計算一個字元串的長度。
如strlen(“hello world”)=11
size_t strlen (const char * str )//正常方法
{
const char *eos = str;
while( *eos++ ) ;
return( eos - str - 1 );
}
size_t strlen(const char *str)//遞歸方法
{
return (str==NULL || *str==’\0’)?0:1+strlen(str+1);
}
題目：将一個字元串逆置。
比如:”hello world”-->”dlrow olleh”
void reverse_str(char* str, unsigned int len)//正常方法
{
if (NULL == str)
{
return;
}
char *p1=str;
char *p2=str+len-1;
while(p1<p2)
{
char c = *p1;
*p1 = *p2;
*p2 = c;
p1++;
p2--;
}
}
void reverse_str(char *str, size_t len)//遞歸方法
{
if(len==0 || len==1 || str == NULL || *str=='\0')
{
return;
}
char tmp = str[0];
str[0]=str[len-1];
str[len-1]=tmp;
reverse_str(str+1, len-2);
}
遞歸算法的關鍵是找到遞歸的出口和遞歸公式。
8，2個指針跑步
2個指針跑步法，是麥洛克菲在算法教學過程中總結的一個很好的程式設計方法。就是在算法實作過程中，我們可以定義2個指針，一前一後，或者相向而行，同時周遊對應的資料結構（如數組，連結清單，字元串等），在周遊過程中解決對應的問題。在大量的名企面試題中，都可以使用該方法來解決并降低算法的複雜度。下面的例子詳細的描述了這個方法的使用方法：
題目1：計算一個連結清單的中間節點。
思路：定義2個指針，一個跑2步，一個跑1步，當跑2步的到連結清單終點，跑1步的正好到達中間結點
node * find_list_middle_node(node * list)
{
if(list == NULL || list->next == NULL)
{
return list;
}
node *p1 = list;
node *p2 = list;
while(p1&&p2&&p2->next)
{
p1=p1->next;
p2=p2->next->next;
}
if(p2->next==NULL || p2==NULL)
return p1;
}
題目2：判斷一個單向連結清單是否存在循環。
思路：定義2個指針，一個指針跑一步，一個指針跑2步；如果2個指針相遇，就存在循環，否則不存在循環。
int find_loop(node *head)
{
node *p = NULL;
node *q = NULL;
if (head == NULL)
return 0;
p = head;
q = head->next;
while (p!=NULL &&
q!=NULL&&q->next!=NULL&&p!=q)
{
p = p->next;
q = q->next->next
}
if (p==q)
return 1;
else
return 0;
}
題目3：從一個字元串中删除某一個特定的字元。
如：”hello world”,’o’-->”hell wrld”
思路：定義2個指針，一個是讀指針，一個是寫指針。讀指針從頭到尾掃描字元串，遇到不需要删除的字元，傳遞給寫指針儲存對應的字元，如果遇到要删除的字元直接忽略。
char* del_char(char *str,char ch)
{
char *p1=str,*p2=str;
if(NULL==str)
{
return NULL;
}
while(*p2!='\0')
{
if(*p2!=ch)
{
*p1++=*p2++;
}
else
{
p2++;
}
}
*p1='\0';
return str;
}
思考題目1：将一個字元串按照單詞順序逆置，如hello this world-->world this hello
思考題目2：将一個IP位址字元串轉化為32位整數。如255.255.255.255-->0xffffffff
思考題3：找出一個單向非循環連結清單中，倒數第M個結點
9. Hash算法
Hash算法一般是用一個hash數組來記錄一個key對應的有無或者統計對應的個數，用key作為hash數組的下标，而下标對應的值用來表示該key的存在與否以及統計對應的個數。
例1：請編寫一個高效率的函數來找出字元串中的第一個無重複字元。例如，"total"中的第一個無重複字元上一"o"
char find_first_single_char(const char *str)
{
int tmp[256]={0};//hash數組
char *s= (char *)str;
while(*s!='\0')
{
tmp[*s]++;
s++;
}
s=(char*)str;
while(*s!='\0')
{
if(tmp[*s]==1)
{
return *s;
}
s++;
}
return '\0';
}
例2：找出一系列整數（都小于65536）中存在的重複數字。
#define MAXMUM 65536
void find_repeated_number(int a[], in n)
{
int tmp[MAXMUM];//hash數組
int i;
for (i = 0; i < MAXMUM; i++)
{
tmp[i] = 0;
}
for (i = 0; i < n; i ++)
{
tmp[a[i]]++;
}
for (i = 0; i < MAXMUM; i++)
{
if (tmp[i]>1)
printf(“%d:%d”, i, tmp[i]);
}
}