Java高级算法笔试真题（含详细解析答案）

Java高级算法笔试真题（含详细解析答案）适用场景：Java中高级开发、后端架构师初面/笔面、社招算法专项笔试题型说明：基础算法选择题、高频手写编程题、工程场景算法题，所有题目均为互联网企业高频真题，答案附带思路、代码、复杂度分析，贴合真实答题规范考试时长：90分钟满分：100分一、单项选择题（共5题，每题4分，共20分）1.以下关于时间复杂度的描述，正确的是（）A.冒泡排序最优时间复杂度为O(n²)B.哈希表查询的平均时间复杂度为O(1)C.二分查找的最坏时间复杂度为O(n)D.快速排序最坏时间复杂度为O(nlogn)答案：B详细解析：A错误：冒泡排序优化后（提前判断有序），最优时间复杂度为O(n)，无序情况下为O(n²)；B正确：哈希表通过哈希函数直接定位索引，无哈希冲突时查询、插入、删除均为O(1)平均复杂度；C错误：二分查找基于有序数组，每次折半，最坏时间复杂度为O(logn)；D错误：快速排序在数组完全有序/逆序的最坏场景下，时间复杂度退化为O(n²)，平均复杂度为O(nlogn)。2.Java中ArrayList和LinkedList的遍历与删除场景，下列说法正确的是（）A.随机访问场景下，LinkedList效率更高B.头尾频繁插入删除，LinkedList效率优于ArrayListC.ArrayList新增元素永远不会触发扩容D.LinkedList支持随机索引快速访问答案：B详细解析：ArrayList基于动态数组实现，支持O(1)随机访问，但中间/头部插入删除需要移动数组元素，效率低，容量不足时会触发扩容拷贝数组；LinkedList基于双向链表实现，不支持随机访问，查询需要遍历节点，但头尾节点的插入、删除仅需修改指针，无需移动元素，高频头尾操作效率更高。3.以下排序算法中，属于稳定排序且时间复杂度为O(nlogn)的是（）A.快速排序B.堆排序C.归并排序D.选择排序答案：C详细解析：稳定排序：相等元素相对顺序排序后不变；快速排序、堆排序：O(nlogn)，不稳定排序；选择排序：O(n²)，不稳定排序；归并排序：分治思想，平均/最优/最坏复杂度均为O(nlogn)，是经典稳定排序算法。4.二叉树的前序遍历顺序为：根-左-右，中序遍历为左-根-右，已知前序序列ABCDEF，中序序列CBAEDF，后序序列为（）A.CBEFDAB.CBFEDAC.BCEDFAD.CBEDFA答案：D详细解析：1.前序首元素A为整棵树根节点；2.结合中序序列，A左侧CBA为左子树节点，右侧EDF为右子树节点；3.前序第二个元素B为左子树根，中序B左侧C为左节点，右侧A为右节点；4.递归推导右子树，最终后序遍历（左-右-根）结果为：CBEDFA。5.关于红黑树的特性，下列说法错误的是（）A.根节点一定是黑色B.任意路径黑色节点数量相同C.红色节点的子节点可以为红色D.所有叶子节点（空节点）为黑色答案：C详细解析：红黑树核心约束：1.根节点黑色；2.叶子空节点黑色；3.红色节点的左右子节点必须为黑色（不能出现连续红节点）；4.任意根到叶子路径黑色节点数一致。因此C选项错误。二、填空题（共3题，每题6分，共18分）1.二分查找的前提是________，时间复杂度为________。答案：数组有序、O(logn)2.二叉搜索树的核心特性是：________。答案：左子树所有节点值<根节点值<右子树所有节点值，左右子树均为二叉搜索树3.解决哈希冲突的两种主流方式是________和________，JavaHashMap采用的是________。答案：开放定址法、链地址法、链地址法（数组+链表+红黑树）三、手写编程算法题（共3题，共52分）题目1：两数之和（简单，16分）给定一个整数数组nums和一个整数目标值target，请在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。要求：数组中同一元素不能重复使用，每种输入只对应一个答案，可按任意顺序返回答案。示例：输入：nums=[2,7,11,15],target=9输出：[0,1]解题思路：采用哈希表一次遍历解法，遍历数组时，用map存储「数值-下标」，每次计算当前值的补数（target-nums[i]），判断补数是否已存在于map中，存在则直接返回下标，不存在则存入当前数值和下标。时间复杂度O(n)，空间复杂度O(n)，优于双层循环暴力解法。完整Java代码：java

importjava.util.HashMap;

importjava.util.Map;

publicclassTwoSum{

publicint[]twoSum(int[]nums,inttarget){

Map<Integer,Integer>map=newHashMap<>();

for(inti=0;i<nums.length;i++){

//计算需要匹配的补数

intcomplement=target-nums[i];

//补数存在，直接返回结果

if(map.containsKey(complement)){

returnnewint[]{map.get(complement),i};

}

//存入当前数值和下标

map.put(nums[i],i);

}

//题目保证有唯一解，此处仅占位

returnnewint[0];

}

}题目2：反转单链表（中等，18分）给你单链表的头节点head，请你反转链表，并返回反转后的链表头节点。示例：输入：1->2->3->4->5输出：5->4->3->2->1解题思路：采用迭代法（职场最优解），定义前驱节点、当前节点，遍历链表，逐个修改节点指针方向，将当前节点的next指向前驱节点，而后迭代更新前驱和当前节点，直到遍历完成。时间复杂度O(n)，空间复杂度O(1)，无额外空间开销。完整Java代码：java

//定义链表节点

classListNode{

intval;

ListNodenext;

ListNode(){}

ListNode(intval){this.val=val;}

ListNode(intval,ListNodenext){this.val=val;this.next=next;}

}

publicclassReverseList{

publicListNodereverseList(ListNodehead){

//前驱节点初始为空

ListNodeprev=null;

//当前节点指向头节点

ListNodecurr=head;

while(curr!=null){

//临时保存下一个节点

ListNodenext=curr.next;

//反转指针

curr.next=prev;

//前驱、当前节点后移

prev=curr;

curr=next;

}

//最终prev为新链表头节点

returnprev;

}

}题目3：最长无重复子串（中等，18分）给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。示例：输入：s="abcabcbb"输出：3解释：最长无重复子串为"abc"，长度为3解题思路：滑动窗口+哈希表解法，用双指针维护窗口左右边界，窗口内始终保持字符无重复。哈希表记录每个字符最后出现的下标，遍历字符串时，若当前字符已在窗口内出现，则更新窗口左边界，同时实时更新最大窗口长度。时间复杂度O(n)，仅遍历一次字符串。完整Java代码：java

importjava.util.HashMap;

importjava.util.Map;

publicclassLengthOfLongestSubstring{

publicintlengthOfLongestSubstring(Strings){

//存储字符及最后出现的下标

Map<Character,Integer>charMap=newHashMap<>();

intmaxLen=0;

//滑动窗口左边界

intleft=0;

for(intright=0;right<s.length();right++){

charch=s.charAt(right);

//字符重复且在窗口内，更新左边界

if(charMap.containsKey(ch)&&charMap.get(ch)>=left){

left=charMap.get(ch)+1;

}

//更新字符最新下标

charMap.put(ch,right);

//计算当前窗口最大长度

maxLen=Math.max(maxLen,right-left+1);

}

returnmaxLen;

}

}四、简答题（10分）题目：简述快速排序的核心原理、优缺点及工程优化手段参考答案：1.核心原理：采用分治思想，选取一个基准值，将数组分区为「小于基准、大于基准」两部分，再递归对左右子数组进行分区排序，最终实现整