Java常见算法面试题及详细答案（实战面试版）

Java常见算法面试题及详细答案（实战面试版）本文整理互联网Java面试高频算法题，覆盖基础语法、数组、字符串、链表、排序、查找、递归、动态规划、常见思维题，答案贴合实际开发和面试答题逻辑，简洁易懂、无冗余套话，适配校招、社招面试场景。一、基础语法与思维算法题1.手写斐波那契数列（两种实现：递归+非递归）题目：输出斐波那契数列前n项，数列规则：F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)参考答案递归实现（代码简洁，但n过大存在栈溢出、重复计算问题，面试需说明优缺点）：java

//递归获取第n个斐波那契数

publicstaticintfibRecursion(intn){

if(n<0){

thrownewIllegalArgumentException("参数不合法");

}

if(n==0)return0;

if(n==1)return1;

returnfibRecursion(n-1)+fibRecursion(n-2);

}非递归迭代实现（面试推荐，时间复杂度O(n)，空间复杂度O(1)，效率更高）：java

publicstaticintfibIter(intn){

if(n<0){

thrownewIllegalArgumentException("参数不合法");

}

if(n==0)return0;

if(n==1)return1;

inta=0,b=1,res=0;

for(inti=2;i<=n;i++){

res=a+b;

a=b;

b=res;

}

returnres;

}面试加分点：递归实现时间复杂度O(2ⁿ)，存在大量重复计算，数值大时会栈溢出；迭代法无重复计算、无栈溢出风险，生产环境优先使用迭代。2.判断一个数是否为质数题目：输入一个正整数，判断是否是质数（素数），质数定义：大于1，只能被1和自身整除的自然数。参考答案java

publicstaticbooleanisPrime(intnum){

//小于2不是质数

if(num<2){

returnfalse;

}

//2是唯一的偶数质数

if(num==2){

returntrue;

}

//偶数直接排除

if(num%2==0){

returnfalse;

}

//只需遍历到平方根，减少循环次数

for(inti=3;i<=Math.sqrt(num);i+=2){

if(num%i==0){

returnfalse;

}

}

returntrue;

}优化思路：常规写法会遍历到num-1，优化后只遍历到平方根，时间复杂度从O(n)降到O(√n)，同时提前过滤偶数，大幅提升效率。3.整数反转题目：给一个32位整数，反转其数字，例如123→321，-123→-321，反转后超出整数范围返回0。参考答案java

publicstaticintreverseInt(intx){

intres=0;

while(x!=0){

//取最后一位数字

inttemp=x%10;

//溢出判断：正数溢出/负数溢出

if(res>Integer.MAX_VALUE/10||(res==Integer.MAX_VALUE/10&&temp>7)){

return0;

}

if(res<Integer.MIN_VALUE/10||(res==Integer.MIN_VALUE/10&&temp<-8)){

return0;

}

res=res*10+temp;

x=x/10;

}

returnres;

}面试重点：必须处理整型溢出问题，这是该题核心考点，只做反转不判溢出会直接扣分。二、字符串高频算法题1.字符串反转（两种方式）题目：输入任意字符串，完成整体反转，不使用自带reverse工具类。参考答案：字符数组交换法（最常用、效率最高）java

publicstaticStringreverseStr(Stringstr){

if(str==null||str.length()<=1){

returnstr;

}

char[]chars=str.toCharArray();

intleft=0;

intright=chars.length-1;

//双指针交换

while(left<right){

chartemp=chars[left];

chars[left]=chars[right];

chars[right]=temp;

left++;

right--;

}

returnnewString(chars);

}2.统计字符串中每个字符出现次数题目：输入一串字符串，统计每个字符的出现次数，无需排序。参考答案：利用HashMap存储字符和次数映射java

importjava.util.HashMap;

importjava.util.Map;

publicstaticvoidcountChar(Stringstr){

if(str==null||str.length()==0){

System.out.println("字符串为空");

return;

}

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

char[]chars=str.toCharArray();

for(charc:chars){

//存在则次数+1，不存在默认1

map.put(c,map.getOrDefault(c,0)+1);

}

//遍历输出结果

for(Map.Entry<Character,Integer>entry:map.entrySet()){

System.out.println("字符："+entry.getKey()+"，次数："+entry.getValue());

}

}3.判断字符串是否是回文字符串题目：回文串指正读、反读完全一致的字符串，如“abcba”“12321”，忽略大小写、无特殊符号。参考答案：双指针法java

publicstaticbooleanisPalindrome(Stringstr){

if(str==null||str.length()<=1){

returntrue;

}

//统一转小写，忽略大小写差异

Strings=str.toLowerCase();

intleft=0;

intright=s.length()-1;

while(left<right){

if(s.charAt(left)!=s.charAt(right)){

returnfalse;

}

left++;

right--;

}

returntrue;

}三、数组高频算法题1.数组去重题目：给定有序数组，原地去除重复元素，返回去重后的数组长度，不额外开辟大空间。参考答案：快慢指针法（面试最优解）java

