【中國直郵】I READING愛閱讀 程式設計師代碼面試指南IT名企演算法與資料結構題目最優解(第2版)

編輯推薦

如何在IT名企的面試中脫穎而出、一舉成名？這本書就是你該擁有的「神兵利器」。 「刷」完本書，你就是「題王」！

對於每一個程式設計師來說，提升演算法和資料結構等方面的能力至關重要。無數碼農和程式設計愛好者「深陷」題海之中，無論你是為了代碼面試、提升能力而不情願地刷題，還是愛好所致沉迷於此，這都是你值得擁有的案頭書。

這裡有你在別處找不到的至優解分析，有高頻出現在IT名氣代碼面試中的真題，有讓人拍案驚嘆巧妙的題目解法，也有讓你工作中的程式設計難題迎刃而解的啟發…

第2版​​說明：

1．修改了第1版部分題目的解釋，並增加了更多範例。

2．增加了許多新出現的流行面試題，刪掉了已經過時的低頻面試題。

3．針對解題套路與演算法原型做了結構化的調整與總結。

內容簡介

《程式設計師代碼面試指南（第2版）》是一本程式設計師代碼面試寶典！書中對IT名企代碼面試各類題目的至優解進行了總結，並提供了相關代碼實作。針對目前程式設計師面試缺乏題目總結這一痛點，本書選取將近200道真實出現過的經典程式碼面試題，幫助廣大程式設計師做充分的面試準備。 「刷」完本書後，你就是「題王」！

《程式設計師代碼面試指南（第2版）》採用「題目+解答」的方式組織內容，並把麵試題類型相近或解法相近的題目盡量放在一起，讀者在學習本書時很容易看出面試題解法之間的聯繫，使知識的學習避免碎片化。本書將所有的面試題從難到易依序分為「將」「校」「尉」「士」四個檔次，方便讀者有針對性地選擇「刷」題。本書收錄的所有面試題都給出了至優解講解和代碼實現，並且提供了一些普通解法和至優解法的運行時間對比，讓讀者真切地感受到至優解的魅力！

《程式設計師代碼面試指南：（第2版）》中的題目全面且經典，更重要的是，書中收錄了大量新題目和至優解分析，這些內容源自筆者多年來“死磕自己”的深入思考。

程式設計師們做好準備在IT名企的面試中脫穎而出、一舉成名了嗎？ 《程式設計師代碼面試指南（第2版）》就是你該擁有的「神兵利器」。當然，對於需要提升演算法和資料結構等方面能力的程式設計師而言，《程式設計師程式碼面試指南（第2版）》的價值也是顯而易見的。

作者簡介

左程雲，大學部和碩士先後就讀華中科技大學和芝加哥大學，在多家國內外優秀網路公司工作多年。自2010年起專注刷題至今，從2015年開始利用業餘時間在牛客網平台針對程式碼面試與演算法開始教學工作。

精彩書評

【精彩書評】

這本書不僅可以作為代碼面試指南，還可以作為學生與程式設計師的輔助練習。作者刷題多年，悉數總結沉澱在這本書裡。跟著他的引導，從頭到尾逐一攻克必有收穫。

——葉向宇牛客網CEO

對工程師而言，演算法既是基礎能力，也是進階突破的必備能力。本書內容深入淺出，不僅涉及演算法知識本身，更能讓讀者解決問題的思考升級。不論是面試準備，還是日常學習，本書都可以成為你進入演算法世界的至優選擇。

——葉玎玎GrowingIO CTO

相較於在網路上泛泛地刷題，這本書更強調至優解和舉一反三的能力。演算法原型的介紹也能幫助程式設計師更有效率地準備面試與提升自己，以及在不斷變化的題目中迅速找到思路。

——鞠林阿里巴巴達摩院人工智慧實驗室技術專家

大部頭的經典書人都買得起，但是卻沒幾個人看得進去。而在本書中，作者透過自己對常見演算法知識的理解，精心選擇了一道道真實的高頻面試題，循序漸進地提升題目難度，輔以翔實的解題思路，讓讀者真正學得到內容，並學得下去。

——徐雲釗@imToken 全端工程師& 區塊鏈技術開發

此書不僅對準備面試而刷題的人有幫助，還針對演算法流程的最佳化技巧做了多維度的詳盡闡述，在我資料處理的工作中甚至將其作為一本演算法優化的Cookbook來讀。另外，在與左老師共事期間，我發現他許多優秀的演算法設計也源自於撰寫此書期間對基礎演算法的累積與沉澱。所以，同樣推薦給已經通過面試的各位職場人。

——Roy Yang GrowingIO前端負責人

程雲總是能清晰敏銳地點出演算法題的關鍵思路並給出優雅的實現，讓人醍醐灌頂。這本書凝聚了他多年的思考與沉澱，相信能成為程式設計師的良好指導，使其找到化繁為簡、領悟解題的要訣。此書能助你斬獲心儀的Offer。

