程序員編程藝術：面試和算法心得

About

看過結構之法算法之道blog的朋友可能知道，從2010年10月起，July 開始整理一個微軟面試100題的系列，他在整理這個系列的過程當中，越來越強烈的感覺到，可以從那100題中精選一些更為典型的題，每一題詳細闡述成章，不斷優化，于此，便成了程序員編程藝術系列。

原編程藝術系列從2011年4月至今，寫了42個編程問題，在創作的過程當中，得到了很多朋友的支持，特別是博客上隨時都會有朋友不斷留言，或提出改進建議，或show出自己的思路、代碼，或指正bug。

為了方便大家更好的改進、優化、增補編程藝術系列，特把博客上的這個程序員編程藝術系列和博客內其它部分經典文章同步到此，成立本項目「Csdn 600萬博客結構之法算法之道部分經典博文優化版：《程序員編程藝術 — 面試和算法心得》」，邀請各位一起修正和優化。

若發現任何問題、錯誤、bug，或可以優化的每一段代碼，歡迎隨時pull request或發issue反饋，thanks。

Start Reading

• 中文目錄 Enhancement in progress
• English Contents Translation in progress

How To Contribute

• 邀請大家幫忙把github上的文章導出到word上，歡迎到這里認領：https://github.com/julycoding/The-Art-Of-Programming-By-July/issues/337 」
• 一章一章的測試所有代碼，指正 bug，修正錯誤。 「必選，可到這里認領：https://github.com/julycoding/The-Art-Of-Programming-By-July/issues/210 」
• 優化原文章上的C/C++ 代碼，優化后的代碼可以放到ebook/code文件夾內，并注意代碼命名規范的問題：https://github.com/julycoding/The-Art-Of-Programming-By-July/issues/234 。 「必選」
• 添加其它語言如Java、python、go 的代碼，放在ebook/code文件夾內，同樣如上，注意代碼命名規范的問題。 「可選」
• 重繪所有的圖片：https://github.com/julycoding/The-Art-Of-Programming-by-July/issues/80
• 翻譯成英文版，參考中文目錄，把翻譯后的文章編輯到這English Version,注：不必逐字翻譯，精簡大氣即可（如有興趣翻譯，請到這里領取感興趣的章節翻譯：https://github.com/julycoding/The-Art-Of-Programming-by-July/issues/84 )
• 自己主導續寫新的章節；
• 任何你想做的事情，包括痛批你覺得寫的爛的章節，所有你的意見都將改進此系列。

你可以做以上任何一件或幾件事情，如遇到任何問題或疑惑，咱們可以隨時討論： https://github.com/julycoding/The-Art-Of-Programming-by-July/issues?state=open。「如不知如何在github上提交及同步作者的更新，可參考此文：http://www.cnblogs.com/rubylouvre/archive/2013/01/24/2874694.html 」

Code Style

本項目暫約定以下代碼風格(不斷逐條添加中)：

• 關于空格
  • 所有代碼使用4個空格縮進
  • 運算符后使用一個空格
  • "," 和for循環語句中的";" 后面跟上一個空格
  • 條件、分支保留字，如 if for while else switch 后留出一個空格
  • "[]", "."和"->" 前后不留空格
• 用空行把大塊代碼分成邏輯上的“段落
• C 指針中的指針符靠近類型名，如寫成int* p，而不寫成int *p
• 關于標點
  • 中文表述，使用中文全角的標點符號，如：（）、。，？
  • 數學公式（包括文中混排的公式）和英文代碼，使用英文半角的標點符號，如：(),.?…
• 關于注釋
  • 注釋統一用中文
  • 盡量統一用"http://"，一般不用"/*...*/"
