2026年Java算法面试题与代码实现参考

2026年Java算法面试题与代码实现参考一、数组与字符串（5题，每题10分，共50分）1.题目：给定一个未排序的整数数组，返回其中缺失的数字。示例：输入：`[3,0,1]`，输出：`2`要求：-时间复杂度O(n)-空间复杂度O(1)答案与解析：javapublicintmissingNumber(int[]nums){intn=nums.length;intexpectedSum=n(n+1)/2;intactualSum=0;for(intnum:nums){actualSum+=num;}returnexpectedSum-actualSum;}解析：数组应包含从0到n的所有数字，其和为`n(n+1)/2`。通过计算实际和与预期和的差值，即可得到缺失的数字。此方法利用数学公式，避免额外空间。2.题目：将字符串中的字母移到左边，数字移到右边，其他字符保持原位。示例：输入：`"a1b2c3d4!"`，输出：`"abcd1234!"`要求：-双指针法，不使用额外数据结构答案与解析：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`用于收集数字。若`left`和`right`指向的字符相同，则将`right`的字符清零并移动`right`；否则交换字符。最后过滤掉清零的部分。3.题目：判断一个字符串是否是另一个字符串的子序列。示例：输入：`s="abc"`，`t="ahbgdc"`，输出：`true`要求：-时间复杂度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;}解析：使用两个指针分别遍历`s`和`t`，若`s`的字符在`t`中顺序匹配，则移动`s`的指针；始终移动`t`的指针。若`s`遍历完成，则返回`true`。4.题目：给定一个字符串，找到最长的回文子串。示例：输入：`"babad"`，输出：`"bab"`或`"aba"`要求：-动态规划或中心扩展法答案与解析（中心扩展法）：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;}解析：通过遍历每个字符作为回文中心，分别扩展奇数长度和偶数长度的回文。记录最大回文子串的起始和结束位置。5.题目：统计字符串中所有字符的出现次数。示例：输入：`"hello"`，输出：`{'h':1,'e':1,'l':2,'o':1}`要求：-哈希表或数组实现答案与解析：javapublicMap<Character,Integer>countChars(Strings){Map<Character,Integer>map=newHashMap<>();for(charc:s.toCharArray()){map.put(c,map.getOrDefault(c,0)+1);}returnmap;}解析：使用`HashMap`遍历字符串，统计每个字符的频次。`getOrDefault`方法简化了计数逻辑。二、链表（4题，每题12分，共48分）1.题目：反转链表。示例：输入：`1->2->3->4->5`，输出：`5->4->3->2->1`要求：-迭代或递归实现答案与解析（迭代）：javapublicListNodereverseList(ListNodehead){ListNodeprev=null;ListNodecurrent=head;while(current!=null){ListNodenext=current.next;current.next=prev;prev=current;current=next;}returnprev;}解析：使用三个指针`prev`、`current`、`next`，逐个反转节点指针。初始`prev`为`null`，遍历链表时将`current.next`指向`prev`，并移动指针。2.题目：合并两个排序链表，返回合并后的头节点。示例：输入：`l1=1->4->5`，`l2=1->3->4`，输出：`1->1->3->4->4->5`要求：-递归或迭代实现答案与解析（迭代）：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;}解析：使用虚拟头节点`dummy`简化边界处理。比较两个链表当前节点的值，将较小节点接入结果链表，并移动指针。最后处理剩余部分。3.题目：判断链表是否存在环。示例：输入：`3->2->0->-4->3`（`-4`指向`3`），输出：`true`要求：-快慢指针法答案与解析：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`每次移动两步，慢指针`slow`每次移动一步。若存在环，快慢指针最终会相遇；否则`fast`会到达链表末尾。4.题目：删除链表中的节点（非头节点）。示例：输入：链表`1->2->3->4->5`，删除节点`3`，输出：`1->2->4->5`要求：-只能访问要删除的节点答案与解析：javapublicvoiddeleteNode(ListNodenode){if(node==null||node.next==null)return;node.val=node.next.val;node.next=node.next.next;}解析：无法直接删除节点，但可以复制下一个节点的值到当前节点，并跳过下一个节点，实现删除。三、树与图（3题，每题16分，共48分）1.题目：二叉树的层序遍历（BFS）。示例：输入：3/\920/\157输出：`[[3],[9,20],[15,7]]`要求：-使用队列实现答案与解析：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;}解析：使用队列按层遍历树。每层遍历过程中，将节点值加入当前层列表，子节点加入队列，最后将当前层列表加入结果。2.题目：判断二叉树是否对称。示例：输入：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);}解析：对称性判断分为两部分：左子树的左节点与右子树的右节点对称，左子树的右节点与右子树的左节点对称。递归检查每一对节点。3.题目：给定一个图，找到最短路径（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`要求：-使用优先队列优化答案与解析：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算法，优先队列按距离排序节点。初始化起点距离为0，遍历邻接节点时更新最短距离。当找到终点时返回距离。四、动态规划（2题，每题20分，共40分）1.题目：斐波那契数列的第n项。示例：输入：`n=5`，输出：`5`要求：-动态规划或记忆化递归答案与解析（动态规划）：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];}解析：使用数组`dp`存储子问题解，`dp[i]=dp[i-1]+dp[i-2]`。空间可优化为`O(1)`。2.题目：爬楼梯问题：每次可爬1或2阶，共n阶，有多少种爬法。示例：输入：`n=3`，输出：`3`（`1+1+1`、`1+2`、`2+1`）要求：-动态规划答案与解析：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]