常用算法面试题及详细答案(职场高频真题)_第1页
常用算法面试题及详细答案(职场高频真题)_第2页
常用算法面试题及详细答案(职场高频真题)_第3页
常用算法面试题及详细答案(职场高频真题)_第4页
常用算法面试题及详细答案(职场高频真题)_第5页
已阅读5页,还剩5页未读, 继续免费阅读

下载本文档

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

文档简介

常用算法面试题及详细答案(职场高频真题)本题库精选互联网、软件开发岗位面试高频算法题型,覆盖入门基础、数据结构、经典算法、实操场景题,适配初级、中级开发面试。所有题目均附带手写通俗解析、完整可运行代码及解题思路,摒弃模板化话术,贴合真实面试答题逻辑,无冗余内容,重点突出解题核心和得分要点。适用岗位:后端开发、前端开发、客户端开发、测试开发、数据分析开发岗语言说明:统一使用Python实现,语法简洁、可读性强,面试通用性极高一、基础数组算法(面试必考)1.两数之和(LeetCode1简单)题目描述:给定一个整数数组nums和一个整数目标值target,请你在该数组中找出和为目标值target的那两个整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案,数组中同一个元素在答案里不能重复出现。解题思路:最优解法使用哈希表(字典),一次遍历数组,遍历过程中记录已遍历元素的数值和下标。对于当前元素,计算需要匹配的目标差值,若差值存在于哈希表中,直接返回两个下标;不存在则将当前元素存入哈希表。时间复杂度O(n),空间复杂度O(n),优于双层循环的暴力解法。完整代码:python

deftwoSum(nums,target):

#定义哈希表,存储数值:下标

hash_map={}

forindex,numinenumerate(nums):

#计算需要匹配的数值

diff=target-num

ifdiffinhash_map:

#找到结果,返回两个下标

return[hash_map[diff],index]

#未找到则存入当前数值

hash_map[num]=index

#题目保证有唯一解,此处仅兜底

return[]

#测试案例

print(twoSum([2,7,11,15],9))#输出[0,1]面试加分点:主动说明暴力解法O(n²)的弊端,对比哈希表解法的优化逻辑,明确时间空间复杂度,面试中会大幅提升印象分。2.数组去重并保持原有顺序题目描述:给定一个无序整数数组,去除数组中重复元素,返回去重后的数组,要求保留元素第一次出现的顺序,禁止直接调用内置去重函数。解题思路:创建空列表存储结果,创建空集合记录已出现元素。遍历原数组,逐个判断元素是否已存在于集合中,不存在则加入结果列表和集合,存在则跳过。集合查询效率为O(1),整体时间复杂度O(n)。完整代码:python

defremoveDuplicates(nums):

res=[]

seen=set()

fornuminnums:

ifnumnotinseen:

seen.add(num)

res.append(num)

returnres

#测试案例

print(removeDuplicates([1,2,2,3,1,4,3]))#输出[1,2,3,4]3.寻找数组中最大值与最小值题目描述:不使用内置max、min函数,遍历数组找出最大值和最小值。解题思路:先处理空数组异常,再将数组第一个元素初始化为最大、最小值,后续遍历数组剩余元素,逐个对比更新最值,仅需一次遍历完成查找,效率最高。完整代码:python

defgetMaxMin(nums):

ifnotnums:

returnNone,None

max_num=min_num=nums[0]

fornuminnums[1:]:

ifnum>max_num:

max_num=num

elifnum<min_num:

min_num=num

returnmax_num,min_num

#测试案例

print(getMaxMin([5,2,9,1,5,6]))#输出(9,1)二、字符串经典算法(高频面试)1.反转字符串题目描述:输入一个字符串,返回反转后的字符串,禁止使用切片反转、内置反转函数。解题思路:利用双指针法,定义左指针指向字符串头部,右指针指向尾部,两端字符交换位置,指针向中间靠拢,直至指针相遇,完成反转。空间复杂度O(1),原地修改效率高。完整代码:python

defreverseString(s):

#字符串转列表,字符串不可变,列表可修改

s_list=list(s)

left,right=0,len(s_list)-1

whileleft<right:

#交换左右指针元素

s_list[left],s_list[right]=s_list[right],s_list[left]

left+=1

right-=1

return''.join(s_list)

#测试案例

print(reverseString("hello"))#输出"olleh"2.判断回文字符串题目描述:给定一个字符串,判断该字符串是否为回文字符串(正读和反读完全一致),忽略大小写、空格和标点符号。解题思路:先对字符串预处理,统一转为小写,过滤非字母数字字符;再通过双指针法首尾对比,全部匹配则为回文,否则不是。完整代码:python

defisPalindrome(s):

#预处理:过滤有效字符并转小写

new_s=''

forcharins:

ifchar.isalnum():

new_s+=char.lower()

#双指针判断

left,right=0,len(new_s)-1

whileleft<right:

ifnew_s[left]!=new_s[right]:

returnFalse

left+=1

right-=1

returnTrue

#测试案例

print(isPalindrome("Aman,aplan,acanal:Panama"))#输出True