• 關于命名
  • 類名為大寫字母開頭的單詞組合
  • 函數名比較長，由多個單詞組成的，每個單詞的首字母大寫，如int MaxSubArray()；函數名很短，由一個單詞組成，首字母小寫，比如int swap()
  • 變量名比較長，由多個單詞組成的，首個單詞的首字母小寫，后面緊跟單詞的首字母大寫，如maxEnd；變量名很短，由一個單詞組成，首字母小寫，如left
  • 變量盡量使用全名，能夠描述所要實現的功能，如 highestTemprature；對于已經公認了的寫法才使用縮寫，如 tmp mid prev next
  • 變量名能“望文生義”，如v1, v2不如area, height
  • 常量的命名都是大寫字母的單詞，之間用下劃線隔開，比如MY_CONSTANT
  • il < 4384 和 inputLength < MAX_INPUT_LENGTH，后一種寫法更好
• 一個函數只專注做一件事
• 時間復雜度小寫表示，如O(nlogn)，而不寫成O(N*logN)
• 正文中絕大部分采用C實現，少量C++代碼，即以C為主，但不去刻意排斥回避C++；
• 關于的地得
  • 形容詞（代詞） + 的 + 名詞，例如：我的小蘋果
  • 副詞 + 地 + 動詞，例如：慢慢地走
  • 動詞 + 得 + 副詞，例如：走得很快
• 關于參考文獻
  • 格式：主要責任者.書名〔文獻類型標識 ] .其他責任者.版本.出版地：出版者，出版年.文獻數量.叢編項.附注項.文獻標準編號。例子：1 劉少奇.論共產黨員的修養.修訂 2 版.北京：人民出版社，1962.76 頁.
• 專業術語
  • 統一一律用“樹結點”，而不是“樹節點”。
  • 用左子樹、右子樹表示樹的左右子樹沒問題，但是否用左孩子、右孩子表示樹或子樹的左右結點？
• ..
• 此外，更多C++ 部分可參考Google C++ Style Guide，中文版見：http://zh-google-styleguide.readthedocs.org/en/latest/contents/ ；

有何問題或補充意見，咱們可以隨時到這里討論：https://github.com/julycoding/The-Art-Of-Programming-By-July/issues/81 。

Ver Note

• 2010年10月11日，在CSDN上正式開博，感謝博客上所有讀者的訪問、瀏覽、關注、支持、留言、評論、批評、指正；
• 2011年1月，在學校的時候，第一家出版社聯系出書，因“時機未到，尚需積累”的原因婉拒，隨后第二家、第三家出版社陸續聯系，因總感覺寫書的時機還沒到，一律婉拒；
• 2011年10月， 當時在圖靈教育的楊海玲老師（現在人民郵電信息技術分社）再度聯系出書，再度認為“時機未到”；
• 2014年1月18日，想通了一件事：如果什么都不去嘗試，那么將年年一事無成，所以元旦一過，便正式確認今2014年之內要把拖了近3年之久的書出版出來；
• 2013年12月-2014年3月，本github的Contributors 轉移結構之法算法之道blog的部分經典文章到本github上，感謝這近100位Contributors，包括但不限于：
  • Boshen（除我之外，貢獻本github的次數最多）
  • sallen450
  • marchtea（專門為本github書稿弄了一個HTML網頁）
  • nateriver520（勸我把書稿放在github上，才有了本github）
• 2014年3月，通讀全部文章，修正明顯錯誤，并邀請部分朋友review本github上的全部文章，包括cherry、王威揚、鄔勇、高增琪、武博文、楊忠寶等；
• 2014年4月
  • 整個4月，精簡篇幅，調整目錄，Contributors 貢獻其它語言代碼，并翻譯部分文章；
  • 4月25日，跟人民郵電出版社信息技術分社簽訂合同，書名暫定《程序員編程藝術：面試和算法心得》，有更好的名字再替換。
• 2014年5月，逐章逐節逐行逐字優化文字描述，測試重寫優化每一段每一行每一個代碼，確定代碼基本風格；
• 2014年6月
  • 第一周，壓縮篇幅，寧愿量少，但求質精；
  • 第二周，全面 review；
  • 第三周，本github的部分Contributors 把全部文章從github轉到word上，這部分contributors 包括包括：zhou1989、qiwsir、DogK、x140yu、ericxk、zhanglin0129、idouba.net、gaohua、 kelvinkuo等；
  • 第四周，繼續在Word 上做出最后徹底的改進，若未發現bug或pull request，本github將暫不再改動；
  • 6月30日，與出版社約定的交稿日期延期，理由：目前版本不是所能做到的最好的版本。
