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

Java算法笔试题（含详细答案解析）本次试题为互联网企业Java后端笔试高频算法题型，包含基础算法选择题、经典编程算法题，难度贴合校招、初级社招笔试真实场景，所有题目均附带详细解题思路、完整可运行Java代码及答案解析。一、算法基础选择题（共5题）1.以下关于数组和链表的说法，错误的是（）A.数组随机访问效率高，插入删除效率低B.链表随机访问效率低，插入删除效率高C.数组和链表都属于线性数据结构D.链表需要连续的内存空间存储数据答案：D解析：数组依赖连续内存空间，而链表通过指针/引用串联节点，内存空间是分散的，不需要连续内存。线性数据结构包含数组、链表、栈、队列，因此ABC说法均正确。2.时间复杂度为O(nlogn)的排序算法是（）A.冒泡排序B.快速排序C.插入排序D.选择排序答案：B解析：冒泡、插入、选择排序的平均和最坏时间复杂度均为O(n²)；快速排序平均时间复杂度为O(nlogn)，最坏为O(n²)，日常算法考察中，归并排序、快速排序、堆排序均为O(nlogn)级别的高效排序。3.二叉树的前序遍历顺序是（）A.左子树-根节点-右子树B.根节点-左子树-右子树C.左子树-右子树-根节点D.根节点-右子树-左子树答案：B解析：二叉树遍历核心规则：前序（根左右）、中序（左根右）、后序（左右根），是二叉树算法的基础核心考点。4.哈希表查找元素的平均时间复杂度为（）A.O(1)B.O(n)C.O(logn)D.O(n²)答案：A解析：哈希表通过哈希函数直接定位元素存储位置，无哈希冲突时，查找、插入、删除操作均为常数级时间复杂度O(1)；极端哈希冲突情况下会退化为O(n)，笔试默认考察平均时间复杂度。5.以下不属于贪心算法特性的是（）A.局部最优推导全局最优B.无需回溯C.可以解决所有最优解问题D.每一步只做当前最优选择答案：C解析：贪心算法仅能解决部分具备贪心选择性质和最优子结构的问题，部分场景下局部最优无法推导全局最优，无法替代动态规划、回溯算法，不能解决所有最优解问题。二、编程算法大题（共4题，高频真题）题目1：两数之和（简单·必考）题目描述：给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，且数组中同一个元素不能使用两遍。示例：输入：nums=[2,7,11,15],target=9输出：[0,1]解题思路：使用HashMap存储数组元素和对应下标，遍历数组时，计算当前元素需要的互补值（target-nums[i]），判断哈希表中是否存在该值，存在则直接返回下标，不存在则将当前元素存入哈希表。时间复杂度O(n)，空间复杂度O(n)，优于双重循环暴力解法。java

importjava.util.HashMap;

importjava.util.Map;

publicclassTwoSum{

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

//key：数组元素，value：元素下标

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[]{};

}

publicstaticvoidmain(String[]args){

int[]nums={2,7,11,15};

inttarget=9;

int[]res=twoSum(nums,target);

System.out.println("下标："+res[0]+","+res[1]);

}

}答案总结：通过哈希表一次遍历完成查找，是笔试最优解法，避免暴力双层循环的O(n²)时间复杂度。题目2：反转单链表（简单·面试高频）题目描述：给你一个单链表的头节点head，请你反转该链表，并返回反转后的链表头节点。示例：输入：1->2->3->4->5输出：5->4->3->2->1解题思路：采用迭代法，定义前驱节点、当前节点，遍历链表时，逐个修改节点指向，将当前节点的next指向前驱节点，依次后移，最终返回新的头节点。该方法空间复杂度O(1)，是笔试最优解法。java

//定义链表节点

classListNode{

intval;

ListNodenext;

ListNode(){}

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

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

}

publicclassReverseList{

publicstaticListNodereverseList(ListNodehead){

ListNodepre=null;//前驱节点

ListNodecur=head;//当前节点

while(cur!=null){

//保存当前节点的下一个节点

ListNodenext=cur.next;

//反转指针

cur.next=pre;

//前驱、当前节点后移

pre=cur;

cur=next;

}

//pre为反转后的头节点

returnpre;

}

//遍历打印链表

publicstaticvoidprintList(ListNodehead){

ListNodetemp=head;

while(temp!=null){

System.out.print(temp.val+"");

temp=temp.next;

}

}

publicstaticvoidmain(String[]args){

//构建链表1->2->3->4->5

ListNodehead=newListNode(1);

head.next=newListNode(2);

head.next.next=newListNode(3);

head.next.next.next=newListNode(4);

head.next.next.next.next=newListNode(5);

ListNodenewHead=reverseList(head);

printList(newHead);//输出：54321

}

}答案总结：迭代反转链表是笔试必掌握解法，逻辑简单、无递归栈溢出风险，空间效率极高。题目3：有效的括号（中等·基础栈应用）题目描述：给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合；左括号必须以正确的顺序闭合；每个右括号都有一个对应的相同类型的左括号。示例：输入：s="()[]{}"输出：true；输入：s="(]"输出：false解题思路：利用栈的先进后出特性，遍历字符串，遇到左括号则将对应的右括号入栈；遇到右括号时，判断栈是否为空、栈顶元素是否等于当前括号，不匹配则直接返回false。遍历结束后栈为空则说明全部匹配成功。java

importjava.util.Stack;

publicclassValidBracket{

publicstaticbooleanisValid(Strings){

Stack<Character>stack=newStack<>();

for(charc:s.toCharArray()){

//左括号入栈对应右括号

if(c=='('){

stack.push(')');

}elseif(c=='{'){

stack.push('}');

}elseif(c=='['){

stack.push(']');

}else{

//右括号：栈空或栈顶不匹配，直接无效

if(stack.isEmpty()||stack.pop()!=c){

returnfalse;

}

}

}

//栈空代表全部匹配完成

returnstack.isEmpty();

}

publicstaticvoidmain(String[]args){

System.out.println(isValid("()[]{}"));//true

System.out.println(isValid("(]"));//false

}

}答案总结：括号匹配是栈结构的经典应用场景，时间复杂度O(n)，一次遍历即可完成校验，是笔试高频基础算法题。题目4：二分查找（简单·必考查找算法）题目描述：给定一个n个元素有序的（升序）整型数组nums和一个目标值target，写一个函数搜索nums中的target，如果目标值存在返回下标，否则返回-1。示例：输入：nums=[-1,0,3,5,9,12],target=9输出：4解题思路：二分查找仅适用于有序数组，通过左右指针确定查找区间，每次取中间值对比目标值，缩小一半查找区间，时间复杂度O(logn)，远优于顺序查找的O(n)。java

publicclassBinarySearch{

publicstaticintsearch(int[]nums,inttarget){

intleft=0;

intright=nums.length-1;

//循环查找

while(left<=right){

//防止溢出，等价于(left+right)/2

intmid=left+(right-left)/2;

if(nums[mid]==target){

returnmid;

}elseif(nums[mid]<target){

//目标值更大，去右区间查找

left=mid+1;

}else{

//目标值更小，去左区间查找

right=mid-1;

}

}

//未找到目标值

return-1;

}

publicstaticvoidmain(String[]args){

int[]