常见算法面试题及详细答案(实战版)_第1页
常见算法面试题及详细答案(实战版)_第2页
常见算法面试题及详细答案(实战版)_第3页
常见算法面试题及详细答案(实战版)_第4页
常见算法面试题及详细答案(实战版)_第5页
已阅读5页,还剩3页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

常见算法面试题及详细答案(实战版)本文整理互联网校招、社招高频算法面试题,涵盖数组、链表、哈希、双指针、动态规划、贪心、二叉树等核心考点,所有题目均附通俗易懂的思路解析、完整可运行代码和细节答疑,贴合真实面试答题逻辑,无模板化话术。一、数组与双指针(面试最高频)1.两数之和题目:给定一个整数数组nums和一个整数目标值target,请你在该数组中找出和为目标值target的那两个整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案,且数组中同一个元素不能使用两遍。示例:nums=[2,7,11,15],target=9,输出:[0,1]解题思路常规暴力双层循环时间复杂度是O(n²),面试中会超时,最优解法是哈希表优化。遍历数组时,用哈希表存储「数值-下标」映射,每遍历一个元素,直接查表判断target-当前值是否存在。存在则直接返回两个下标,不存在则将当前值和下标存入哈希表,仅需一次遍历。完整代码(Java)java

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

//哈希表:key=数组数值,value=对应下标

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),仅遍历一次数组;空间复杂度:O(n),哈希表最多存储全部数组元素。面试加分点:主动提及暴力解法的弊端,说明哈希优化的核心逻辑,强调「先查表、后存值」避免重复使用同一元素。2.移除元素题目:给你一个数组nums和一个值val,你需要原地移除所有数值等于val的元素,并返回移除后数组的新长度。不要使用额外的数组空间,必须仅使用O(1)额外空间并原地修改输入数组。示例:nums=[3,2,2,3],val=3,输出:2,数组修改为[2,2]解题思路经典快慢双指针题型。慢指针记录新数组的有效位置,快指针遍历整个数组。快指针遍历到不等于val的元素时,将该元素赋值给慢指针位置,随后慢指针右移。遍历结束后,慢指针的数值就是新数组长度。完整代码(Java)java

publicintremoveElement(int[]nums,intval){

intslow=0;

//快指针遍历所有元素

for(intfast=0;fast<nums.length;fast++){

//保留不等于目标值的元素

if(nums[fast]!=val){

nums[slow]=nums[fast];

slow++;

}

}

returnslow;

}复杂度分析:时间O(n),空间O(1),完全满足原地修改要求。二、链表经典面试题1.反转链表题目:给你单链表的头节点head,请你反转链表,并返回反转后的链表头节点。示例:1->2->3->4->5反转后5->4->3->2->1解题思路面试必考基础题,首选迭代法(递归法可作为拓展回答)。定义三个指针:前驱节点pre、当前节点cur、后继节点next。遍历链表,每次先保存当前节点的下一个节点,再将当前节点的指针指向前驱节点,然后pre、cur依次后移,直到cur为空,此时pre就是新链表头节点。完整代码(Java)java

//链表节点定义

classListNode{

intval;

ListNodenext;

ListNode(){}

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

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

}

publicListNodereverseList(ListNodehead){

ListNodepre=null;

ListNodecur=head;

while(cur!=null){

//保存后继节点,防止断链

ListNodenext=cur.next;

//反转指针

cur.next=pre;

//指针后移

pre=cur;

cur=next;

}

returnpre;

}面试注意点:必须处理空链表、单节点链表边界情况,代码天然兼容所有边界,无需额外判断。2.链表中环的检测题目:给你一个链表的头节点head,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪next指针再次到达,则链表存在环。解题思路快慢指针(龟兔赛跑)最优解。慢指针每次走1步,快指针每次走2步。如果链表有环,快慢指针一定会相遇;如果无环,快指针会先走到链表末尾(null)。相比哈希存储节点的方法,空间复杂度更低。完整代码(Java)java

