乾貨 | 算法和編程面試題精選TOP50!(附代碼+解題思路+答案)

作者 | javinpaul

編譯 | 王天宇、Jane

整理 | Jane

【導讀】之前我們給同學們推薦了很多關於 Python 的面試資源，大家都表示很有用。這次營長表示要翻 Java 的牌子啦~ 應大家的強烈反饋，我們找了一套 Java 語言的算法和編程的面試題。

這份面試資源主要包含五部分內容：數組、鍊表、字符串、二叉樹和重要算法（如排序算法）的編程面試題，其中每部分內容我們都列出了一些最常被問到的熱門問題，並且在每個題目後給出了可以參考的解決思路和代碼，因為題目較多，我們沒有羅列所有的方法和代碼，只給出了訪問地址。相信大家在掌握了這些內容後，一定可以提升實力、信心大增。

數組

數組，將元素存儲到內存的連續位置中，是最基本的數據結構。在任何和編程相關的面試中，都會被問到和數組相關的問題，可以說是非常熱門的考題之一。比如：將數組反轉、對數組進行排序、搜索數組中的元素等。

數組數據結構的主要優點是如果知道索引就可以通過 O(l) 進行快速搜索，但是在數組中添加和刪除元素的速度會很慢，因為數組一旦被創建，就無法更改其大小。如果需要創建更長或更短的數組，得先創建一個新數組，再把原數組中的所有元素複製到新創建的數組中。

解決數組相關問題的關鍵是要熟悉數組的數據結構和基本的構造，如循環、遞歸等等；下面給出了 10 道熱門面試題幫助大家掌握知識並進行練習。

▌1.給定一個 1-100 的整數數組，請找到其中缺少的數字。

解決方法與代碼：

https://javarevisited.blogspot.com/2014/11/how-to-find-missing-number-on-integer-array-java.html

▌2.請在給出的整數數組中找到重複的數字。

解決方法與代碼：

http://javarevisited.blogspot.com/2014/01/how-to-remove-duplicates-from-array-java-without-collection-API.html

▌3.如何在未排序的整數數組中找到最大值與最小值？

解決方法與代碼：

http://java67.blogspot.com/2014/02/how-to-find-largest-and-smallest-number-array-in-java.html

▌4.在給定的成對整數數組中，請找出所有總和等於給定數字的組合。

解決方法與代碼：

http://javarevisited.blogspot.com/2014/08/how-to-find-all-pairs-in-array-of-integers-whose-sum-equal-given-number-java.html

▌5.如果數組中有多個重複項，如何找到重複的數字？

解決方法與代碼：

http://javarevisited.blogspot.com/2014/03/3-ways-to-find-first-non-repeated-character-String-programming-problem.html

▌6.用 Java 語言實現，在給出的數組中，刪除重複項。

解決方法與代碼：

http://javarevisited.blogspot.com/2014/01/how-to-remove-duplicates-from-array-java-without-collection-API.html

▌7.用 quicksort 算法實現對整數數組的排序。

解決方法和代碼：

http://javarevisited.blogspot.com/2014/08/quicksort-sorting-algorithm-in-java-in-place-example.html

▌8.如何刪除現有數組中的重複項？

解決方法和代碼：

http://javarevisited.blogspot.com/2014/01/how-to-remove-duplicates-from-array-java-without-collection-API.html

▌9.用 Java 語言把數組進行反轉。

解決方法和代碼:

http://javarevisited.blogspot.com/2013/03/how-to-reverse-array-in-java-int-String-array-example.html

▌10.如何在不調用庫的情況下刪除數組中的重複項？

解決方法和代碼：

http://javarevisited.blogspot.sg/2014/01/how-to-remove-duplicates-from-array-java-without-collection-API.html

十個問題太少？更多複雜問題，可訪問：

http://javarevisited.blogspot.sg/2015/06/top-20-array-interview-questions-and-answers.html

鍊表

鍊表是另一種常見的數據結構，和數組相似，鍊表也是線性的數據結構並且以線性方式存儲元素。而與數組不同的是，鍊表不是將元素存儲在連續的位置中，而是可以存儲在任意位置，彼此之間通過節點相互連接。

鍊表也可以說就是一個節點列表，每個節點中包含存儲的值和下一個節點的地址。也正是因為這種結構，在鍊表裡添加和刪除元素很容易，你只需要更改連結而不用創建新的數組。但是搜索會很困難，並且在單鍊表中找到一個元素就需要 O（n）個時間。

