Java算法常見面試題及答案-創(chuàng)新互聯(lián)
隨著疫情的好轉(zhuǎn)，各大企業(yè)公司紛紛開始復(fù)工，招聘也將迎來(lái)一個(gè)高峰。Java程序員想要在這次疫情后，拿到滿意的offer，就必須做好充足的準(zhǔn)備。眾所周知，算法可以說(shuō)是大廠面試Java程序員的必問(wèn)面試題。相信算法的重要性大家都了解，好的算法可以讓性能得到萬(wàn)倍提升，做到毫秒級(jí)處理千萬(wàn)數(shù)據(jù)的程度。因此，為了提升大家在面試中的底氣，本文整理了一些Java程序員算法面試題并比附上了答案，一起來(lái)看看吧！
創(chuàng)新互聯(lián)于2013年創(chuàng)立，先為普安等服務(wù)建站，普安等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為普安企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問(wèn)題。
1、算法的時(shí)間復(fù)雜度時(shí)候是什么？
答案：算法的時(shí)間復(fù)雜度表示程序運(yùn)行完成所需的總時(shí)間，它通常用大O表示法來(lái)表示。
2、合并k個(gè)有序（假設(shè)升序）數(shù)組的具體步驟是什么？
答案：將k個(gè)數(shù)組的第一個(gè)元素取出來(lái)，維護(hù)一個(gè)小頂堆；彈出堆頂元素存入結(jié)果數(shù)組中，并把該元素所在數(shù)組的下一個(gè)元素取出來(lái)壓入隊(duì)中；調(diào)整堆的結(jié)構(gòu)，使其滿足小頂堆的定義；重復(fù)前兩步直到合并完成。
3、解釋二分法檢索如何工作？
答案：在二分法檢索中，我們先確定數(shù)組的中間位置，然后將要查找的值與數(shù)組中間位置的值進(jìn)行比較，若小于數(shù)組中間值，則要查找的值應(yīng)位于該中間值之前，依此類推，不斷縮小查找范圍，直至得到最終結(jié)果。
代碼拓展，二分法查找
def BinarySearch(t,x):
t.sort() #對(duì)列表進(jìn)行排序，列表是有序的，是二分法的前提
low = 0;
high = len(t)-1;
while low < high:
mid = (low+high)/2;
if t[mid] low=mid+1; elif t[mid]>x: high = mid-1; else : return mid return Non 4、查找數(shù)組中出現(xiàn)次數(shù)超過(guò)一半的數(shù)字 答案：等價(jià)于求數(shù)組中第n/2大的數(shù)，和4中思想一樣，平均時(shí)間復(fù)雜度O(n) 5、一個(gè)數(shù)組怎么輸出前K大的值、時(shí)間復(fù)雜度？ 答案：借助快排partition的思想，平均時(shí)間復(fù)雜度是O(n) 6、用A表示1第一列，B表示2第二列，。。。，Z表示26，AA表示27，AB表示28。。。以此類推。請(qǐng)寫出一個(gè)函數(shù)，輸入用字母表示的列號(hào)編碼，輸出它是第幾列。 答案：這道題的解題思路關(guān)鍵在于26進(jìn)制轉(zhuǎn)10進(jìn)制。 7、輸入一個(gè)正數(shù)n，輸出所有和為n 連續(xù)正數(shù)序列。 答案：輸入15，由于1+2+3+4+5=4+5+6=7+8=15，所以輸出3 個(gè)連續(xù)序列1-5、4-6 和7-8。 8、輸出一個(gè)整數(shù)二進(jìn)制表示中1的個(gè)數(shù)。 答案：這道題的解法多樣，可以右移原數(shù)判斷，如果輸入是負(fù)數(shù)可能陷入死循環(huán)；也可以左移1；還可以把一個(gè)整數(shù)-1后與原數(shù)做與運(yùn)算會(huì)消去原數(shù)最左邊的1。 9、在一個(gè)二維數(shù)組中（每個(gè)一維數(shù)組的長(zhǎng)度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。 答案：這道算法面試題對(duì)大多數(shù)Java程序員來(lái)講并不難，大致的解題思路如下，我們注意到這個(gè)二維數(shù)組的行和列都是升序的，也就是說(shuō)最上面的一行和最右邊的一列在整體上也是升序的，在一個(gè)排序數(shù)組上查找某個(gè)我們會(huì)很自然的想起二分法。這樣我們每次都把要查找的數(shù)和當(dāng)前剩下的二維數(shù)組的右上角數(shù)字比較，這樣每次我們都可以排除掉一行或一列。算法的時(shí)間復(fù)雜度是O(n+m)，也就是行數(shù)加列數(shù)。 10、兩個(gè)排序數(shù)組A1和A2，現(xiàn)在想把A2插入A1中并仍保持有序。 答案：數(shù)組是個(gè)順序表，我們往數(shù)組中插入某個(gè)數(shù)的話必須要移動(dòng)當(dāng)前位置后面所有的數(shù)。常規(guī)的思路是每次插入一個(gè)數(shù)并移動(dòng)后面的數(shù)，這樣多次插入后會(huì)導(dǎo)致數(shù)組中有的數(shù)被移動(dòng)了多次，極大浪費(fèi)了效率。我們希望每個(gè)數(shù)移動(dòng)一次就到達(dá)它最終的位置，所以我們往往會(huì)反向移動(dòng)數(shù)組，這樣做的好處是移動(dòng)當(dāng)前數(shù)時(shí)后面的數(shù)已經(jīng)到達(dá)了最終位置，我們移動(dòng)當(dāng)前數(shù)不會(huì)影響到后面的數(shù)，這樣就確保了每個(gè)數(shù)只被移動(dòng)一次。 11、斐波那契數(shù)列：f(0) = 0, f(1) = 1, f(n) = f(n - 1) + f(n - 2) 答案：這道算法面試題的解答方法是多樣的，可以用遞歸，不過(guò)效率低；還可以用循環(huán)，正著推；用矩陣運(yùn)算也是可以的。 12、給定一個(gè)整數(shù)序列，你可以刪去其中的連續(xù)一段（可以不刪），求刪去后數(shù)組的大連續(xù)子段和。 答案：大連續(xù)子序列的變種題，從前往后遍歷一遍求大連續(xù)子序列和，然后從后往前遍歷一遍求大連續(xù)子序列和。另外，對(duì)于刪去中間一段不好直接操作的話，可以先從前往后遍歷，在從后往前遍歷。 13、小明要在t分鐘之內(nèi)做l張餅，有n個(gè)鍋，但只能選其中k個(gè)鍋，每個(gè)鍋每分鐘能做vi個(gè)餅，最多能做mi個(gè)餅，問(wèn)能不能做完l張餅，如果能，輸出最少需要多少分鐘；如果不能，輸出最多能做幾張餅。 答案：查詢時(shí)先想一下二分。首先判斷能不能做完：每個(gè)鍋在t分鐘內(nèi)能做的餅數(shù)為min(mi,vi*t), 降序排列，前k個(gè)鍋能做出來(lái)的餅>l就能；如果不能做完：直接輸出前k個(gè)鍋能做餅的和；如果能：二分最短時(shí)間，然后判斷在mid分鐘內(nèi)能不能做完餅，判斷方法同t分鐘的情況。 14、推排序是什么？ 答案：堆排序可以看成是選擇排序的改進(jìn)，它可以定義為基于比較的排序算法。它將其輸入劃分為未排序和排序的區(qū)域，通過(guò)不斷消除最小元素并將其移動(dòng)到排序區(qū)域來(lái)收縮未排序區(qū)域。 15、快速排序算法是什么？ 答案：通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列；空間復(fù)雜度為O(log2n)；時(shí)間復(fù)雜度比較復(fù)雜，最好的情況是O(n)，最差的情況是O(n2)，所以平時(shí)說(shuō)的O(nlogn)，為其平均時(shí)間復(fù)雜度。 16、什么是“哈希算法”，它們用于什么？ 答案：“哈希算法”是一個(gè)哈希函數(shù)，它使用任意長(zhǎng)度的字符串，并將其減少為唯一的固定長(zhǎng)度字符串。它用于密碼有效性、消息和數(shù)據(jù)完整性以及許多其他加密系統(tǒng)； 17、如果字符串一的所有字符按其在字符串中的順序出現(xiàn)在另外一個(gè)字符串二中，則字符串一稱之為字符串二的子串。注意，并不要求子串（字符串一）的字符必須連續(xù)出現(xiàn)在字符串二中。請(qǐng)編寫一個(gè)函數(shù)，輸入兩個(gè)字符串，求它們的最長(zhǎng)公共子串，并打印出最長(zhǎng)公共子串。 答案：求最長(zhǎng)公共子串是一道非常經(jīng)典的動(dòng)態(tài)規(guī)劃題。輸入兩個(gè)字符串BDCABA 和ABCBDAB，字符串BCBA 和BDAB 都是是它們的最長(zhǎng)公共子串，則輸出它們的長(zhǎng)度4，并打印任意一個(gè)子串。 18、如何查找鏈表是否有循環(huán)？ 答案：要知道鏈表是否有循環(huán)，我們將采用兩個(gè)指針的方法；如果保留兩個(gè)指針，并且在處理兩個(gè)節(jié)點(diǎn)之后增加一個(gè)指針，并且在處理每個(gè)節(jié)點(diǎn)之后，遇到指針指向同一個(gè)節(jié)點(diǎn)的情況，這只有在鏈表有循環(huán)時(shí)才會(huì)發(fā)生。 以上就是關(guān)于Java程序員算法面試題的全部整理，這些對(duì)應(yīng)的答案大家可以在做完之后再看。如果有弄不明白的算法面試題，就需要大家好好對(duì)算法的相關(guān)知識(shí)點(diǎn)進(jìn)行查漏補(bǔ)缺。最后，希望大家都能夠順利通過(guò)面試。
標(biāo)題名稱：Java算法常見面試題及答案-創(chuàng)新互聯(lián)
分享路徑：http://m.jiaotiyi.com/article/cdicei.html