Java开发工程师算法面试题及解析

2026年Java开发工程师算法面试题及解析一、编程实现题（共3题，每题20分）1.题1（20分）：字符串子序列判断题目：给定两个字符串`s`和`t`，判断`t`是否为`s`的子序列。子序列是指可以通过删除`s`中的某些字符而不改变剩余字符的相对顺序得到`t`。示例：-输入：`s="abcde"`,`t="ace"`→输出：`true`-输入：`s="abcde"`,`t="aec"`→输出：`false`要求：-时间复杂度不超过O(n)，空间复杂度不超过O(1)。-请实现`booleanisSubsequence(Strings,Stringt)`方法。2.题2（20分）：滑动窗口最大值题目：给定一个整数数组`nums`和一个整数`k`，找到长度为`k`的连续子数组，输出该子数组内所有元素的最大值。示例：-输入：`nums=[1,3,-1,-3,5,3,6,7]`,`k=3`→输出：`[3,3,5,5,6,7]`要求：-使用单调队列实现，时间复杂度O(n)，空间复杂度O(k)。-请实现`int[]maxSlidingWindow(int[]nums,intk)`方法。3.题3（20分）：二叉树层序遍历题目：给定一个二叉树的根节点`root`，返回其层序遍历的结果（从上到下，同一层从左到右）。示例：-输入：`root=[3,9,20,null,null,15,7]`→输出：`[[3],[9,20],[15,7]]`要求：-使用队列实现，时间复杂度O(n)，空间复杂度O(n)。-请实现`List<List<Integer>>levelOrder(TreeNoderoot)`方法。二、算法设计题（共2题，每题25分）1.题4（25分）：LRU缓存机制题目：设计一个LRU（LeastRecentlyUsed）缓存机制，支持`get`和`put`操作。缓存容量为`capacity`，当缓存容量已满时，最近最少使用的元素将被移除以给新元素腾出空间。要求：-`get(key)`：返回key对应的值，如果不存在返回-1。-`put(key,value)`：插入或更新key-value对。如果键已存在，则更新其值；如果键不存在，则添加该键值对。如果达到容量上限，则删除最近最少使用的元素。示例：-初始化：`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`（未命中）提示：-可使用哈希表+双向链表实现，时间复杂度O(1)。2.题5（25分）：合并K个排序链表题目：给定`k`个排序链表，合并它们为一个新的排序链表。示例：-输入：`head1=[1,4,5]`,`head2=[1,3,4]`,`head3=[2,6]`→输出：`[1,1,2,3,4,4,5,6]`要求：-使用优先队列（最小堆）实现，时间复杂度O(nlogk)，空间复杂度O(k)。-请实现`ListNodemergeKLists(List<ListNode>lists)`方法。三、复杂度分析题（共2题，每题15分）1.题6（15分）：对数时间算法分析题目：给定一个有序数组`arr`，设计一个算法，在O(logn)时间复杂度内判断某个元素`target`是否存在于数组中。要求：-请描述算法步骤，并解释为什么时间复杂度为O(logn)。-假设数组中元素不重复，`target`可能存在或不存在。2.题7（15分）：动态规划问题复杂度分析题目：给定一个背包问题：容量为`W`的背包，有`n`件物品，每件物品的重量为`weights[i]`，价值为`values[i]`。求背包能装下的最大价值。要求：-请解释动态规划解法的时间复杂度和空间复杂度，并说明如何优化空间复杂度至O(W)。答案及解析一、编程实现题题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();}解析：-使用双指针法，`i`遍历`s`，`j`遍历`t`。-当`s[i]==t[j]`时，`i++`，表示当前字符匹配；否则`j++`跳过`t`中的字符。-最终判断`i`是否遍历完`s`，如果是则`t`是`s`的子序列。-时间复杂度O(n)，空间复杂度O(1)。题2（滑动窗口最大值）答案：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++){//移除不在窗口内的元素if(!deque.isEmpty()&&deque.peekFirst()<i-k+1){deque.pollFirst();}//移除比当前元素小的元素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;}解析：-使用单调递减队列，队列中存储的是元素的索引。-滑动窗口移动时，维护队列头部为当前窗口最大值。-每次添加新元素时，移除队列中比当前元素小的索引，保证队列单调递减。-时间复杂度O(n)，空间复杂度O(k)。题3（二叉树层序遍历）答案：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;}解析：-使用队列实现广度优先遍历。-每次遍历当前层的所有节点，并将其子节点加入队列。-时间复杂度O(n)，空间复杂度O(n)。二、算法设计题题4（LRU缓存机制）答案：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;//将访问的元素移到队尾deque.remove(key);deque.offerLast(key);returnmap.get(key);}publicvoidput(intkey,intvalue){if(map.containsKey(key)){//更新值，并移到队尾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);}}}解析：-使用哈希表+双向链表实现。哈希表存储`(key,value)`，链表维护访问顺序。-`get`操作时，将访问的元素移到链表尾部。-`put`操作时，如果容量已满，移除链表头部元素（最久未使用），然后添加新元素到链表尾部。-时间复杂度O(1)，空间复杂度O(capacity)。题5（合并K个排序链表）答案：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;}解析：-使用优先队列（最小堆）维护当前各链表头部，每次弹出最小节点。-时间复杂度O(nlogk)，空间复杂度O(k)。-`n`是所有链表的总节点数，`k`是链表数量。三、复杂度分析题题6（对数时间算法分析）答案：算法步骤：1.初始化`left=0`，`right=arr.length-1`。2.当`left<=right`时：-计算`mid=left+(right-left)/2`。-如果`arr[mid]==target`，返回`true`。-如果`arr[mid]<target`，则`left=mid+1`。-如果`arr[mid]>target`，则`right=mid-1`。3.未找到则返回`false`。复杂度分析：-每次操作将搜索范围减半，因此时间复杂度为O(logn)。-空间复杂度为O(1)。题7（动态规划问题复杂度分析）答案：时间复杂度：-基于递归或迭代，每个状态只计算一次，状态数为`nW`，因此时间复杂度为O(nW)。空间复杂度：-未优化的动态规划需要存储`nW`状态，空间复杂度为O(nW)。-可以使用滚动数组优化至O(W)，仅存储当前层和上一层的状态。优化方法：javapublicintknapsack(int[]weights,int[]values,intW)