publicstaticintremoveDuplicate(int[]arr){

if(arr==null||arr.length==0){

return0;

}

//慢指针：记录有效位置

intslow=0;

for(intfast=1;fast<arr.length;fast++){

//快慢指针值不同，说明是新元素

if(arr[fast]!=arr[slow]){

slow++;

arr[slow]=arr[fast];

}

}

returnslow+1;

}说明：该方法空间复杂度O(1)，原地修改数组，是笔试面试标准解法。2.两数之和题目：给定一个整数数组和一个目标值，找出数组中两个相加等于目标值的元素下标，假设每组输入只有一个答案。参考答案：HashMap优化（时间复杂度O(n)，优于双重循环）java

importjava.util.HashMap;

importjava.util.Map;

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

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

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

//计算需要匹配的差值

intdiff=target-nums[i];

if(map.containsKey(diff)){

//找到结果，返回下标

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

}

//未找到则存入当前值和下标

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

}

returnnewint[]{};

}面试对比：暴力双重循环时间O(n²)，哈希表解法仅遍历一次数组，效率大幅提升，是面试标准答案。3.找出数组最大值和最小值题目：遍历一次数组，同时找出最大值和最小值，减少循环次数。参考答案java

publicstaticint[]getMaxAndMin(int[]arr){

if(arr==null||arr.length==0){

returnnewint[]{};

}

intmax=arr[0];

intmin=arr[0];

//一次遍历完成比对

for(intnum:arr){

if(num>max){

max=num;

}

if(num<min){

min=num;

}

}

returnnewint[]{max,min};

}四、链表高频算法题1.单链表反转（面试必考）题目：手写单链表反转，返回反转后的链表头节点，提供迭代版（推荐）和递归版。先定义链表节点java

publicclassListNode{

intval;

ListNodenext;

ListNode(){}

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

}迭代解法（最优，无栈溢出风险）java

publicstaticListNodereverseList(ListNodehead){

ListNodepre=null;//前驱节点

ListNodecur=head;//当前节点

while(cur!=null){

//保存下一个节点

ListNodenext=cur.next;

//反转指针

cur.next=pre;

//指针后移

pre=cur;

cur=next;

}

returnpre;

}递归解法java

publicstaticListNodereverseRecursion(ListNodehead){

//终止条件：空节点或最后一个节点

if(head==null||head.next==null){

returnhead;

}

ListNodenewHead=reverseRecursion(head.next);

//反转指针

head.next.next=head;

head.next=null;

returnnewHead;

}面试总结：迭代法时间O(n)、空间O(1)；递归法空间O(n)（栈空间），长链表会栈溢出，工作中优先用迭代。2.判断链表是否有环题目：判断单链表是否存在环形结构。参考答案：快慢指针（龟兔赛跑）java

publicstaticbooleanhasCycle(ListNodehead){

if(head==null||head.next==null){

returnfalse;

}

//慢指针走1步，快指针走2步

ListNodeslow=head;

ListNodefast=head;

while(fast!=null&&fast.next!=null){

slow=slow.next;

fast=fast.next.next;

//相遇则有环

if(slow==fast){

returntrue;

}

}

returnfalse;

}原理：无环时快指针会优先走到末尾，有环时快慢指针一定会在环内相遇。五、排序算法高频面试题面试重点：手写冒泡、选择、快速排序，掌握各排序的时间复杂度、稳定性、优缺点。1.冒泡排序思路：相邻元素两两比对，大的后移，每轮排序确定一个最大值，稳定排序。java

publicstaticvoidbubbleSort(int[]arr){

if(arr==null||arr.length<=1)return;

for(inti=0;i<arr.length-1;i++){

//标记本轮是否交换，优化有序数组

booleanflag=false;

for(intj=0;j<arr.length-1-i;j++){

if(arr[j]>arr[j+1]){

inttemp=arr[j];

arr[j]=arr[j+1];

arr[j+1]=temp;

flag=true;

}

}

//无交换说明已有序，直接退出

if(!flag)break;

}

}复杂度：最好O(n)，最坏/平均O(n²)，空间O(1)，稳定。2.快速排序（面试必考）思路：选基准值，将数组分为左右两部分，左小右大，递归排序左右区间，不稳定排序，实际效率最高。java

publicstaticvoidquickSort(int[]arr,intleft,intright){

if(arr==null||arr.length<=1||left>=right)return;

intl=left,r=right;

//选取基准值

intpivot=arr[left];

while(l<r){

//从右往左找小于基准的值

while(l<r&&arr[r]>=pivot){

r--;

}

arr[l]=arr[r];

//从左往右找大于基准的值

while(l<r&&arr[l]<=pivot){

l++;

}

arr[r]=arr[l];

}

//基准值归位

arr[l]=pivot;

//递归排序左右

quickSort(arr,left,l-1);

quickSort(arr,l+1,right);

}复杂度：平均O(nlogn)，最坏O(n²)，空间O(logn)，不稳定，Java底层Arrays.sort()基本类型用快速排序。六、递归与动态规划简单高频题1.跳台阶问题题目：一只青蛙一次可以跳1级或2级台阶，求跳上n级台阶