• 2014年7月，邀請部分好友進行第一輪審稿，包括曹鵬、鄒偉、林奔、王婷、何歡，其中，曹鵬重寫優化了部分代碼。此外，葛立娜對書稿中的語言描述做了不少改進；
• 2014年8月
  • 8月上旬，新增KMP一節內容；
  • 8月下旬，重點修改SVM一節內容；
• 2014年9月
  • 9月上旬，和一些朋友一起重繪稿件中的部分圖和公式，這部分朋友包括顧運（@陳笙）、mastermay、在山東大學讀研二的豐俊丙、廈門大學電子工程系陳友和等等；
  • 9月下旬，再度邀請另一部分好友進行第二輪審稿，包括許利杰、王亮、陳贏、李祥老師、litaoye等，并在微博上公開征集部分讀者審稿，包括李元超、劉琪等等；
• 2014年10月
  • 10月8日起，開始一章一章陸續交Word 稿給出版社初審
  • 10月9日，第一章、字符串完成修改；
  • 10月10日，第二章、數組完成修改；
  • 10月22日，第三章、樹完成修改；
• 2014年11月
  • 11月5日，第三章、樹完成第二版修改，主要修正部分圖片、公式、語言描述的錯誤；
• 2014年12月
  • 12月1日，第四章、查找完成修改。至此，前4 章的修改稿交付出版社。
  • 12月8日，第五章、動態規劃完成修改，等出版社反饋中。一個人堅持有點枯燥。
  • 12月31日，第六章仍未修改完。
• 2015年3月，出版社重繪全部圖片和公式，編輯加工，復審，三審；
• 2015年4月，發稿審批，排版校對；
• 2015年5月，出膠片，印刷，裝訂成書；

第一部分 數據結構

• 第一章 字符串
  • 1.0 本章導讀
  • 1.1 旋轉字符串
  • 1.2 字符串包含
  • 1.3 字符串轉換成整數
  • 1.4 回文判斷
  • 1.5 最長回文子串
  • 1.6 字符串的全排列
  • 1.10 本章習題
• 第二章 數組
  • 2.0 本章導讀
  • 2.1 尋找最小的 k 個數
  • 2.2 尋找和為定值的兩個數
  • 2.3 尋找和為定值的多個數
  • 2.4 最大連續子數組和
  • 2.5 跳臺階
  • 2.6 奇偶排序
  • 2.7 荷蘭國旗
  • 2.8 矩陣相乘
  • 2.9 完美洗牌
  • 2.15 本章習題
• 第三章 樹
  • 3.0 本章導讀
  • 3.1 紅黑樹
  • 3.2 B樹
  • 3.3 最近公共祖先LCA
  • 3.10 本章習題

第二部分 算法心得

• 第四章 查找匹配
  • 4.1 有序數組的查找
  • 4.2 行列遞增矩陣的查找
  • 4.3 出現次數超過一半的數字
• 第五章 動態規劃
  • 5.0 本章導讀
  • 5.1 最大連續乘積子串
  • 5.2 字符串編輯距離
  • 5.3 格子取數
  • 5.4 交替字符串
  • 5.10 本章習題

第三部分 綜合演練

• 第六章 海量數據處理
  • 6.0 本章導讀
  • 6.1 關聯式容器
  • 6.2 分而治之
  • 6.3 simhash算法
  • 6.4 外排序
  • 6.5 MapReduce
  • 6.6 多層劃分
  • 6.7 Bitmap
  • 6.8 Bloom filter
  • 6.9 Trie樹
  • 6.10 數據庫
  • 6.11 倒排索引
  • 6.15 本章習題
• 第七章 機器學習
  • 7.1 K 近鄰算法
  • 7.2 支持向量機

• 附錄 更多題型

  • 附錄A 語言基礎
  • 附錄B 概率統計
  • 附錄C 智力邏輯
  • 附錄D 系統設計
  • 附錄E 操作系統
  • 附錄F 網絡協議

項目主頁：http://www.baiduhome.net/lib/view/home/1420682308796