——劉耀東今日頭條高級工程師

本書涵蓋了網路公司面試時的絕大多數演算法題型，不僅是求職的好幫手，而且對實際的工作也很有指導意義。作者對題目的講解鞭闢入裡，讀起來讓人耳目一新，不由得感概原來演算法題要這樣做！

——付強高級研發工程師

求職或跳槽刷題人的優選工具用書！作者藉助豐富的工作經驗和對演算法的深刻理解，透過精闢的範例，把程式碼面試題目至優解解釋得簡明和「平易近人」。

——楊猛資深工程師

目錄

【目錄】

第1章棧和佇列

└ 設計一個有getMin功能的堆疊

└ 由兩個堆疊組成的佇列

└ 如何只用遞歸函數和堆疊操作逆序一個棧

└ 貓狗隊列

└ 用一個棧實作另一個棧的排序

└ 用堆疊來解漢諾塔問題

└ 產生視窗最大值數組

└ 單調堆疊結構

└ 求最大子矩陣的大小

└ 最大值減去最小值小於或等於num的子數組數量

第2章鍊錶問題

└ 可見的山峰對數量

└ 列印兩個有序鍊錶的公共部分

└ 在單鍊錶和雙鍊錶中刪除倒數第K個節點

└ 刪除鍊錶的中間節點和a/b處的節點

└ 反轉單向和雙向鍊錶

└ 反轉部分單向鍊錶

└ 環形單鍊錶的約瑟夫問題

└ 判斷一個鍊錶是否為回文結構

└ 將單向鍊錶依某值分割成左邊小、中間相等、右邊大的形式

└ 複製含有隨機指標節點的鍊錶

└ 兩個單鍊錶產生相加鍊錶

└ 兩個單鍊錶相交的一系列問題

└ 將單鍊錶的每K個節點之間逆序

└ 刪除無序單鍊錶中值重複出現的節點

└ 在單鍊錶中刪除指定值的節點

└ 將搜尋二元樹轉換成雙向鍊錶

└ 單鍊錶的選擇排序

└ 一種怪異的節點刪除方式

└ 將新節點

└ 合併兩個有序的單鍊錶

└ 依照左右半區的方式重新組合單鍊錶

第3章二元樹問題

└ 分別以遞歸和非遞歸方式實現二元樹先序、中序和後序遍歷

└ 列印二元樹的邊界節點

└ 如何較為直觀地列印二元樹

└ 二元樹的序列化與反序列化

└ 遍歷二元樹的神級方法

└ 在二元樹中找到累加和為指定值的最長路徑長度

└ 找出二元樹中的最大搜尋二元樹

└ 找出二元樹中符合搜尋二元樹條件的最大拓樸結構

└ 二元樹的按層列印與ZigZag列印

└ 調整搜尋二元樹中兩個錯誤的節點

└ 判斷t1樹是否包含t2樹全部的拓樸結構

└ 判斷t1樹中是否有與t2樹拓樸結構完全相同的子樹

└ 判斷二元樹是否為平衡二元樹

└ 依後序數組重建搜尋二元樹

└ 判斷一棵二元樹是否為搜尋二元樹和完全二元樹

└ 透過有序數組產生平衡搜尋二元樹

└ 在二元樹中找到一個節點的後繼節點

└ 在二元樹中找出兩個節點的最近公共祖先

└ Tarjan演算法與並檢視解決二元樹節點間最近公共祖先的批次查詢問題

└ 二元樹節點間的最大距離問題

└ 派對的最大快樂值

└ 透過先序和中序數組產生後序數組

└ 統計並產生所有不同的二元樹

└ 統計完全二元樹的節點數

第4章遞迴與動態規劃

└ 斐波那契數列問題的遞迴與動態規劃

└ 矩陣的最小路徑和

└ 換錢的最少貨幣數

└ 機器人達到指定位置方法數

└ 換錢的方法數

└ 打氣球的最大分數

└ 最長遞增子序列

└ 信封嵌套問題

└ 漢諾塔問題

└ 最長公共子序列問題

└ 最長公共子字串問題

└ 子數組異或和為0的最多劃分

└ 最小編輯代價

└ 字串的交錯組成

└ 龍與地下城遊戲問題

└ 數字字串轉換為字母組合的種數

└ 表達式得到期望結果的組成種數

└ 排成一條線的紙牌博弈問題

└ 跳躍遊戲

└ 數組中最長的連續序列

└ N皇后問題

第5章字串問題

└ 判斷兩個字串是否互為變形詞

└ 判斷兩個字串是否互為旋轉詞

└ 將整數字串轉成整數值

└ 字串的統計字串

└ 判斷字元數組中是否所有的字元都只出現過一次