鍊表有多種形式，如：單鍊表，允許你在一個方向上進行遍歷；雙鍊表，可以在兩個方向上進行遍歷；循環鍊表，最後節點的指針指向第一個節點從而形成一個環形的鏈；因為鍊表是一種遞歸數據結構，所以在解決鍊表問題時，熟練掌握遞歸算法就顯得更加重要了。

下面是關於鍊表的一些最常見、熱門的面試問題，大家可以著重練習：

▌1.如何在一次遞歸後找到單鍊表的中間元素？

解決方法和代碼：

http://javarevisited.blogspot.sg/2012/12/how-to-find-middle-element-of-linked-list-one-pass.html

▌2.檢查給定的鍊表中是否包含循環鍊表，並找出循環鍊表的起始節點。

解決方法和代碼：

http://javarevisited.blogspot.sg/2013/05/find-if-linked-list-contains-loops-cycle-cyclic-circular-check.html

▌3.如何將列表反轉（倒置）？

解決方法和代碼：

http://www.java67.com/2016/07/how-to-reverse-singly-linked-list-in-java-example.html

▌4.如何在沒有遞歸的情況下反轉單鍊表？

解決方法和代碼：

http://javarevisited.blogspot.sg/2017/03/how-to-reverse-linked-list-in-java-using-iteration-and-recursion.html

▌5.刪除未經過排序的鍊表中重複的節點。

解決方法和代碼：

https://www.geeksforgeeks.org/remove-duplicates-from-an-unsorted-linked-list/

▌6.計算單鍊表的長度。

解決方法和代碼：

http://javarevisited.blogspot.sg/2016/05/how-do-you-find-length-of-singly-linked.html

▌7.找出單鍊表中倒數第三個節點。

解決方法和代碼：

http://javarevisited.blogspot.sg/2016/07/how-to-find-3rd-element-from-end-in-linked-list-java.html

▌8.如何使用 Stack 查找兩個鍊表的和？

解決方法和代碼：

https://www.geeksforgeeks.org/sum-of-two-linked-lists/

這些問題可以幫你提升解決問題的能力，加深對鍊表數據結構的了解。

關於數組和鍊表間的區別，可詳細閱讀：

http://javarevisited.blogspot.sg/2013/07/difference-between-array-and-linked-list-java.html

更多複雜問題，可訪問：

http://javarevisited.blogspot.sg/2017/07/top-10-linked-list-coding-questions-and.html

字符串

除了數組和鍊表數據結構，字符串是應聘過程中編程面試的另一個熱門問題。在我參加過的編程面試中，每一個都涉及了有關字符串的問題。

值得慶幸的是，如果你了解數組，你可以很容易解決關於字符串的問題，因為字符串本身就是一個由字符組成的數組。

因此，你學過的所有用來解決數組編程問題的知識，也可以用來解決字符串的編程問題。

以下是一些在編程面試中高頻出現的字符串問題：

▌1.如何輸出字符串中重複的字符？

解決方法與代碼：

http://java67.blogspot.sg/2014/03/how-to-find-duplicate-characters-in-String-Java-program.html

▌2.如何判斷兩個字符串是否互為回文？

解決方法與代碼：

http://javarevisited.blogspot.sg/2013/03/Anagram-how-to-check-if-two-string-are-anagrams-example-tutorial.html

▌3.如何找出字符串首個非重複的字符？

解決方法與代碼：

https://javarevisited.blogspot.com/2014/03/3-ways-to-find-first-non-repeated-character-String-programming-problem.html

▌4.如何用遞歸的方法將字符串進行反轉？

解決方法與代碼：

https://javarevisited.blogspot.com/2012/01/how-to-reverse-string-in-java-using.html

▌5.如何判斷一個字符串是否只包含數字？

解決方法與代碼：

http://javarevisited.blogspot.sg/2012/10/regular-expression-example-in-java-to-check-String-number.html

▌6.如何找到字符串中重複的字符？

解決方法與代碼：

http://java67.blogspot.sg/2014/03/how-to-find-duplicate-characters-in-String-Java-program.html

▌7.如何計算一個字符串中元音字母和輔音字母的個數？

解決方法與代碼：

http://java67.blogspot.sg/2013/11/how-to-count-vowels-and-consonants-in-Java-String-word.html

▌8.如何計算一個給定字符在字符串中出現的次數？

解決方法與代碼：

https://javarevisited.blogspot.com/2012/12/how-to-count-occurrence-of-character-in-String.html

▌9.如何找出一個字符串的所有排列組合？

解決方法與代碼：

http://javarevisited.blogspot.com/2015/08/how-to-find-all-permutations-of-string-java-example.html