publicbooleanhasCycle(ListNodehead){

ListNodeslow=head;

ListNodefast=head;

//无环时快指针先走到末尾

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

slow=slow.next;

fast=fast.next.next;

//相遇则有环

if(slow==fast){

returntrue;

}

}

returnfalse;

}复杂度:时间O(n),空间O(1)。三、二叉树高频面试题1.二叉树的层序遍历题目:给你二叉树的根节点root,返回其节点值的层序遍历(逐层从左往右遍历所有节点)。解题思路层序遍历固定用队列实现。核心逻辑:每次记录当前队列的节点数量(当前层节点数),批量遍历当前层所有节点,取出节点存入结果,同时将左右子节点入队,循环直到队列为空。完整代码(Java)java

importjava.util.*;

//二叉树节点定义

classTreeNode{

intval;

TreeNodeleft;

TreeNoderight;

TreeNode(){}

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

TreeNode(intval,TreeNodeleft,TreeNoderight){

this.val=val;

this.left=left;

this.right=right;

}

}

publicList<List<Integer>>levelOrder(TreeNoderoot){

List<List<Integer>>res=newArrayList<>();

if(root==null)returnres;

Queue<TreeNode>queue=newLinkedList<>();

queue.offer(root);

while(!queue.isEmpty()){

//当前层节点个数

intlevelSize=queue.size();

List<Integer>levelList=newArrayList<>();

for(inti=0;i<levelSize;i++){

TreeNodenode=queue.poll();

levelList.add(node.val);

//左右子节点入队

if(node.left!=null)queue.offer(node.left);

if(node.right!=null)queue.offer(node.right);

}

res.add(levelList);

}

returnres;

}2.二叉树的最大深度题目:给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。解题思路递归核心思路:当前节点深度=左右子树最大深度+1。递归终止条件:节点为空时,深度为0。分别递归求左子树、右子树深度,取最大值即可。完整代码(Java)java

publicintmaxDepth(TreeNoderoot){

//空节点深度为0

if(root==null)return0;

//递归计算左右子树深度

intleftDepth=maxDepth(root.left);

intrightDepth=maxDepth(root.right);

//当前节点深度=子树最大深度+1

returnMath.max(leftDepth,rightDepth)+1;

}复杂度:时间O(n)(遍历所有节点),空间O(h)(h为树的高度,递归栈空间)。四、动态规划基础高频题1.爬楼梯题目:假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶?示例:n=3,输出3(1+1+1、1+2、2+1)解题思路经典一维DP问题。推导状态转移方程:爬到第n阶台阶的方法数,等于爬到n-1阶(再爬1步)+爬到n-2阶(再爬2步)的方法数。即dp[n]=dp[n-1]+dp[n-2]。初始化:dp[1]=1,dp[2]=2。可优化空间,无需数组,仅用两个变量迭代。完整代码(空间优化版)java

publicintclimbStairs(intn){

//边界条件

if(n<=2)returnn;

inta=1;//n-2阶

intb=2;//n-1阶

intres=0;

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

res=a+b;

a=b;

b=res;

}

returnres;

}面试点拨:优先写空间优化版本,面试官会关注对DP空间复杂度的优化意识。2.最大子数组和题目:给你一个整数数组nums,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。示例:nums=[-2,1,-3,4,-1,2,1,-5,4],输出6(子数组[4,-1,2,1])解题思路贪心+动态规划思路。遍历数组,维护当前子数组和,如果当前前缀和为负数,直接舍弃(负数叠加只会更小),从当前元素重新开始累加。同时全程记录遍历过程中的最大值。完整代码(Java)java

publicintmaxSubArray(int[]nums){

intmaxSum=nums[0];

intcurSum=0;

for(intnum:nums){

//当前和为负则重置,否则累加

curSum=Math.max(curSum+num,num);

//更新最大值

maxSum=Math.max(maxSum,curSum);

}

returnmaxSum;

}复杂度:时间O(n),空间O(1),最优解法。五、贪心算法面试题1.买卖股票的最佳时机题目:给定一个数组prices,它的第i个元素prices[i]表示一支给定股票第i天的价格。你只能选择某一天买入这只股票,并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论