Java算法常見面試題及答案

隨著疫情的好轉，各大企業公司紛紛開始復工，招聘也將迎來一個高峰。Java程序員想要在這次疫情后，拿到滿意的offer，就必須做好充足的準備。眾所周知，算法可以說是大廠面試Java程序員的必問面試題。相信算法的重要性大家都了解，好的算法可以讓性能得到萬倍提升，做到毫秒級處理千萬數據的程度。因此，為了提升大家在面試中的底氣，本文整理了一些Java程序員算法面試題并比附上了答案，一起來看看吧！

1、算法的時間復雜度時候是什么？

答案：算法的時間復雜度表示程序運行完成所需的總時間，它通常用大O表示法來表示。

2、合并k個有序（假設升序）數組的具體步驟是什么？

答案：將k個數組的第一個元素取出來，維護一個小頂堆；彈出堆頂元素存入結果數組中，并把該元素所在數組的下一個元素取出來壓入隊中；調整堆的結構，使其滿足小頂堆的定義；重復前兩步直到合并完成。

3、解釋二分法檢索如何工作？

答案：在二分法檢索中，我們先確定數組的中間位置，然后將要查找的值與數組中間位置的值進行比較，若小于數組中間值，則要查找的值應位于該中間值之前，依此類推，不斷縮小查找范圍，直至得到最終結果。

代碼拓展，二分法查找

def BinarySearch(t,x):

    t.sort() #對列表進行排序，列表是有序的，是二分法的前提

    low = 0;

    high = len(t)-1;

    while low < high:

        mid = (low+high)/2;

        if t[mid]<x:

            low=mid+1;

        elif t[mid]>x:

            high = mid-1;

        else :

            return mid

    return Non

4、查找數組中出現次數超過一半的數字

答案：等價于求數組中第n/2大的數，和4中思想一樣，平均時間復雜度O(n)

5、一個數組怎么輸出前K大的值、時間復雜度？

答案：借助快排partition的思想，平均時間復雜度是O(n)

6、用A表示1第一列，B表示2第二列，。。。，Z表示26，AA表示27，AB表示28。。。以此類推。請寫出一個函數，輸入用字母表示的列號編碼，輸出它是第幾列。

答案：這道題的解題思路關鍵在于26進制轉10進制。

7、輸入一個正數n，輸出所有和為n 連續正數序列。

答案：輸入15，由于1+2+3+4+5=4+5+6=7+8=15，所以輸出3 個連續序列1-5、4-6 和7-8。

8、輸出一個整數二進制表示中1的個數。

答案：這道題的解法多樣，可以右移原數判斷，如果輸入是負數可能陷入死循環；也可以左移1；還可以把一個整數-1后與原數做與運算會消去原數最左邊的1。

9、在一個二維數組中（每個一維數組的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。

答案：這道算法面試題對大多數Java程序員來講并不難，大致的解題思路如下，我們注意到這個二維數組的行和列都是升序的，也就是說最上面的一行和最右邊的一列在整體上也是升序的，在一個排序數組上查找某個我們會很自然的想起二分法。這樣我們每次都把要查找的數和當前剩下的二維數組的右上角數字比較，這樣每次我們都可以排除掉一行或一列。算法的時間復雜度是O(n+m)，也就是行數加列數。

10、兩個排序數組A1和A2，現在想把A2插入A1中并仍保持有序。

答案：數組是個順序表，我們往數組中插入某個數的話必須要移動當前位置后面所有的數。常規的思路是每次插入一個數并移動后面的數，這樣多次插入后會導致數組中有的數被移動了多次，極大浪費了效率。我們希望每個數移動一次就到達它最終的位置，所以我們往往會反向移動數組，這樣做的好處是移動當前數時后面的數已經到達了最終位置，我們移動當前數不會影響到后面的數，這樣就確保了每個數只被移動一次。

11、斐波那契數列：f(0) = 0, f(1) = 1, f(n) = f(n - 1) + f(n - 2)

答案：這道算法面試題的解答方法是多樣的，可以用遞歸，不過效率低；還可以用循環，正著推；用矩陣運算也是可以的。

12、給定一個整數序列，你可以刪去其中的連續一段（可以不刪），求刪去后數組的最大連續子段和。

答案：最大連續子序列的變種題，從前往后遍歷一遍求最大連續子序列和，然后從后往前遍歷一遍求最大連續子序列和。另外，對于刪去中間一段不好直接操作的話，可以先從前往后遍歷，在從后往前遍歷。

13、小明要在t分鐘之內做l張餅，有n個鍋，但只能選其中k個鍋，每個鍋每分鐘能做vi個餅，最多能做mi個餅，問能不能做完l張餅，如果能，輸出最少需要多少分鐘；如果不能，輸出最多能做幾張餅。

答案：查詢時先想一下二分。首先判斷能不能做完：每個鍋在t分鐘內能做的餅數為min(mi,vi*t), 降序排列，前k個鍋能做出來的餅>l就能；如果不能做完：直接輸出前k個鍋能做餅的和；如果能：二分最短時間，然后判斷在mid分鐘內能不能做完餅，判斷方法同t分鐘的情況。

14、推排序是什么？

答案：堆排序可以看成是選擇排序的改進，它可以定義為基于比較的排序算法。它將其輸入劃分為未排序和排序的區域，通過不斷消除最小元素并將其移動到排序區域來收縮未排序區域。

15、快速排序算法是什么？

答案：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列；空間復雜度為O(log2n)；時間復雜度比較復雜，最好的情況是O(n)，最差的情況是O(n2)，所以平時說的O(nlogn)，為其平均時間復雜度。

16、什么是&ldquo;哈希算法&rdquo;，它們用于什么？

答案：&ldquo;哈希算法&rdquo;是一個哈希函數，它使用任意長度的字符串，并將其減少為唯一的固定長度字符串。它用于密碼有效性、消息和數據完整性以及許多其他加密系統；

17、如果字符串一的所有字符按其在字符串中的順序出現在另外一個字符串二中，則字符串一稱之為字符串二的子串。注意，并不要求子串（字符串一）的字符必須連續出現在字符串二中。請編寫一個函數，輸入兩個字符串，求它們的最長公共子串，并打印出最長公共子串。

答案：求最長公共子串是一道非常經典的動態規劃題。輸入兩個字符串BDCABA 和ABCBDAB，字符串BCBA 和BDAB 都是是它們的最長公共子串，則輸出它們的長度4，并打印任意一個子串。

18、如何查找鏈表是否有循環？

答案：要知道鏈表是否有循環，我們將采用兩個指針的方法；如果保留兩個指針，并且在處理兩個節點之后增加一個指針，并且在處理每個節點之后，遇到指針指向同一個節點的情況，這只有在鏈表有循環時才會發生。

以上就是關于Java程序員算法面試題的全部整理，這些對應的答案大家可以在做完之后再看。如果有弄不明白的算法面試題，就需要大家好好對算法的相關知識點進行查漏補缺。最后，希望大家都能夠順利通過面試。