print(isPalindrome("raceacar"))#输出False3.统计字符串中字符出现次数题目描述:输入一串字符串,统计每个字符的出现次数,返回统计结果,区分大小写。解题思路:使用字典存储字符和对应次数,遍历字符串,字符首次出现则赋值为1,重复出现则次数加1,最终返回字典。完整代码:python

defcountChar(s):

count_dict={}

forcharins:

ifcharincount_dict:

count_dict[char]+=1

else:

count_dict[char]=1

returncount_dict

#测试案例

print(countChar("abracadabra"))#输出{'a':5,'b':2,'r':2,'c':1,'d':1}三、链表基础算法(后端/客户端必考)1.反转单链表(最经典面试题)题目描述:给定一个单链表的头节点,反转该链表,返回反转后的链表头节点。解题思路:迭代法,定义前驱节点、当前节点,遍历链表,逐个修改节点指向,让当前节点指向前驱节点,完成链表反转。时间O(n),空间O(1),是面试最优解法。完整代码:python

#定义链表节点

classListNode:

def__init__(self,val=0,next=None):

self.val=val

self.next=next

defreverseList(head):

pre=None#前驱节点

cur=head#当前节点

whilecur:

#保存后续节点

temp=cur.next

#反转指向

cur.next=pre

#指针后移

pre=cur

cur=temp

#pre为新的头节点

returnpre面试重点:面试官常追问递归解法,迭代法空间复杂度更低,工程中优先使用。2.判断链表是否有环题目描述:给定一个链表,判断链表中是否存在环,存在返回True,不存在返回False。解题思路:快慢指针法(龟兔赛跑),慢指针每次走1步,快指针每次走2步。若无环,快指针会先走到末尾;若有环,快慢指针最终一定会相遇。完整代码:python

defhasCycle(head):

slow=fast=head

whilefastandfast.next:

slow=slow.next

fast=fast.next.next

ifslow==fast:

returnTrue

returnFalse四、排序算法(原理+手写代码,面试高频问答)1.冒泡排序算法原理:重复遍历数组,相邻两个元素两两对比,顺序错误则交换位置,每一轮遍历都会将当前最大值冒泡到数组末尾,经过n-1轮完成排序。时间复杂度O(n²),空间O(1),稳定排序。手写代码:python

defbubbleSort(nums):

n=len(nums)

foriinrange(n-1):

#标记是否发生交换,优化有序数组

flag=False

forjinrange(n-1-i):

ifnums[j]>nums[j+1]:

nums[j],nums[j+1]=nums[j+1],nums[j]

flag=True

ifnotflag:

break

returnnums

#测试

print(bubbleSort([3,1,4,2,5]))#输出[1,2,3,4,5]2.快速排序(面试重点)算法原理:分治思想,选取一个基准值,将数组分为左右两部分,左侧元素全部小于基准值,右侧全部大于基准值,再递归排序左右子数组。平均时间复杂度O(nlogn),空间O(logn),不稳定排序,实际工程排序效率最高。手写代码:python

defquickSort(nums):

iflen(nums)<=1:

returnnums

#选取基准值

pivot=nums[len(nums)//2]

left=[xforxinnumsifx<pivot]

mid=[xforxinnumsifx==pivot]

right=[xforxinnumsifx>pivot]

#递归拼接

returnquickSort(left)+mid+quickSort(right)

#测试

print(quickSort([5,3,8,6,2,9]))#输出[2,3,5,6,8,9]五、动态规划基础(入门高频题)1.斐波那契数列题目描述:求斐波那契数列第n项,数列规则:F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)。禁止纯递归暴力解法(超时严重)。解题思路:动态规划迭代解法,用两个变量保存前两项结果,逐步递推,时间O(n),空间O(1),优化递归的重复计算问题。完整代码:python

deffib(n):

ifn==0:

return0

elifn==1:

return1

a,b=0,1

for_inrange(2,n+1):

a,b=b,a+b

returnb

#测试

print(fib(10))#输出552.爬楼梯问题题目描述:假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶?解题思路:动态规划经典题型,递推公式:dp[n]=dp[n-1]+dp[n-2]。到达第n阶的方法数=到达n-1阶(再爬1步)+到达n-2阶(再爬2步)。完整代码:python

defclimbStairs(n):

ifn<=2:

returnn

dp=[0]*(n+1)

dp[1]=1

dp[2]=2

foriinrange(3,n+1):

dp[i]=dp[i-1]+dp[i-2]

returndp[n]

#测试

print(climbStairs(5))#输出8六、经典场景算法题(面试实操高频)1.找出数组中重复的数字题目描述:给定一个长度为n的数组,数组元素取值范围0~n-1,数组中存在重复数字,找出任意一个重复的数字。解题思路:利用数组下标与数值的对应关系,遍历数组,将数值放到对应下标位置,若该位置已有相同数值,即为重复数字。时间O(n),空间O(1)。完整代码:python

deffindRepeatNumber(nums):

foriinrange(len(nums)):

#当前数值与下标不匹配,持续交换

whilenums[i]!=i:

ifnums[nums[i]]==nums[i]:

#找到重复值

returnnums[i]

#交换数值到对应下标位置

nums[nums[i]],nums[i]=nums[i],nums[nums[i]]

return-1

#测试

print(findRepeatNumber([2,3,1,0,2,5,3]))#输出2

温馨提示

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

最新文档

评论

0/150

提交评论