數(shù)組問題
數(shù)組是最常用的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，它將元素保存在連續(xù)的內(nèi)存中。它也是面試最喜歡的問題之一，在代碼面試中你會經(jīng)常聽到很多關(guān)于數(shù)組的問題，例如，數(shù)組的反轉(zhuǎn)、數(shù)組的排序或者查找數(shù)組中的一個元素。
數(shù)組結(jié)構(gòu)的一個關(guān)鍵優(yōu)點是在知道索引的情況能夠以 O(1) 的復(fù)雜度找到一個元素。但是增加或者刪除一個元素是很慢的，因為一旦創(chuàng)建了一個數(shù)組，你就不能改變它的大小了。
為了創(chuàng)建一個更長或者更短的數(shù)組，你需要創(chuàng)建一個新的數(shù)組，然后將所有元素從舊數(shù)組中復(fù)制到新數(shù)組中。
解決數(shù)組問題的關(guān)鍵是，你要對數(shù)組這種數(shù)據(jù)結(jié)構(gòu)有一個深刻的認識，同時還要了解基本的程序流程如循環(huán)、遞歸以及基本的操作符。
下面是一些經(jīng)常問到和數(shù)組相關(guān)的面試題，你可以拿來練習(xí)：
1、在一個給定的從1到100的整型數(shù)組中，如何快速找到缺失的數(shù)字？
2、如何找到一個給定的整型數(shù)組中的重復(fù)數(shù)字？
3、在一個未排序的整型數(shù)組中，如何找到最大和最小的數(shù)字？
4、在一個整型數(shù)組中，如何找到一個所有成對的數(shù)字，滿足它們的和等于一個給定的數(shù)字？
5、如果一個數(shù)組包含多個重復(fù)元素，如何找到這些重復(fù)的數(shù)字？
6、用 Java 實現(xiàn)從一個給定數(shù)組中刪除重復(fù)元素？
7、如何利用快速排序?qū)σ粋€整型數(shù)組進行排序？
8、如何從一個數(shù)組中刪除重復(fù)元素？
9、用 Java 實現(xiàn)數(shù)組反轉(zhuǎn)？
10、如何不借助庫實現(xiàn)從數(shù)組中刪除重復(fù)元素？
鏈表問題
鏈表是另外一個常見的數(shù)據(jù)結(jié)構(gòu)，對數(shù)組結(jié)構(gòu)是一個補充。和數(shù)組類似，它也是一個線性的數(shù)據(jù)結(jié)構(gòu)，以線性方式存儲元素。
不過和數(shù)組不同的是，鏈表的元素不是存儲在連續(xù)位置中，而是分散在各個內(nèi)存中的各個位置，通過節(jié)點鏈接起來。一個鏈表就是一個包含了下個節(jié)點內(nèi)存地址的節(jié)點列表。
基于這種結(jié)構(gòu)，可以很容易實現(xiàn)鏈表中元素的添加和刪除，因為只需要改變節(jié)點的指向而無需創(chuàng)建一個新的數(shù)組。不過鏈表中的查找是相對困難的，在一個單向鏈表中需要花費 O(n) 的時間代價來查找一個元素。
鏈表有幾種不同的形式。首先是單向鏈表，在這個結(jié)構(gòu)你只能向一個方向遍歷（向前或者反轉(zhuǎn)）；其次是雙向鏈表，你可以雙向遍歷（向前或者向后）；最后是環(huán)形鏈表，組成一個環(huán)的形式。
要解決鏈表問題，你就必須了解遞歸的相關(guān)知識，因為鏈表是一種遞歸的數(shù)據(jù)結(jié)構(gòu)。如果你從鏈表中去掉一個節(jié)點, 剩下的數(shù)據(jù)結(jié)構(gòu)仍然是鏈表，因此, 許多鏈表問題有比遍歷更簡單的遞歸解決方案.
下面是一些最常見和流行的鏈表面試問題
1、在一次遍歷中，怎樣發(fā)現(xiàn)單個鏈表的中間元素?
2、怎樣驗證給定的鏈表是環(huán)形的? 怎樣發(fā)現(xiàn)這個環(huán)的起始節(jié)點?
3、怎樣翻轉(zhuǎn)鏈表?
4、不使用遞歸，怎樣反轉(zhuǎn)單個鏈表?
5、在未排序鏈表中，怎樣移除重復(fù)的節(jié)點?
6、怎樣找出單個鏈表的長度?
7、從單個鏈表的結(jié)尾處，怎樣找出鏈表的第三個節(jié)點?
8、怎樣使用棧計算兩個鏈表的和?
字符串相關(guān)問題
與數(shù)組和鏈表數(shù)據(jù)結(jié)構(gòu)一起，字符串是編程工作面試中的另一個熱門話題。我從未參加過沒有問過基于字符串相關(guān)問題的編碼面試。
字符串的一個優(yōu)勢在于，如果你了解數(shù)組，你可以很容易地解決基于字符串的問題，因為字符串僅僅是一個字符數(shù)組。
因此，在解決基于數(shù)組的編程問題中所學(xué)到的所有技術(shù)也可用于解決字符串編程問題。
以下是編程求職面試中常見的字符串編程問題：
1、如何輸出字符串中的重復(fù)字符？
2、如何判斷兩個字符串是否互為回文？
3、如何從字符串中輸出第一個不重復(fù)字符？
4、如何使用遞歸實現(xiàn)字符串反轉(zhuǎn)?
5、如何檢查字符僅包含數(shù)字字符？
6、如何在字符串中找到重復(fù)字符？
7、如何對給定字符串中的元音及輔音進行計數(shù)？
8、如何計算給定字符傳中特定字符出現(xiàn)的次數(shù)？
9、如何找到一個字符串的全排列？
10、在不使用任何庫方法的情況下如何反轉(zhuǎn)給定語句中的單詞？
11、如何判斷兩個字符串是否互為旋轉(zhuǎn)？
12、如何判斷給定字符串是否是回文？
二叉樹問題
到目前為止，我們只研究了線性數(shù)據(jù)結(jié)構(gòu)，但現(xiàn)實世界中的所有信息無法全部使用線性方式表示，而這正是樹數(shù)據(jù)結(jié)構(gòu)所擅長的地方。
樹是一種支持以分層方式存儲數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。根據(jù)你存儲數(shù)據(jù)的方式，有不同類型的樹，例如二叉樹，其中每個節(jié)點最多有兩個子節(jié)點。
與它的近親二叉搜索樹一起，它們也是最流行的樹數(shù)據(jù)結(jié)構(gòu)之一。因此，你會發(fā)現(xiàn)很多基于它們的問題，例如如何遍歷它們、計算節(jié)點數(shù)、查找深度，以及檢查它們是否平衡。
解決二叉樹問題的一個關(guān)鍵點是對其理論的深刻理解，例如：什么是二叉樹的大小或深度，什么是葉節(jié)點，什么是節(jié)點，以及對流行的遍歷算法的理解，例如前序、后序和中序遍歷。
下面是一些經(jīng)常問到的基于二叉樹的面試題，你可以拿來練習(xí)：
1、二叉搜索樹是如何實現(xiàn)的？
2、如何在給定二叉樹上實現(xiàn)前序遍歷？
3、不使用遞歸如何按照前序遍歷給定二叉樹？
4、如何在給定二叉樹上實現(xiàn)中序遍歷？
5、不使用遞歸情況下如何使用中序遍歷輸出給定二叉樹所有節(jié)點？
6、如何實現(xiàn)后序遍歷算法？
7、如何不使用遞歸實現(xiàn)二叉樹的后續(xù)遍歷？
8、如何輸出二叉搜索樹的所有葉節(jié)點？
9、如何在給定二叉樹中計算葉節(jié)點數(shù)目？
10、如何在給定數(shù)組中執(zhí)行二分搜索？
編程面試問題之雜項
除了基于數(shù)據(jù)結(jié)構(gòu)的問題之外，大多數(shù)編程工作面試還會詢問算法、設(shè)計、位操作和基于邏輯的常規(guī)問題，我將在本節(jié)中對其進行介紹。
練習(xí)這些概念很重要，因為有時在實際面試中解決這些概念很棘手。提前練習(xí)它們不僅能讓你熟悉它們，而且還讓你更自信地向面試官解釋其解決方案。
1、冒泡排序是如何實現(xiàn)的?
2、迭代式快排算法是如何實現(xiàn)的？
3、你如何實現(xiàn)插入排序算法？
4、合并排序算法是如何實現(xiàn)的？
5、桶排序算法是如何實現(xiàn)的？
6、計數(shù)排序算法是如何實現(xiàn)的？
7、基數(shù)排序算法是如何實現(xiàn)的？
8、在不使用第三個變量的前提下如何交換兩個數(shù)？
9、如何檢查兩個矩形是否重疊？
10、如何設(shè)計一個自動售貨機？
以上這些是數(shù)據(jù)結(jié)構(gòu)和算法之外的一些最常見的面試問題，可以幫助你在面試中做得很好。
如果有小伙伴愿意共享自己的解題方法或者思路可以聯(lián)系我哦~屆時可以整理出有答案的更有意義的一篇~