▌10.在不使用任何方法庫的情況下，如何將一句話中的單詞進行反轉？

解決方法與代碼：

http://www.java67.com/2015/06/how-to-reverse-words-in-string-java.html

▌11.如何判斷一個字符串是否為另一個字符串循環移動的結果？

解決方法與代碼：

http://www.java67.com/2017/07/string-rotation-in-java-write-program.html

▌12.如何判斷一個字符串是否為回文？

解決方法與代碼：

http://java67.blogspot.com/2015/06/how-to-check-is-string-is-palindrome-in.html

這些問題有助於提高你對字符串數據結構的理解。如果你在沒有外界幫助的情況下，可以解決所有這些字符串問題，那麼你的水平已經很棒了。

若想了解更多複雜的問題，建議學習一下《Algorithm Design Manual by Steven Skiena》這本書中的問題，裡面大都是難度很高的算法問題。

      

如果你需要更多的練習，可以參考這一組問題，包含20個字符串編程問題。

問題連結：

https://javarevisited.blogspot.com/2015/01/top-20-string-coding-interview-question-programming-interview.html

二叉樹

到目前為止，我們只涉及了線性數據結構，但現實世界的所有信息都不是以線性的形式展現的，因此出現了樹結構。

樹結構是一種將數據進行分層存儲的數據結構。根據數據存儲方式的不同，存在不同類型的樹，比如二叉樹，其中每個節點至多有兩個子節點。

和二叉查找樹一樣，它們都是最流行的樹形式的數據結構。因此，你會發現很多問題基於它們的問題，如計算節點數，如何進行遍歷，計算深度，判斷它們是否平衡。

解決二叉樹問題的關鍵是要有紮實的知識理論，如什麼是二叉樹的大小或深度，什麼是葉，以及什麼是節點。還有對當前流行的遍歷算法的理解，如前序遍歷、後序遍歷和中序遍歷。

下面是一系列常在軟體開發面試中出現的二叉樹熱門問題：

▌1.如何部署使用二叉查找樹？

解決方法與代碼：

http://javarevisited.blogspot.sg/2015/10/how-to-implement-binary-search-tree-in-java-example.html#axzz4wnEtnNB3

▌2.給定一個二叉樹，如何進行前序遍歷？

解決方法與代碼：

http://javarevisited.blogspot.sg/2016/07/binary-tree-preorder-traversal-in-java-using-recursion-iteration-example.html#axzz5ArdIFI7y

▌3.在不使用遞歸的情況下，如何對給定二叉樹進行前序遍歷？

解決方法與代碼：

http://www.java67.com/2016/07/binary-tree-preorder-traversal-in-java-without-recursion.html

▌4.給定一個二叉樹，如何進行中序遍歷？

解決方法與代碼：

http://www.java67.com/2016/08/binary-tree-inorder-traversal-in-java.html

▌5.在不使用遞歸的情況下，如何使用中序遍歷輸出給定二叉樹的所有節點？

解決方法與代碼：

http://www.java67.com/2016/08/binary-tree-inorder-traversal-in-java.html

▌6.如何實現後序遍歷算法？

解決方法與代碼：

http://www.java67.com/2016/10/binary-tree-post-order-traversal-in.html

▌7.在不使用遞歸的情況下，如何對二叉樹進行後序遍歷？

解決方法與代碼：

http://www.java67.com/2017/05/binary-tree-post-order-traversal-in-java-without-recursion.html

▌8.如何輸出一個二叉查找樹的所有葉子？

解決方法與代碼：

http://www.java67.com/2016/09/how-to-print-all-leaf-nodes-of-binary-tree-in-java.html

▌9.如何計算一個給定二叉樹的葉子節點數目？

解決方法與代碼：

http://javarevisited.blogspot.sg/2016/12/how-to-count-number-of-leaf-nodes-in-java-recursive-iterative-algorithm.html

▌10.給定一個數組，如何對其進行二叉搜索？

解決方法與代碼：

http://javarevisited.blogspot.sg/2015/10/how-to-implement-binary-search-tree-in-java-example.html#axzz4wnEtnNB3

如果你覺得自己對二叉樹編程的理解還不夠，無法獨自解決這些問題，我列出了我使用過的書籍：

http://javarevisited.blogspot.sg/2015/07/5-data-structure-and-algorithm-books-best-must-read.html

http://javarevisited.blogspot.sg/2018/01/top-5-free-data-structure-and-algorithm-courses-java--c-programmers.html

       

其它算法編程問題

除了數據結構問題，大多數編程面試也會問有關算法、設計、位操作和一般的邏輯問題，在這部分中我會介紹這些問題。