└ 在有序但含有空的陣列中尋找字串

└ 字串的調整與替換

└ 翻轉字串

└ 完美洗牌問題

└ 刪除多餘字元得到字典序最小的字串

└ 數組中兩個字串的最小距離

└ 字串的轉換路徑問題

└ 新增最少字元使字串整體都是回文字串

└ 括號字串的有效性和最長有效長度

└ 公式字串求值

└ 0左邊必有1的二進位字串數量

└ 拼接所有字串產生字典順序最小的大寫字串

└ 找到字串的最長無重複字元子字串

└ 找到指定的新類型字符

└ 旋變字串問題

└ 最小包含子字串的長度

└ 回文最少分割數

└ 字串比對問題

└ 字典樹（前綴樹）的實現

└ 子數組的最大異或和

第6章大數據和空間限制

└ 認識布隆過濾器

└ 只用2GB內存在20億個整數中找到出現次數最多的數

└ 40億個非負整數中找出未出現的數

└ 找到100億個URL中重複的URL及搜尋詞彙的Top K問題

└ 40億個非負整數中找出出現兩次的數和所有數的中位數

└ 一致性雜湊演算法的基本原理

└ 島問題

第7章位運算

└ 不用額外變數交換兩個整數的值

└ 不用做任何比較判斷找出兩個數中較大的數

└ 只用位元運算不用算術運算實現整數的加減乘除運算

└ 整數的二進制數表達式中有多少個1

└ 在其他數都出現偶數次的陣列中找出出現奇數次的數

└ 在其他數都出現k次的陣列中找出只出現一次的數

└ 第8章數組與矩陣問題

└ 轉圈列印矩陣

└ 將正方形矩陣順時針轉動90°

└ “之”字形列印矩陣

└ 找出無序數組中最小的k個數

└ 需要排序的最短子數組長度

└ 在陣列中找出出現次數大於N/K的數

└ 在行列都排好序的矩陣中找出指定數

└ 最長的可整合子數組的長度

└ 不重複列印排序數組中相加和為給定值的所有二元組和三元組

└ 未排序正數數組中累加和為給定值的最長子數組長度

└ 未排序數組中累加和為給定值的最長子數組系列問題

└ 未排序數組中累加和小於或等於給定值的最長子數組長度

└ 計算數組的小和

└ 自然數數組的排序

└ 奇數下標都是奇數或偶數下標都是偶數

└ 子數組的最大累加與問題

└ 子矩陣的最大累加與問題

└ 在陣列中找出一個局部最小的位置

└ 數組中子數組的最大累乘積

└ 列印N個陣列整體最大的Top K

└ 邊界都是1的最大正方形大小

└ 不包含本位置值的累乘數組

└ 數組的partition調整

└ 求最短通路值

└ 數組中未出現的最小正整數

└ 數組排序之後相鄰數的最大差值

└ 做專案的最大效益問題

└ 分金條的最小花費

└ 大樓輪廓問題

└ 加油站良好出發點問題

└ 容器盛水問題

第9章其他題目

└ 從5隨機到7隨機及其擴展

└ 一行程式碼求兩個數的最大公約數

└ 有關階乘的兩個問題

└ 判斷點是否在矩形內部

└ 判斷點是否在三角形內部

└ 摺紙問題

└ 能否完美地拼成矩形

└ 蓄水池演算法

└ 設計有setAll功能的哈希表

└ 最大的leftMax與rightMax之差的絕對值

└ 設計LRU快取結構

└ LFU快取結構設計

└ 設計RandomPool結構

└ 並查集的實現

└ 調整[0,x)區間上的數出現的機率

└ 路徑數組變成統計數組

└ 正數數組的最小不可組成和

└ 累加出整個範圍所有的數最少還需幾個數

└ 一種字串和數字的對應關係

└ 1到n中1出現的次數

└ 從N個數中等機率列印M個數

└ 判斷一個數字是否為回文數

└ 在有序旋轉數組中找到最小值

└ 在有序旋轉數組中找出一個數

└ 數字的英文表達和中文表達

└ 分糖果問題

└ 一種訊息接收並列印的結構設計

└ 隨時找到資料流的中位數

└ 在兩個長度相等的排序數組中找出上中位數

└ 在兩個排序數組中找出第k小的數

└ 兩個有序數組間相加和的Top k問題

└ 出現次數的Top k題

└ Manacher演算法

└ KMP演算法

└ 丟棋子問題

└ 畫匠問題

└ 郵局選址問題

前言/序言

