2026年Java開(kāi)發(fā)工程師算法面試題及解析一、編程實(shí)現(xiàn)題（共3題，每題20分）1.題1（20分）：字符串子序列判斷題目：給定兩個(gè)字符串`s`和`t`，判斷`t`是否為`s`的子序列。子序列是指可以通過(guò)刪除`s`中的某些字符而不改變剩余字符的相對(duì)順序得到`t`。示例：-輸入：`s="abcde"`,`t="ace"`→輸出：`true`-輸入：`s="abcde"`,`t="aec"`→輸出：`false`要求：-時(shí)間復(fù)雜度不超過(guò)O(n)，空間復(fù)雜度不超過(guò)O(1)。-請(qǐng)實(shí)現(xiàn)`booleanisSubsequence(Strings,Stringt)`方法。2.題2（20分）：滑動(dòng)窗口最大值題目：給定一個(gè)整數(shù)數(shù)組`nums`和一個(gè)整數(shù)`k`，找到長(zhǎng)度為`k`的連續(xù)子數(shù)組，輸出該子數(shù)組內(nèi)所有元素的最大值。示例：-輸入：`nums=[1,3,-1,-3,5,3,6,7]`,`k=3`→輸出：`[3,3,5,5,6,7]`要求：-使用單調(diào)隊(duì)列實(shí)現(xiàn)，時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(k)。-請(qǐng)實(shí)現(xiàn)`int[]maxSlidingWindow(int[]nums,intk)`方法。3.題3（20分）：二叉樹(shù)層序遍歷題目：給定一個(gè)二叉樹(shù)的根節(jié)點(diǎn)`root`，返回其層序遍歷的結(jié)果（從上到下，同一層從左到右）。示例：-輸入：`root=[3,9,20,null,null,15,7]`→輸出：`[[3],[9,20],[15,7]]`要求：-使用隊(duì)列實(shí)現(xiàn)，時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(n)。-請(qǐng)實(shí)現(xiàn)`List<List<Integer>>levelOrder(TreeNoderoot)`方法。二、算法設(shè)計(jì)題（共2題，每題25分）1.題4（25分）：LRU緩存機(jī)制題目：設(shè)計(jì)一個(gè)LRU（LeastRecentlyUsed）緩存機(jī)制，支持`get`和`put`操作。緩存容量為`capacity`，當(dāng)緩存容量已滿時(shí)，最近最少使用的元素將被移除以給新元素騰出空間。要求：-`get(key)`：返回key對(duì)應(yīng)的值，如果不存在返回-1。-`put(key,value)`：插入或更新key-value對(duì)。如果鍵已存在，則更新其值；如果鍵不存在，則添加該鍵值對(duì)。如果達(dá)到容量上限，則刪除最近最少使用的元素。示例：-初始化：`LRUCachecapacity=2`-`put(1,1)`→緩存為`{(1,1)}`-`put(2,2)`→緩存為`{(1,1),(2,2)}`-`get(1)`→返回`1`-`put(3,3)`→原緩存最近最少使用的是`2`，被移除，緩存為`{(1,1),(3,3)}`-`get(2)`→返回`-1`（未命中）提示：-可使用哈希表+雙向鏈表實(shí)現(xiàn)，時(shí)間復(fù)雜度O(1)。2.題5（25分）：合并K個(gè)排序鏈表題目：給定`k`個(gè)排序鏈表，合并它們?yōu)橐粋€(gè)新的排序鏈表。示例：-輸入：`head1=[1,4,5]`,`head2=[1,3,4]`,`head3=[2,6]`→輸出：`[1,1,2,3,4,4,5,6]`要求：-使用優(yōu)先隊(duì)列（最小堆）實(shí)現(xiàn)，時(shí)間復(fù)雜度O(nlogk)，空間復(fù)雜度O(k)。-請(qǐng)實(shí)現(xiàn)`ListNodemergeKLists(List<ListNode>lists)`方法。三、復(fù)雜度分析題（共2題，每題15分）1.題6（15分）：對(duì)數(shù)時(shí)間算法分析題目：給定一個(gè)有序數(shù)組`arr`，設(shè)計(jì)一個(gè)算法，在O(logn)時(shí)間復(fù)雜度內(nèi)判斷某個(gè)元素`target`是否存在于數(shù)組中。要求：-請(qǐng)描述算法步驟，并解釋為什么時(shí)間復(fù)雜度為O(logn)。-假設(shè)數(shù)組中元素不重復(fù)，`target`可能存在或不存在。2.題7（15分）：動(dòng)態(tài)規(guī)劃問(wèn)題復(fù)雜度分析題目：給定一個(gè)背包問(wèn)題：容量為`W`的背包，有`n`件物品，每件物品的重量為`weights[i]`，價(jià)值為`values[i]`。求背包能裝下的最大價(jià)值。要求：-請(qǐng)解釋動(dòng)態(tài)規(guī)劃解法的時(shí)間復(fù)雜度和空間復(fù)雜度，并說(shuō)明如何優(yōu)化空間復(fù)雜度至O(W)。答案及解析一、編程實(shí)現(xiàn)題題1（字符串子序列判斷）答案：javapublicbooleanisSubsequence(Strings,Stringt){inti=0,j=0;while(i<s.length()&&j<t.length()){if(s.charAt(i)==t.charAt(j)){i++;}j++;}returni==s.length();}解析：-使用雙指針?lè)ǎ琡i`遍歷`s`，`j`遍歷`t`。-當(dāng)`s[i]==t[j]`時(shí)，`i++`，表示當(dāng)前字符匹配；否則`j++`跳過(guò)`t`中的字符。-最終判斷`i`是否遍歷完`s`，如果是則`t`是`s`的子序列。-時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)。題2（滑動(dòng)窗口最大值）答案：javapublicint[]maxSlidingWindow(int[]nums,intk){intn=nums.length;if(n==0||k==0)returnnewint[0];int[]res=newint[n-k+1];Deque<Integer>deque=newLinkedList<>();for(inti=0;i<n;i++){//移除不在窗口內(nèi)的元素if(!deque.isEmpty()&&deque.peekFirst()<i-k+1){deque.pollFirst();}//移除比當(dāng)前元素小的元素while(!deque.isEmpty()&&nums[i]>=nums[deque.peekLast()]){deque.pollLast();}deque.offerLast(i);//窗口形成后記錄最大值if(i>=k-1){res[i-k+1]=nums[deque.peekFirst()];}}returnres;}解析：-使用單調(diào)遞減隊(duì)列，隊(duì)列中存儲(chǔ)的是元素的索引。-滑動(dòng)窗口移動(dòng)時(shí)，維護(hù)隊(duì)列頭部為當(dāng)前窗口最大值。-每次添加新元素時(shí)，移除隊(duì)列中比當(dāng)前元素小的索引，保證隊(duì)列單調(diào)遞減。-時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(k)。題3（二叉樹(shù)層序遍歷）答案：javapublicList<List<Integer>>levelOrder(TreeNoderoot){List<List<Integer>>res=newArrayList<>();if(root==null)returnres;Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);while(!queue.isEmpty()){intsize=queue.size();List<Integer>level=newArrayList<>();for(inti=0;i<size;i++){TreeNodenode=queue.poll();level.add(node.val);if(node.left!=null)queue.offer(node.left);if(node.right!=null)queue.offer(node.right);}res.add(level);}returnres;}解析：-使用隊(duì)列實(shí)現(xiàn)廣度優(yōu)先遍歷。-每次遍歷當(dāng)前層的所有節(jié)點(diǎn)，并將其子節(jié)點(diǎn)加入隊(duì)列。-時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(n)。二、算法設(shè)計(jì)題題4（LRU緩存機(jī)制）答案：javaclassLRUCache{privateintcapacity;privateMap<Integer,Integer>map;privateDeque<Integer>deque;publicLRUCache(intcapacity){this.capacity=capacity;map=newHashMap<>();deque=newLinkedList<>();}publicintget(intkey){if(!map.containsKey(key))return-1;//將訪問(wèn)的元素移到隊(duì)尾deque.remove(key);deque.offerLast(key);returnmap.get(key);}publicvoidput(intkey,intvalue){if(map.containsKey(key)){//更新值，并移到隊(duì)尾deque.remove(key);deque.offerLast(key);map.put(key,value);}else{if(map.size()==capacity){//移除最久未使用的元素intoldKey=deque.pollFirst();map.remove(oldKey);}deque.offerLast(key);map.put(key,value);}}}解析：-使用哈希表+雙向鏈表實(shí)現(xiàn)。哈希表存儲(chǔ)`(key,value)`，鏈表維護(hù)訪問(wèn)順序。-`get`操作時(shí)，將訪問(wèn)的元素移到鏈表尾部。-`put`操作時(shí)，如果容量已滿，移除鏈表頭部元素（最久未使用），然后添加新元素到鏈表尾部。-時(shí)間復(fù)雜度O(1)，空間復(fù)雜度O(capacity)。題5（合并K個(gè)排序鏈表）答案：javapublicListNodemergeKLists(List<ListNode>lists){if(lists==null||lists.isEmpty())returnnull;PriorityQueue<ListNode>pq=newPriorityQueue<>(lists.size(),CparingInt(node->node.val));for(ListNodehead:lists){if(head!=null){pq.offer(head);}}ListNodedummy=newListNode(0);ListNodetail=dummy;while(!pq.isEmpty()){ListNodenode=pq.poll();tail.next=node;tail=tail.next;if(node.next!=null){pq.offer(node.next);}}returndummy.next;}解析：-使用優(yōu)先隊(duì)列（最小堆）維護(hù)當(dāng)前各鏈表頭部，每次彈出最小節(jié)點(diǎn)。-時(shí)間復(fù)雜度O(nlogk)，空間復(fù)雜度O(k)。-`n`是所有鏈表的總節(jié)點(diǎn)數(shù)，`k`是鏈表數(shù)量。三、復(fù)雜度分析題題6（對(duì)數(shù)時(shí)間算法分析）答案：算法步驟：1.初始化`left=0`，`right=arr.length-1`。2.當(dāng)`left<=right`時(shí)：-計(jì)算`mid=left+(right-left)/2`。-如果`arr[mid]==target`，返回`true`。-如果`arr[mid]<target`，則`left=mid+1`。-如果`arr[mid]>target`，則`right=mid-1`。3.未找到則返回`false`。復(fù)雜度分析：-每次操作將搜索范圍減半，因此時(shí)間復(fù)雜度為O(logn)。-空間復(fù)雜度為O(1)。題7（動(dòng)態(tài)規(guī)劃問(wèn)題復(fù)雜度分析）答案：時(shí)間復(fù)雜度：-基于遞歸或迭代，每個(gè)狀態(tài)只計(jì)算一次，狀態(tài)數(shù)為`nW`，因此時(shí)間復(fù)雜度為O(nW)?？臻g復(fù)雜度：-未優(yōu)化的動(dòng)態(tài)規(guī)劃需要存儲(chǔ)`nW`狀態(tài)，空間復(fù)雜度為O(nW)。-可以使用滾動(dòng)數(shù)組優(yōu)化至O(W)，僅存儲(chǔ)當(dāng)前層和上一層的狀態(tài)。優(yōu)化方法：javapublicintknapsack(int[]weights,int[]values,intW)