《Java程序員面試算法寶典》是一本講解Java程序員面試算法的書籍,在寫法上,除了講解如何解答算法問題外,還引入了實(shí)例輔以說明,讓讀者能夠更好地理解本書內(nèi)容。
《Java程序員面試算法寶典》將Java程序員面試、筆試過程中各類算法類真題一網(wǎng)打盡。在題目的廣度上,本書收集了近三年來幾乎所有IT企業(yè)面試、筆試算法高頻題目,所選擇題目均為企業(yè)招聘使用題目。在題目的深度上,本書由淺入深,庖丁解牛式地分析每一個(gè)題目,并提煉歸納。同時(shí),引入實(shí)例與源代碼、時(shí)間復(fù)雜度與空間復(fù)雜度的分析,而這些內(nèi)容是其他同類書籍所沒有的。本書根據(jù)真題所屬知識點(diǎn)進(jìn)行分門別類,力圖做到結(jié)構(gòu)合理、條理清晰,對于讀者進(jìn)行學(xué)習(xí)與檢索意義重大。
本書是一本計(jì)算機(jī)相關(guān)專業(yè)畢業(yè)生面試、筆試的求職用書,也可以作為本科生、研究生學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的輔導(dǎo)書,同時(shí)也適合期望在計(jì)算機(jī)軟、硬件行業(yè)大顯身手的計(jì)算機(jī)愛好者閱讀。
程序員,一類聽起來神秘看上去卻普普通通的人群,寫著那些密密麻麻的常人看不懂的代碼,領(lǐng)著一份讓很多人都羨慕的薪水。也許每個(gè)人心中對程序員的理解都不盡相同,也許每個(gè)程序員的生活狀態(tài)各有千秋,但毋庸置疑,在程序員是否是一個(gè)高大上的職業(yè)上,他們還是驚人的一致:是。
在信息技術(shù)高度發(fā)達(dá)的今天,很難想象,離開了程序員,這個(gè)社會會是什么樣子。從手機(jī)、計(jì)算機(jī)、電視機(jī)、洗衣機(jī)等日常生活用品到宇宙飛船、空間站、飛機(jī)、坦克、大炮,都離不開計(jì)算機(jī)程序。計(jì)算機(jī)程序已然滲透到生活中的方方面面。雖然計(jì)算機(jī)程序是一個(gè)軟實(shí)體,看不見摸不著,人們也感知不到它的存在,但是你們是否知道,沒有了操作系統(tǒng)與應(yīng)用程序,手機(jī)就是一個(gè)廢物;沒有了計(jì)算機(jī)程序,大炮、飛機(jī)、航空母艦就是一個(gè)鐵疙瘩;沒有了計(jì)算機(jī)程序,洗衣機(jī)、空調(diào)就是一個(gè)擺設(shè)。
計(jì)算機(jī)程序有多么重要,也許上面說的還不清楚,在此舉兩個(gè)簡單例子就可以說明。當(dāng)前,智能手機(jī)高度發(fā)展,但是手機(jī)的Android操作系統(tǒng)是由軟件巨頭谷歌(Google)研發(fā)的,所有使用Android系統(tǒng)的手機(jī)廠商都受制于Google。諾基亞(Nokia)手機(jī)曾經(jīng)是世界上銷量非常好的手機(jī),由于沒能跟上Android的步伐,最終走向了覆滅,被另一家軟件巨頭微軟(Microsoft)公司收購了。蘋果(Apple)智能設(shè)備之所以很受歡迎,除了其良好的外形設(shè)計(jì)以外,另一個(gè)重要原因就是其蘋果操作系統(tǒng)(iOS)的獨(dú)一無二。這些都是軟件打敗硬件的例子。
計(jì)算機(jī)技術(shù)博大精深,而且日新月異,Hadoop、GPU計(jì)算、移動互聯(lián)網(wǎng)、模式匹配、圖像識別、神經(jīng)網(wǎng)絡(luò)、蟻群算法、大數(shù)據(jù)、機(jī)器學(xué)習(xí)、人工智能、深度學(xué)習(xí)等新技術(shù)讓人眼花繚亂,稍有不慎,就會被時(shí)代所拋棄。于是,很多IT從業(yè)者就開始困惑了,不知道從何學(xué)起,到底什么才是計(jì)算機(jī)技術(shù)的基石。其實(shí),究其本質(zhì)還是最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)與算法知識:Hash、動態(tài)規(guī)劃、分治、排序、查找等,所以無論是世界級的大型IT企業(yè)還是小公司,在面試求職者時(shí),往往都會考察這些最基礎(chǔ)的知識,無論研究方向是什么,這些基礎(chǔ)知識都是必須熟練掌握的。
本書在寫作風(fēng)格上推陳出新,對于算法的講解,不僅文字描述,更以示例佐證,讓讀者能夠更好地讀懂本書內(nèi)容。為了能夠?qū)懗鼍窌,我們對每一個(gè)技術(shù)問題,都反復(fù)推敲,與算法精英一起反復(fù)論證可行性;對文字,我們咬文嚼字、字斟句酌,所有這些付出,只為讓讀者能夠?qū)屑夹g(shù)點(diǎn)放心,文字描述舒心。
市面上同類型書籍很多,但是,我們相信,我們能夠?qū)懗龈m合讀者的高質(zhì)量精品書籍。為了能夠在有限的篇幅里面盡可能地全是“干貨”,作者在選擇題目上下了很大的工夫。首先,我們通過搜集近三年來幾乎所有IT企業(yè)的面試、筆試算法真題,包括已經(jīng)出版的其他著作、技術(shù)博客、在線編碼平臺、刷題網(wǎng)站等,保證所選樣本足夠全面。其次,在選擇題目時(shí),盡可能不選擇那種一眼就能知道結(jié)果的簡單題,也沒有選擇那種怪題、偏題、難題。我們的原則是選擇那些難度適中或者看上去簡單但實(shí)際容易中陷阱的題目。我們力求遴選出來的算法真題能夠最大限度地幫助讀者。在真題的解析上,采用層層遞進(jìn)的寫法,先易后難,將問題抽絲剝繭,使得讀者能夠跟隨作者的思路,一步步找到問題的最優(yōu)解。
寫作的過程是一個(gè)自我提高、自我認(rèn)識的過程,很多知識,只有深入理解與剖析后,才能領(lǐng)悟其中的精髓,掌握其中的技巧,程序員求職算法也不例外。本書不僅具備了其他書籍分析透徹、代碼清晰合理等優(yōu)點(diǎn),還具備以下幾個(gè)方面獨(dú)有的優(yōu)勢。
第一,本書分多種語言版本實(shí)現(xiàn):C/C++、Java、C#等,不管讀者側(cè)重于哪一種語言,都能夠從書中找到適合自己的內(nèi)容。后續(xù)可能還有PHP等其他語言描述的圖書出現(xiàn)。本書中如果沒有特別強(qiáng)調(diào),則代碼實(shí)現(xiàn)均默認(rèn)使用Java語言。
第二,每個(gè)題目除了有循序漸進(jìn)的分析以外,還對方法進(jìn)行了詳細(xì)闡述,針對不同方法的時(shí)間復(fù)雜度與空間復(fù)雜度都進(jìn)行了詳細(xì)的分析。除此之外,為了更具說服力,每一種方法幾乎都對應(yīng)有示例講解輔以說明。
第三,代碼較為規(guī)范,完全參照華為編程規(guī)范、Google編程規(guī)范和編碼規(guī)范。程序員要想在團(tuán)隊(duì)中大展拳腳,就離不開合作,而合作的基礎(chǔ)就是共同遵循統(tǒng)一的編碼規(guī)范。不僅如此,規(guī)范化的編碼往往有助于讀者理解代碼。
第四,除了題目講解,還有部分觸類旁通的題目供讀者練習(xí)。本書不可能將所有的程序員求職類的數(shù)據(jù)結(jié)構(gòu)與算法類題目囊括,但是會盡可能地將一些常見的求知類算法題、具有代表性的算法題重點(diǎn)講解,將其他一些題目以練習(xí)題的形式展現(xiàn)在讀者面前,以供讀者思考與學(xué)習(xí)。
數(shù)據(jù)結(jié)構(gòu)與算法知識博大精深,非一本或是幾本著作就能將其講解透徹的。盡管我們力求將所有程序員求職過程中出現(xiàn)的面試、筆試題一網(wǎng)打盡,試圖做到知識覆蓋面廣,內(nèi)容知識全,但仍然無法做到面面俱到,百分之百的讀者滿意率是本書以及后續(xù)改版奮斗與追求的目標(biāo),希望讀者能夠體諒。有興趣的讀者可以參閱《算法導(dǎo)論》《編程珠璣》等國外知名專家編寫的專著進(jìn)行知識的擴(kuò)展與延伸。
其實(shí),本書不僅可以作為程序員求職的應(yīng)試類書籍,還可以作
前言
面試、筆試經(jīng)驗(yàn)技巧篇
經(jīng)驗(yàn)技巧1 如何巧妙地回答面試官的問題2
經(jīng)驗(yàn)技巧2 如何回答技術(shù)性的問題3
經(jīng)驗(yàn)技巧3 如何回答非技術(shù)性問題4
經(jīng)驗(yàn)技巧4 如何回答快速估算類問題5
經(jīng)驗(yàn)技巧5 如何回答算法設(shè)計(jì)問題6
經(jīng)驗(yàn)技巧6 如何回答系統(tǒng)設(shè)計(jì)題8
經(jīng)驗(yàn)技巧7 如何解決求職中的時(shí)間沖突問題11
經(jīng)驗(yàn)技巧8 如果面試問題曾經(jīng)遇見過,是否要告知面試官12
經(jīng)驗(yàn)技巧9 在被企業(yè)拒絕后是否可以再申請12
經(jīng)驗(yàn)技巧10 如何應(yīng)對自己不會回答的問題13
經(jīng)驗(yàn)技巧11 如何應(yīng)對面試官的“激將法”語言13
經(jīng)驗(yàn)技巧12 如何處理與面試官持不同觀點(diǎn)這個(gè)問題14
經(jīng)驗(yàn)技巧13 什么是職場暗語14
面試、筆試真題解析篇
第1章 鏈表19
1.1 如何實(shí)現(xiàn)鏈表的逆序20
1.2 如何從無序鏈表中移除重復(fù)項(xiàng)24
1.3 如何計(jì)算兩個(gè)單鏈表所代表的數(shù)之和27
1.4 如何對鏈表進(jìn)行重新排序30
1.5 如何找出單鏈表中的倒數(shù)第k個(gè)元素33
1.6 如何檢測一個(gè)較大的單鏈表是否有環(huán)37
1.7 如何把鏈表相鄰元素翻轉(zhuǎn)39
1.8 如何把鏈表以K個(gè)結(jié)點(diǎn)為一組進(jìn)行翻轉(zhuǎn)41
1.9 如何合并兩個(gè)有序鏈表44
1.10 如何在只給定單鏈表中某個(gè)結(jié)點(diǎn)的指針的情況下刪除該結(jié)點(diǎn)47
1.11 如何判斷兩個(gè)單鏈表(無環(huán))是否交叉49
1.12 如何展開鏈接列表52
第2章 棧、隊(duì)列與哈希表56
2.1 如何實(shí)現(xiàn)棧56
2.2 如何實(shí)現(xiàn)隊(duì)列60
2.3 如何翻轉(zhuǎn)棧的所有元素65
2.4 如何根據(jù)入棧序列判斷可能的出棧序列69
2.5 如何用O(1)的時(shí)間復(fù)雜度求棧中最小元素71
2.6 如何用兩個(gè)棧模擬隊(duì)列操作73
2.7 如何設(shè)計(jì)一個(gè)排序系統(tǒng)74
2.8 如何實(shí)現(xiàn)LRU緩存方案76
2.9 如何從給定的車票中找出旅程78
2.10 如何從數(shù)組中找出滿足a+b=c+d的兩個(gè)數(shù)對79
第3章 二叉樹81
3.1 二叉樹基礎(chǔ)知識81
3.2 如何把一個(gè)有序的整數(shù)數(shù)組放到二叉樹中83
3.3 如何從頂部開始逐層打印二叉樹結(jié)點(diǎn)數(shù)據(jù)84
3.4 如何求一棵二叉樹的最大子樹和87
3.5 如何判斷兩棵二叉樹是否相等89
3.6 如何把二叉樹轉(zhuǎn)換為雙向鏈表90
3.7 如何判斷一個(gè)數(shù)組是否是二元查找樹后序遍歷的序列92
3.8 如何找出排序二叉樹上任意兩個(gè)結(jié)點(diǎn)的最近共同父結(jié)點(diǎn)93
3.9 如何復(fù)制二叉樹98
3.10 如何在二叉樹中找出與輸入整數(shù)相等的所有路徑100
3.11 如何對二叉樹進(jìn)行鏡像反轉(zhuǎn)102
3.12 如何在二叉排序樹中找出第一個(gè)大于中間值的結(jié)點(diǎn)104
3.13 如何在二叉樹中找出路徑最大的和106
3.14 如何實(shí)現(xiàn)反向DNS查找緩存108
第4章 數(shù)組112
4.1 如何找出數(shù)組中唯一的重復(fù)元素112
4.2 如何查找數(shù)組中元素的最大值和最小值118
4.3 如何找出旋轉(zhuǎn)數(shù)組的最小元素121
4.4 如何找出數(shù)組中丟失的數(shù)125
4.5 如何找出數(shù)組中出現(xiàn)奇數(shù)次的數(shù)127
4.6 如何找出數(shù)組中第k小的數(shù)130
4.7 如何求數(shù)組中兩個(gè)元素的最小距離133
4.8 如何求解最小三元組距離136
4.9 如何求數(shù)組中絕對值最小的數(shù)140
4.10 如何求數(shù)組連續(xù)最大和143
4.11 如何找出數(shù)組中出現(xiàn)一次的數(shù)147
4.12 如何對數(shù)組旋轉(zhuǎn)150
4.13 如何在不排序的情況下求數(shù)組中的中位數(shù)151
4.14 如何求集合的所有子集153
4.15 如何對數(shù)組進(jìn)行循環(huán)移位156
4.16 如何在有規(guī)律的二維數(shù)組中進(jìn)行高效的數(shù)據(jù)查找158
4.17 如何尋找最多的覆蓋點(diǎn)160
4.18 如何判斷請求能否在給定的存儲條件下完成162
4.19 如何按要求構(gòu)造新的數(shù)組164
4.20 如何獲取最好的矩陣鏈相乘方法165
4.21 如何求解迷宮問題167
4.22 如何從三個(gè)有序數(shù)組中找出它們的公共元素170
4.23 如何求兩個(gè)有序集合的交集171
4.24 如何對有大量重復(fù)的數(shù)字的數(shù)組排序175
4.25 如何對任務(wù)進(jìn)行調(diào)度179
4.26 如何對磁盤分區(qū)181
第5章 字符串183
5.1 如何求一個(gè)字符串的所有排列183
5.2 如何求兩個(gè)字符串的最長公共子串188
5.3 如何對字符串進(jìn)行反轉(zhuǎn)192
5.4 如何判斷兩個(gè)字符串是否為換位字符串194
5.5 如何判斷兩個(gè)字符串的包含關(guān)系196
5.6 如何對由大小寫字母組成的字符數(shù)組排序198
5.7 如何消除字符串的內(nèi)嵌括號199
5.8 如何判斷字符串是否是整數(shù)201
5.9 如何實(shí)現(xiàn)字符串的匹配204
5.10 如何求字符串里的最長回文子串208
5.11 如何按照給定的字母序列對字符數(shù)組排序214
5.12 如何判斷一個(gè)字符串是否包含重復(fù)字符217
5.13 如何找到由其他單詞組成的最長單詞218
5.14 如何統(tǒng)計(jì)字符串中連續(xù)的重復(fù)字符個(gè)數(shù)221
5.15 如何求最長遞增子序列的長度222
5.16 求一個(gè)串中出現(xiàn)的第一個(gè)最長重復(fù)子串223
5.17 如何求解字符串中字典序最大的子序列225
5.18 如何判斷一個(gè)字符串是否由另外一個(gè)字符串旋轉(zhuǎn)得到227
5.19 如何求字符串的編輯距離229
5.20 如何在二維數(shù)組中尋找最短路線231
5.21 如何截取包含中文的字符串234
5.22 如何求相對路徑235
5.23 如何查找到達(dá)目標(biāo)詞的最短鏈長度237
第6章 基本數(shù)字運(yùn)算240
6.1 如何判斷一個(gè)自然數(shù)是否是某個(gè)數(shù)的二次方240
6.2 如何判斷一個(gè)數(shù)是否為2的n次方242
6.3 如何不使用除法操作符實(shí)現(xiàn)兩個(gè)正整數(shù)的除法244
6.4 如何只使用++操作符實(shí)現(xiàn)加減乘除運(yùn)算248
6.