2026年Java算法面試題與代碼實(shí)現(xiàn)參考一、數(shù)組與字符串（5題，每題10分，共50分）1.題目：給定一個(gè)未排序的整數(shù)數(shù)組，返回其中缺失的數(shù)字。示例：輸入：`[3,0,1]`，輸出：`2`要求：-時(shí)間復(fù)雜度O(n)-空間復(fù)雜度O(1)答案與解析：javapublicintmissingNumber(int[]nums){intn=nums.length;intexpectedSum=n(n+1)/2;intactualSum=0;for(intnum:nums){actualSum+=num;}returnexpectedSum-actualSum;}解析：數(shù)組應(yīng)包含從0到n的所有數(shù)字，其和為`n(n+1)/2`。通過(guò)計(jì)算實(shí)際和與預(yù)期和的差值，即可得到缺失的數(shù)字。此方法利用數(shù)學(xué)公式，避免額外空間。2.題目：將字符串中的字母移到左邊，數(shù)字移到右邊，其他字符保持原位。示例：輸入：`"a1b2c3d4!"`，輸出：`"abcd1234!"`要求：-雙指針?lè)ǎ皇褂妙~外數(shù)據(jù)結(jié)構(gòu)答案與解析：javapublicStringreorganizeString(Strings){int[]counts=newint[128];for(charc:s.toCharArray()){counts[c]++;}char[]chars=s.toCharArray();intleft=0,right=0;while(right<chars.length){if(counts[chars[right]]==0){right++;continue;}if(chars[left]!=0&&chars[left]!=chars[right]){left++;}if(left==right){chars[left]=chars[right];counts[chars[right]]--;left++;}else{chars[right]=0;right++;}}returnnewString(chars);}解析：雙指針`left`和`right`分別從頭部和尾部遍歷，`left`用于放置字母，`right`用于收集數(shù)字。若`left`和`right`指向的字符相同，則將`right`的字符清零并移動(dòng)`right`；否則交換字符。最后過(guò)濾掉清零的部分。3.題目：判斷一個(gè)字符串是否是另一個(gè)字符串的子序列。示例：輸入：`s="abc"`，`t="ahbgdc"`，輸出：`true`要求：-時(shí)間復(fù)雜度O(n)答案與解析：javapublicbooleanisSubsequence(Strings,Stringt){intm=s.length(),n=t.length();inti=0,j=0;while(i<m&&j<n){if(s.charAt(i)==t.charAt(j)){i++;}j++;}returni==m;}解析：使用兩個(gè)指針?lè)謩e遍歷`s`和`t`，若`s`的字符在`t`中順序匹配，則移動(dòng)`s`的指針；始終移動(dòng)`t`的指針。若`s`遍歷完成，則返回`true`。4.題目：給定一個(gè)字符串，找到最長(zhǎng)的回文子串。示例：輸入：`"babad"`，輸出：`"bab"`或`"aba"`要求：-動(dòng)態(tài)規(guī)劃或中心擴(kuò)展法答案與解析（中心擴(kuò)展法）：javapublicStringlongestPalindrome(Strings){if(s==null||s.length()<1)return"";intstart=0,end=0;for(inti=0;i<s.length();i++){intlen1=expandAroundCenter(s,i,i);intlen2=expandAroundCenter(s,i,i+1);intlen=Math.max(len1,len2);if(len>end-start){start=i-(len-1)/2;end=i+len/2;}}returns.substring(start,end+1);}privateintexpandAroundCenter(Strings,intleft,intright){while(left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){left--;right++;}returnright-left-1;}解析：通過(guò)遍歷每個(gè)字符作為回文中心，分別擴(kuò)展奇數(shù)長(zhǎng)度和偶數(shù)長(zhǎng)度的回文。記錄最大回文子串的起始和結(jié)束位置。5.題目：統(tǒng)計(jì)字符串中所有字符的出現(xiàn)次數(shù)。示例：輸入：`"hello"`，輸出：`{'h':1,'e':1,'l':2,'o':1}`要求：-哈希表或數(shù)組實(shí)現(xiàn)答案與解析：javapublicMap<Character,Integer>countChars(Strings){Map<Character,Integer>map=newHashMap<>();for(charc:s.toCharArray()){map.put(c,map.getOrDefault(c,0)+1);}returnmap;}解析：使用`HashMap`遍歷字符串，統(tǒng)計(jì)每個(gè)字符的頻次。`getOrDefault`方法簡(jiǎn)化了計(jì)數(shù)邏輯。二、鏈表（4題，每題12分，共48分）1.題目：反轉(zhuǎn)鏈表。示例：輸入：`1->2->3->4->5`，輸出：`5->4->3->2->1`要求：-迭代或遞歸實(shí)現(xiàn)答案與解析（迭代）：javapublicListNodereverseList(ListNodehead){ListNodeprev=null;ListNodecurrent=head;while(current!=null){ListNodenext=current.next;current.next=prev;prev=current;current=next;}returnprev;}解析：使用三個(gè)指針`prev`、`current`、`next`，逐個(gè)反轉(zhuǎn)節(jié)點(diǎn)指針。初始`prev`為`null`，遍歷鏈表時(shí)將`current.next`指向`prev`，并移動(dòng)指針。2.題目：合并兩個(gè)排序鏈表，返回合并后的頭節(jié)點(diǎn)。示例：輸入：`l1=1->4->5`，`l2=1->3->4`，輸出：`1->1->3->4->4->5`要求：-遞歸或迭代實(shí)現(xiàn)答案與解析（迭代）：javapublicListNodemergeTwoLists(ListNodel1,ListNodel2){ListNodedummy=newListNode(0);ListNodecurrent=dummy;while(l1!=null&&l2!=null){if(l1.val<=l2.val){current.next=l1;l1=l1.next;}else{current.next=l2;l2=l2.next;}current=current.next;}if(l1!=null)current.next=l1;if(l2!=null)current.next=l2;returndummy.next;}解析：使用虛擬頭節(jié)點(diǎn)`dummy`簡(jiǎn)化邊界處理。比較兩個(gè)鏈表當(dāng)前節(jié)點(diǎn)的值，將較小節(jié)點(diǎn)接入結(jié)果鏈表，并移動(dòng)指針。最后處理剩余部分。3.題目：判斷鏈表是否存在環(huán)。示例：輸入：`3->2->0->-4->3`（`-4`指向`3`），輸出：`true`要求：-快慢指針?lè)ù鸢概c解析：javapublicbooleanhasCycle(ListNodehead){if(head==null||head.next==null)returnfalse;ListNodeslow=head,fast=head.next;while(fast!=slow){if(fast==null||fast.next==null)returnfalse;slow=slow.next;fast=fast.next.next;}returntrue;}解析：快指針`fast`每次移動(dòng)兩步，慢指針`slow`每次移動(dòng)一步。若存在環(huán)，快慢指針最終會(huì)相遇；否則`fast`會(huì)到達(dá)鏈表末尾。4.題目：刪除鏈表中的節(jié)點(diǎn)（非頭節(jié)點(diǎn)）。示例：輸入：鏈表`1->2->3->4->5`，刪除節(jié)點(diǎn)`3`，輸出：`1->2->4->5`要求：-只能訪問(wèn)要?jiǎng)h除的節(jié)點(diǎn)答案與解析：javapublicvoiddeleteNode(ListNodenode){if(node==null||node.next==null)return;node.val=node.next.val;node.next=node.next.next;}解析：無(wú)法直接刪除節(jié)點(diǎn)，但可以復(fù)制下一個(gè)節(jié)點(diǎn)的值到當(dāng)前節(jié)點(diǎn)，并跳過(guò)下一個(gè)節(jié)點(diǎn)，實(shí)現(xiàn)刪除。三、樹(shù)與圖（3題，每題16分，共48分）1.題目：二叉樹(shù)的層序遍歷（BFS）。示例：輸入：3/\920/\157輸出：`[[3],[9,20],[15,7]]`要求：-使用隊(duì)列實(shí)現(xiàn)答案與解析：javapublicList<List<Integer>>levelOrder(TreeNoderoot){List<List<Integer>>result=newArrayList<>();if(root==null)returnresult;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);}result.add(level);}returnresult;}解析：使用隊(duì)列按層遍歷樹(shù)。每層遍歷過(guò)程中，將節(jié)點(diǎn)值加入當(dāng)前層列表，子節(jié)點(diǎn)加入隊(duì)列，最后將當(dāng)前層列表加入結(jié)果。2.題目：判斷二叉樹(shù)是否對(duì)稱。示例：輸入：1/\22/\/\3443輸出：`true`要求：-遞歸判斷答案與解析：javapublicbooleanisSymmetric(TreeNoderoot){returnisMirror(root,root);}privatebooleanisMirror(TreeNodet1,TreeNodet2){if(t1==null&&t2==null)returntrue;if(t1==null||t2==null)returnfalse;returnt1.val==t2.val&&isMirror(t1.left,t2.right)&&isMirror(t1.right,t2.left);}解析：對(duì)稱性判斷分為兩部分：左子樹(shù)的左節(jié)點(diǎn)與右子樹(shù)的右節(jié)點(diǎn)對(duì)稱，左子樹(shù)的右節(jié)點(diǎn)與右子樹(shù)的左節(jié)點(diǎn)對(duì)稱。遞歸檢查每一對(duì)節(jié)點(diǎn)。3.題目：給定一個(gè)圖，找到最短路徑（Dijkstra算法）。示例：輸入：graph={'A':['B','C','E'],'B':['A','D','E'],'C':['A','F','E'],'D':['B'],'E':['A','B','C','F'],'F':['C','E']}從`A`到`C`的最短路徑：`A->E->C`，距離：`2`要求：-使用優(yōu)先隊(duì)列優(yōu)化答案與解析：javaimportjava.util.;publicintshortestPathLength(Map<String,List<String>>graph,Stringstart,Stringend){Map<String,Integer>distances=newHashMap<>();PriorityQueue<String>pq=newPriorityQueue<>(CparingInt(distances::get));distances.put(start,0);pq.offer(start);while(!pq.isEmpty()){Stringcurrent=pq.poll();if(current.equals(end))returndistances.get(current);for(Stringneighbor:graph.get(current)){intnewDist=distances.get(current)+1;if(!distances.containsKey(neighbor)||newDist<distances.get(neighbor)){distances.put(neighbor,newDist);pq.offer(neighbor);}}}return-1;}解析：使用Dijkstra算法，優(yōu)先隊(duì)列按距離排序節(jié)點(diǎn)。初始化起點(diǎn)距離為0，遍歷鄰接節(jié)點(diǎn)時(shí)更新最短距離。當(dāng)找到終點(diǎn)時(shí)返回距離。四、動(dòng)態(tài)規(guī)劃（2題，每題20分，共40分）1.題目：斐波那契數(shù)列的第n項(xiàng)。示例：輸入：`n=5`，輸出：`5`要求：-動(dòng)態(tài)規(guī)劃或記憶化遞歸答案與解析（動(dòng)態(tài)規(guī)劃）：javapublicintfib(intn){if(n<=1)returnn;int[]dp=newint[n+1];dp[0]=0;dp[1]=1;for(inti=2;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}returndp[n];}解析：使用數(shù)組`dp`存儲(chǔ)子問(wèn)題解，`dp[i]=dp[i-1]+dp[i-2]`?？臻g可優(yōu)化為`O(1)`。2.題目：爬樓梯問(wèn)題：每次可爬1或2階，共n階，有多少種爬法。示例：輸入：`n=3`，輸出：`3`（`1+1+1`、`1+2`、`2+1`）要求：-動(dòng)態(tài)規(guī)劃答案與解析：javapublicintclimbStairs(intn){if(n<=2)returnn;int[]dp=newint[n+1];dp[1]=1;dp[2]=2;for(inti=3;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}returndp[n];}解析：與斐波那契類似，`dp[i]=dp[i-1]