# 數據結構與算法/leetcode/lintcode題解
## 簡介
本文檔為數據結構和算法學習筆記,全文大致分為以下三大部分:
1. Part I為數據結構和算法基礎,介紹一些基礎的排序/鏈表/基礎算法
1. Part II為 OJ 上的編程題目實戰,按題目的內容分章節編寫,主要來源為 [https://leetcode.com/](https://leetcode.com/) 和 [http://www.lintcode.com/](http://www.lintcode.com/).
1. Part III 為附錄部分,包含如何寫簡歷和其他附加材料
本文參考了很多教材和博客,凡參考過的幾乎都給出明確鏈接,如果不小心忘記了,請不要吝惜你的評論和issue :)
本項目托管在 [https://github.com/billryan/algorithm-exercise](https://github.com/billryan/algorithm-exercise) 由 [Gitbook](https://www.gitbook.com/book/yuanbin/algorithm/details) 渲染生成 HTML 頁面。你可以在 GitHub 中 star 該項目查看更新,RSS 種子功能正在開發中。
你可以在線或者離線查看/搜索本文檔,以下方式任君選擇~
- 在線閱讀(由 Gitbook 渲染) [http://algorithm.yuanbin.me](http://algorithm.yuanbin.me)
- 離線閱讀: 推送到GitHub后會觸發 travis-ci 的編譯,相應的部分編譯輸出提供 GitHub 和 GitCafe 下載。
1. EPUB: [GitHub](https://raw.githubusercontent.com/billryan/algorithm-exercise/deploy/epub/algorithm-ebook_zh-cn.epub), [Gitbook](https://www.gitbook.com/download/epub/book/yuanbin/algorithm?lang=zh-cn), [GitCafe(中國大陸用戶適用)](https://gitcafe.com/billryan/algorithm-exercise/raw/deploy/epub/algorithm-ebook_zh-cn.epub) - 適合在 iPhone/iPad/MAC 上離線查看,實測效果極好。
1. PDF: [GitHub](https://raw.githubusercontent.com/billryan/algorithm-exercise/deploy/pdf/algorithm-ebook_zh-cn.pdf), [Gitbook](https://www.gitbook.com/download/pdf/book/yuanbin/algorithm?lang=zh-cn), [GitCafe(中國大陸用戶適用)](https://gitcafe.com/billryan/algorithm-exercise/raw/deploy/pdf/algorithm-ebook_zh-cn.pdf) - 推薦下載GitHub 和 GitCafe 的版本,Gitbook 官方使用的中文字體有點問題。
1. MOBI: [GitHub](https://raw.githubusercontent.com/billryan/algorithm-exercise/deploy/mobi/algorithm-ebook_zh-cn.mobi), [Gitbook](https://www.gitbook.com/download/mobi/book/yuanbin/algorithm?lang=zh-cn), [GitCafe(中國大陸用戶適用)](https://gitcafe.com/billryan/algorithm-exercise/raw/deploy/mobi/algorithm-ebook_zh-cn.mobi) - Kindle 專用,未測試,感覺不適合在 Kindle 上看此類書籍,盡管 Kindle 的屏幕對眼睛很好...
- Google 站內搜索: `keywords site:algorithm.yuanbin.me`
- Swiftype 站內搜索: 可使用網頁右下方的 `Search this site` 進行站內搜索
## 許可證
本作品采用 **知識共享署名-相同方式共享 4.0 國際許可協議** 進行許可。**傳播此文檔時請注意遵循以上許可協議。** 關于本許可證的更多詳情可參考 [http://creativecommons.org/licenses/by-sa/4.0/](http://creativecommons.org/licenses/by-sa/4.0/)
本著獨樂樂不如眾樂樂的開源精神,我將自己的算法學習筆記公開和小伙伴們討論,希望高手們不吝賜教。
## 多國語言
- [English](http://algorithm.yuanbin.me/en/index.html) maintained by who?
- [簡體中文](http://algorithm.yuanbin.me/zh-cn/index.html) maintained by [@billryan](https://github.com/billryan)
- [繁體中文](http://algorithm.yuanbin.me/zh-tw/index.html) maintained by [@CrossLuna](https://github.com/CrossLuna)
## 如何貢獻
如果你發現任何有錯誤的地方或是想更新/翻譯本文檔,請毫不猶豫地猛擊 [貢獻指南](https://github.com/billryan/algorithm-exercise/blob/master/contributing_zh-cn.md).
## 捐助
添加這一小節其實是有點誠惶誠恐的,畢竟這本小書目前還很不完善,把捐助信息貼出來不臉紅嗎?:-( 但既然前些天有網友專門發郵件來問這個事,我就大概說下我目前的想法,先以 @billryan 為例,其他 Contributor 后續補充,捐助者后期會單獨整理公布,當然這是在征得捐助人同意的前提下進行的。除了在 GitHub 上協助編寫文檔外,你還可以以下面幾種方式回饋各位貢獻者:
### 郵寄明信片
@billryan 喜歡收集各種明信片,來者不拒~ 郵寄的話可以郵寄至 `上海市閔行區上海交通大學閔行校區電院群樓5號樓307`,這個地址2016 年3月前有效,收件人:`袁斌`。
### 送書
除了郵寄明信片,你還可以買本書送給各位貢獻者,@billryan 的地址見上節。
### 支付寶打賞

金額隨意。
### PayPal
賬戶名:yuanbin2014(at)gmail.com 付款時選擇 friends and family
金額隨意。
## 如何練習算法
雖說練習算法偏向于算法本身,但是好的代碼風格還是很有必要的。粗略可分為以下幾點:
- 代碼塊可為三大塊:異常處理(空串和邊界處理),主體,返回
- 代碼風格(**可參考Google的編程語言規范**)
1. 變量名的命名(有意義的變量名)
1. 縮進(語句塊)
1. 空格(運算符兩邊)
1. 代碼可讀性(即使if語句只有一句也要加花括號)
- 《代碼大全》中給出的參考
而對于實戰算法的過程中,我們可以采取如下策略:
1. 總結歸類相似題目
1. 找出適合同一類題目的模板程序
1. 對基礎題熟練掌握
以下整理了一些最近練習算法的網站資源,和大家共享之。
## 在線OJ及部分題解
- [LeetCode Online Judge](https://leetcode.com/) - 找工作方面非常出名的一個OJ,每道題都有 discuss 頁面,可以看別人分享的代碼和討論,很有參考價值,相應的題解非常多。不過在線代碼編輯框不太好用,寫著寫著框就拉下來了,最近評測速度比 lintcode 快很多,而且做完后可以看自己代碼的運行時間分布,首推此 OJ 刷面試相關的題。
- [LintCode | Coding interview questions online training system](http://www.lintcode.com) - 和leetcode類似的在線OJ,但是篩選和寫代碼時比較方便,左邊為題目,右邊為代碼框。還可以在`source`處選擇 CC150 或者其他來源的題。會根據系統locale選擇中文或者英文,可以拿此 OJ 輔助 leetcode 進行練習。
- [LeetCode題解 - GitBook](https://www.gitbook.com/book/siddontang/leetcode-solution/details) - 題解部分十分詳細,比較容易理解,但部分題目不全。
- [FreeTymeKiyan/LeetCode-Sol-Res](https://github.com/FreeTymeKiyan/LeetCode-Sol-Res) - Clean, Understandable Solutions and Resources on LeetCode Online Judge Algorithms Problems.
- [soulmachine/leetcode](https://github.com/soulmachine/leetcode) - 含C++和Java兩個版本的題解。
- [Woodstock Blog](http://okckd.github.io/) - IT,算法及面試。有知識點及類型題總結,特別贊。
- [ITint5 | 專注于IT面試](http://www.itint5.com/) - 文章質量很高,也有部分公司面試題評測。
- [Acm之家,專業的ACM學習網站](http://www.acmerblog.com/) - 各類題解
- [牛客網-專業IT筆試面試備考平臺,最全求職題庫,全面提升IT編程能力](http://www.nowcoder.com/) - 國內一個IT求職方面的綜合性網站,比較適合想在國內求職的看看。感謝某位美女的推薦 :)
## 其他資源
- [九章算法](http://www.jiuzhang.com/) - 代碼質量大多不錯,但是不太全。這家也提供有償輔導。
- [七月算法 - julyedu.com](http://julyedu.com/) - july大神主導的在線算法輔導。
- [刷題 | 一畝三分地論壇](http://www.1point3acres.com/bbs/forum-84-1.html) - 時不時就會有驚喜放出。
- [VisuAlgo - visualising data structures and algorithms through animation](http://www.comp.nus.edu.sg/~stevenha/visualization/index.html) - 相當碉堡的數據結構和算法可視化。
- [Data Structure Visualization](http://www.cs.usfca.edu/~galles/visualization/Algorithms.html) - 同上,非常好的動畫演示!!涵蓋了常用的各種數據結構/排序/算法。
- [結構之法 算法之道](http://blog.csdn.net/v_JULY_v) - 不得不服!
- [julycoding/The-Art-Of-Programming-By-July](https://github.com/julycoding/The-Art-Of-Programming-By-July) - 程序員面試藝術的電子版
- [程序員面試、算法研究、編程藝術、紅黑樹、數據挖掘5大系列集錦](http://blog.csdn.net/v_july_v/article/details/6543438)
- [專欄:算法筆記——《算法設計與分析》](http://blog.csdn.net/column/details/lf-algoritnote.html) - CSDN上對《算法設計與分析》一書的學習筆記。
- [我的算法學習之路 - Lucida](http://zh.lucida.me/blog/on-learning-algorithms/) - Google 工程師的算法學習經驗分享。
## 書籍推薦
本節后三項參考自九章微信分享,謝過。
- [Algorithm Design (豆瓣)](http://book.douban.com/subject/1475870/)
- [The Algorithm Design Manual](http://www.amazon.com/exec/obidos/ASIN/1848000693/thealgorithmrepo), 作者還放出了自己上課的視頻和slides - [Skiena's Audio Lectures](http://www3.cs.stonybrook.edu/~algorith/video-lectures/),[The Algorithm Design Manual (豆瓣)](http://book.douban.com/subject/3072383/)
- 大部頭有 *Introduction to Algorithm* 和 TAOCP
- *Cracking The Coding Interview*. 著名的CTCI(又稱CC150),Google, Mircosoft, LinkedIn 前HR離職之后寫的書,從很全面的角度剖析了面試的各個環節和題目。除了算法數據結構等題以外,還包含OO Design, Database, System Design, Brain Teaser等類型的題目。**準備北美面試的同學一定要看。**
- *劍指Offer*。適合國內找工作的同學看看,英文版叫Coding Interviews. 作者是何海濤(Harry He)。Amazon上可以買到。有大概50多題,題目的分析比較全面,會從面試官的角度給出很多的建議和show各種坑。
- *進軍硅谷* -- 程序員面試揭秘。有差不多150題。
- Preface
- Part I - Basics
- Basics Data Structure
- String
- Linked List
- Binary Tree
- Huffman Compression
- Queue
- Heap
- Stack
- Set
- Map
- Graph
- Basics Sorting
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
- Heap Sort
- Bucket Sort
- Counting Sort
- Radix Sort
- Basics Algorithm
- Divide and Conquer
- Binary Search
- Math
- Greatest Common Divisor
- Prime
- Knapsack
- Probability
- Shuffle
- Basics Misc
- Bit Manipulation
- Part II - Coding
- String
- strStr
- Two Strings Are Anagrams
- Compare Strings
- Anagrams
- Longest Common Substring
- Rotate String
- Reverse Words in a String
- Valid Palindrome
- Longest Palindromic Substring
- Space Replacement
- Wildcard Matching
- Length of Last Word
- Count and Say
- Integer Array
- Remove Element
- Zero Sum Subarray
- Subarray Sum K
- Subarray Sum Closest
- Recover Rotated Sorted Array
- Product of Array Exclude Itself
- Partition Array
- First Missing Positive
- 2 Sum
- 3 Sum
- 3 Sum Closest
- Remove Duplicates from Sorted Array
- Remove Duplicates from Sorted Array II
- Merge Sorted Array
- Merge Sorted Array II
- Median
- Partition Array by Odd and Even
- Kth Largest Element
- Binary Search
- Binary Search
- Search Insert Position
- Search for a Range
- First Bad Version
- Search a 2D Matrix
- Search a 2D Matrix II
- Find Peak Element
- Search in Rotated Sorted Array
- Search in Rotated Sorted Array II
- Find Minimum in Rotated Sorted Array
- Find Minimum in Rotated Sorted Array II
- Median of two Sorted Arrays
- Sqrt x
- Wood Cut
- Math and Bit Manipulation
- Single Number
- Single Number II
- Single Number III
- O1 Check Power of 2
- Convert Integer A to Integer B
- Factorial Trailing Zeroes
- Unique Binary Search Trees
- Update Bits
- Fast Power
- Hash Function
- Count 1 in Binary
- Fibonacci
- A plus B Problem
- Print Numbers by Recursion
- Majority Number
- Majority Number II
- Majority Number III
- Digit Counts
- Ugly Number
- Plus One
- Linked List
- Remove Duplicates from Sorted List
- Remove Duplicates from Sorted List II
- Remove Duplicates from Unsorted List
- Partition List
- Two Lists Sum
- Two Lists Sum Advanced
- Remove Nth Node From End of List
- Linked List Cycle
- Linked List Cycle II
- Reverse Linked List
- Reverse Linked List II
- Merge Two Sorted Lists
- Merge k Sorted Lists
- Reorder List
- Copy List with Random Pointer
- Sort List
- Insertion Sort List
- Check if a singly linked list is palindrome
- Delete Node in the Middle of Singly Linked List
- Rotate List
- Swap Nodes in Pairs
- Remove Linked List Elements
- Binary Tree
- Binary Tree Preorder Traversal
- Binary Tree Inorder Traversal
- Binary Tree Postorder Traversal
- Binary Tree Level Order Traversal
- Binary Tree Level Order Traversal II
- Maximum Depth of Binary Tree
- Balanced Binary Tree
- Binary Tree Maximum Path Sum
- Lowest Common Ancestor
- Invert Binary Tree
- Diameter of a Binary Tree
- Construct Binary Tree from Preorder and Inorder Traversal
- Construct Binary Tree from Inorder and Postorder Traversal
- Subtree
- Binary Tree Zigzag Level Order Traversal
- Binary Tree Serialization
- Binary Search Tree
- Insert Node in a Binary Search Tree
- Validate Binary Search Tree
- Search Range in Binary Search Tree
- Convert Sorted Array to Binary Search Tree
- Convert Sorted List to Binary Search Tree
- Binary Search Tree Iterator
- Exhaustive Search
- Subsets
- Unique Subsets
- Permutations
- Unique Permutations
- Next Permutation
- Previous Permuation
- Unique Binary Search Trees II
- Permutation Index
- Permutation Index II
- Permutation Sequence
- Palindrome Partitioning
- Combinations
- Combination Sum
- Combination Sum II
- Minimum Depth of Binary Tree
- Word Search
- Dynamic Programming
- Triangle
- Backpack
- Backpack II
- Minimum Path Sum
- Unique Paths
- Unique Paths II
- Climbing Stairs
- Jump Game
- Word Break
- Longest Increasing Subsequence
- Palindrome Partitioning II
- Longest Common Subsequence
- Edit Distance
- Jump Game II
- Best Time to Buy and Sell Stock
- Best Time to Buy and Sell Stock II
- Best Time to Buy and Sell Stock III
- Best Time to Buy and Sell Stock IV
- Distinct Subsequences
- Interleaving String
- Maximum Subarray
- Maximum Subarray II
- Longest Increasing Continuous subsequence
- Longest Increasing Continuous subsequence II
- Graph
- Find the Connected Component in the Undirected Graph
- Route Between Two Nodes in Graph
- Topological Sorting
- Word Ladder
- Bipartial Graph Part I
- Data Structure
- Implement Queue by Two Stacks
- Min Stack
- Sliding Window Maximum
- Longest Words
- Heapify
- Problem Misc
- Nuts and Bolts Problem
- String to Integer
- Insert Interval
- Merge Intervals
- Minimum Subarray
- Matrix Zigzag Traversal
- Valid Sudoku
- Add Binary
- Reverse Integer
- Gray Code
- Find the Missing Number
- Minimum Window Substring
- Continuous Subarray Sum
- Continuous Subarray Sum II
- Longest Consecutive Sequence
- Part III - Contest
- Google APAC
- APAC 2015 Round B
- Problem A. Password Attacker
- Microsoft
- Microsoft 2015 April
- Problem A. Magic Box
- Problem B. Professor Q's Software
- Problem C. Islands Travel
- Problem D. Recruitment
- Microsoft 2015 April 2
- Problem A. Lucky Substrings
- Problem B. Numeric Keypad
- Problem C. Spring Outing
- Microsoft 2015 September 2
- Problem A. Farthest Point
- Appendix I Interview and Resume
- Interview
- Resume