自序
我能出書挺意外的。
雖然我早就知道想進入那些大公司要靠「刷」程式碼面試題來練習寫程式碼的能力，可是在6年前的某一天，我突然有了心情去看程式碼面試題長什麼樣子，於是收集了程式碼面試的題目。了解得越深入，我就越有一種恐慌的感覺，因為感覺自己什麼都不太在行，對一個歸併排序（Merge sort）寫出完整的代碼都感覺挺費勁的，面對這個馮·諾依曼發明的排序演算法，我真的有底氣說自己是電腦系的學生嗎？這種打擊並沒有持續太久，因為愛耍小聰明的人總是會特別有自信。我決定開始認真面對「刷」題這件事，但那時我根本不知道我即將面對什麼，更不會有寫書的念頭。
我把課餘時間利用起來，心想：不就是「刷」題嗎？別人能寫出來，咱也能寫出來。起初的心態是我不服，我就想告訴自己能行。過程虐心是肯定的，常常半夜因為看到一個複雜度特別低的演算法自己真的不能理解而沮喪地睡不著。當時覺得找不到資料能徹底讓我明白，書上講得太粗淺，網路上講的太散亂，程式碼寫得看不懂。起初我「刷」題的時候無數次想放棄，因為覺得這些都是什麼玩意兒！我為什麼放著好好的日子不過，去找這種罪？但我又不甘心，雖然我不懂很多解法，但我覺得它們真的很有趣。
我將能買到的所有相關書籍上的所有題目全都研究了一遍，無論是中文的還是英文的，我都硬著頭皮「啃」。寫完每題後，我都和書上的方法反覆對比。 「啃」完了五、六本書之後，距離我剛開始「刷」題目已經過16個月了。寫書？別逗了，才剛看完。
「年輕人總是會找藉口說這個東西不是我感興趣的，所以做不好是應該的。但他們沒有註意的是，你面對的事情中感興趣的事情總是少數，這就使得大多數時候你做事情的態度總是很懈怠、很消極，這使你變成了一個懈怠的人。當你真正面對自己感興趣的東西時，你發現你已經攥不緊拳頭了。」時常想起本科時的畢業設計指導老師－高鵬義老師說的這段話。說得對！對一個東西，如果你沒有透徹研究過，就不要輕易說它不精彩。這不是博愛，而是對自己認真。
「刷」題代碼達到4萬行的時候，我基本上成了國內外所有熱門「刷」題網站的日常用戶，此時我確認了一件事情，今天的代碼面試指導真的處在一個很初級的階段，這種不健全是全方面的。
例如：
常常看到一篇文章前後的語境是割裂的，作者經常根據先前的一個優良解法提出更好的最佳化方式，但整篇文章都不提及先前的解法是什麼。這就導致初學者根本看不懂。
幾乎所有的書籍都忽略例子帶來的引導作用，甚至還有不少書籍在闡述一個解法的時候只寫偽代碼，這就使得讀者在看懂意思和自己真正能寫出代碼之間其實還有很多的路要走。
代碼面試題目的特點是“多”“雜”“難”，從著手開始學習到最終達到自己想要的效果之間，自己對自己的評估根本無從談起。 「慢慢練吧，學海無涯」成為主要的心態，這就難免會產生懷疑的情緒。
看見一道新的面試題目時還是會無從下手，因為之前的學習無法做到舉一反三，對自己做過的題目缺乏總結和歸納。
難道「刷」題真的只適合「聰明人」？我不這麼看，既然大多數內容處在有待商榷的階段，那我就去學習原論文吧。
記得當時我一個人在國外，在初冬的一個下午，「刷」題已經兩年之久，快吃晚飯的時候，我突然想起自己忘了吃午飯，就衝出家門去覓食。站在7-11門前的廣場上，我拿著1.5美元的熱狗和75美分的咖啡，微溫的陽光撒在身上，遠遠望著即將消失的太陽。我停下來，把咖啡放在斑駁的石頭台子上，手裡的熱狗挺好看，香腸和洋蔥都挺新鮮，清冷的空氣吹過來，卻讓我的心緒更亂。舊金山的天空五彩斑斕，讓漂泊者頭暈目眩。哭得跟個鬼似的我除了想家，哪裡敢設想自己會出書呢？
當我意識到在網路上很難搜尋到新鮮的題目時，我已經換了兩家公司，反覆實現了600多道題目，編寫了差不多10萬行程式碼。原來只是為了找份工作「刷」題這一初心早就忘了，而變成了興趣並堅持了這麼久，我自己也感到意外。更奇怪的是，我已經完全樂在其中，同時交流慾望越來越強，時常和同事們展開這方面的討論。我發現很多書上的解法不是最優，很多題目其實和同事們討論的做法更好，可以發現高手特別多，但好像都懶得動筆。
有一天，我看到自己寫的題目，想到自己那些「抓心搔肝」的日子，突然覺得要不出書吧？我已經離不開這種感覺了，如果這不是真愛，那什麼才是？
這不是一個勵志的故事，是一個愛「刷」題的人決定把很多最優解講出來的過程，就這麼簡單。
左程雲
2015年7月20日