在實際問題中應用這些概念是十分重要的，因為在面試中它們往往都比較難對付。多加練習不僅可以讓你對這些概念更熟悉，也會讓你在面試過程中更有信心。

▌1.如何實現冒泡排序算法？

解決方法與代碼：

http://javarevisited.blogspot.sg/2014/08/bubble-sort-algorithm-in-java-with.html#axzz5ArdIFI7y

▌2.如何用迭代實現快速排序算法？

解決方法與代碼：

http://javarevisited.blogspot.sg/2016/09/iterative-quicksort-example-in-java-without-recursion.html#axzz5ArdIFI7y

▌3.如何實現插入排序算法？

解決方法與代碼：

http://www.java67.com/2014/09/insertion-sort-in-java-with-example.html

▌4.如何實現歸併排序算法？

解決方法與代碼：

http://www.java67.com/2018/03/mergesort-in-java-algorithm-example-and.html

▌5.如何實現桶排序算法？

解決方法與代碼：

https://javarevisited.blogspot.com/2017/01/bucket-sort-in-java-with-example.html

▌6.如何實現計數排序算法？

解決方法與代碼：

http://www.java67.com/2017/06/counting-sort-in-java-example.html

▌7.如何實現基數排序算法？

解決方法與代碼：

http://www.java67.com/2018/03/how-to-implement-radix-sort-in-java.html

▌8.在不使用第三個變量的情況下，如何交換兩個數字的值？

解決方法與代碼：

http://www.java67.com/2015/08/how-to-swap-two-integers-without-using.html

▌9.如何判斷兩個矩形是否有重疊？

解決方法與代碼：

http://javarevisited.blogspot.sg/2016/10/how-to-check-if-two-rectangle-overlap-in-java-algorithm.html

▌10.如何設計一個自動販售機？

解決方法與代碼：

https://javarevisited.blogspot.com/2016/06/design-vending-machine-in-java.html

推薦閱讀：

《Cracking The Code Interview》書中介紹了189個編程問題及解決方法

50個電面編程問題：

http://javarevisited.blogspot.sg/2015/02/50-programmer-phone-interview-questions-answers.html

有關書籍：

https://javarevisited.blogspot.com/2016/06/top-5-books-for-programming-coding-interviews-best.html

       

練習解決的實際問題越多，準備就越充分。希望這份面試資源對大家有幫忙，面試順利，都能獲得好結果！

原文連結：

https://hackernoon.com/50-data-structure-and-algorithms-interview-questions-for-programmers-b4b1ac61f5b0

添加小編微信：tangguoyemeng，備註「進群」即可，加入【雲計算學習交流群】，和志同道合的朋友們共同打卡學習！

成為群成員，或拉人進群，

還有機會參與紅包抽獎，獲得免費贈書哦~~

CSDN作為國內專業的雲計算服務平臺，目前提供雲計算、大數據、虛擬化、數據中心、OpenStack、CloudStack、機器學習、智能算法等相關雲計算觀點、技術、平臺、實踐、雲產業諮詢等服務。CSDN 公眾號也一直堅持「與千萬技術人共成長」的理念，深度解讀行業內熱門技術與場景應用，致力於讓所有開發者保持敏銳的技術嗅覺、對行業趨勢與技術獲得更廣闊的認知。

 稿費：根據原創性、實用性和時效性等方面進行審核，通過的文章會發布在本微信平臺。一經採用，我們將支付作者酬勞。酬勞可能不多，這代表的是一個心意，更多是因為愛好，是有識之士抒發胸懷的一種方式；

字數要求：稿件字數以2K-8K為宜，少於2K或多於8K都會一定程度降低閱讀愉悅感；

投稿郵箱：[e-mail]。或者添加微信表明來意，微信號：tangguoyemeng。請備註投稿+姓名+公司職位。

如果咱們的合作穩定又愉快，還可以籤訂合同長期合作哦！

2018 AI開發者大會（AI NEXTCon）由中國IT社區CSDN與矽谷AI社區AICamp聯合出品的AI技術與產業年度盛會。多年經驗淬鍊，如今蓄勢待發：將有近百位中美頂尖AI專家、知名企業代表以及千餘名AI開發者齊聚北京，進行技術解讀和產業論證。我們只講技術，拒絕空談，誠摯邀請AI業內人士一起共鑄人工智慧新篇章！

2018 AI開發者大會首輪重磅嘉賓及深度議題現已火熱出爐，掃碼搶「鮮」看。國慶特惠，購票立享 5 折優惠！