程序员面试算法题解析大全

2026年程序员面试算法题解析大全字符串处理类题目（共5题，每题10分）题目1（10分）题目：给定两个字符串s和t，判断t是否是s的子序列。可以假设两个字符串均由小写字母组成。你可以假设s和t的最大长度分别为1000和100。示例：输入：s="abc",t="ahbgdc"输出：true解析：这个问题可以使用双指针的方法来解决。具体思路是使用两个指针分别遍历两个字符串，如果s中的字符在t中也存在，则两个指针都向后移动，否则只移动s的指针。如果s的指针能够遍历完整个s，则说明t是s的子序列。答案：pythondefisSubsequence(s:str,t:str)->bool:m,n=len(s),len(t)i,j=0,0whilei<mandj<n:ifs[i]==t[j]:i+=1j+=1returni==m题目2（10分）题目：字符串转换整数（atoi）。请你实现一个atoi函数，将字符串转换成整数。首先，你需要根据下面的规则去除字符串的前导空格。之后，你需要根据下面的规则判断如何处理接下来的字符：1.如果第一个非空字符不是一个数字，则返回0。2.如果第一个非空字符是正号或负号，则将它的符号与后面尽可能多的连续数字相乘。这就意味着，如果第一个非空字符是负号或正号，则它后面的所有连续数字都将乘以-1或+1。3.字符串中后续出现的任何非数字字符都将被忽略。你可以假设给定的字符串只包含空格字符、数字字符和正号或负号。示例：输入："-42"输出：-42解析：这个问题需要按照规定的步骤进行处理。首先去除前导空格，然后判断第一个字符是否为正负号，接着遍历字符串中的数字字符，并转换为整数。需要注意处理数字溢出的问题。答案：pythondefmyAtoi(s:str)->int:s=s.strip()ifnots:return0sign=1i=0ifs[0]=='-':sign=-1i=1elifs[0]=='+':i=1num=0whilei<len(s)ands[i].isdigit():num=num10+int(s[i])i+=1num=signnum=max(min(num,231-1),-231)returnnum题目3（10分）题目：给定一个字符串，请你找出其中不含有重复字符的长度最长的子串。例如，给定"abcabcbb"，最长无重复字符的子串是"abc"，长度为3。示例：输入："abcabcbb"输出：3解析：这个问题可以使用滑动窗口的方法来解决。具体思路是使用两个指针表示窗口的左右边界，通过移动右指针扩展窗口，如果遇到重复字符则移动左指针缩小窗口。记录过程中窗口的最大长度。答案：pythondeflengthOfLongestSubstring(s:str)->int:char_set=set()left=0max_length=0forrightinrange(len(s)):whiles[right]inchar_set:char_set.remove(s[left])left+=1char_set.add(s[right])max_length=max(max_length,right-left+1)returnmax_length题目4（10分）题目：将一个字符串转换成一个整数，这个整数表示字符串所表示的数值。你可以假定字符串中可能存在正负号，并且忽略开头和结尾的空格。如果字符串的数值超过32位整数的范围，则返回INT_MAX（2147483647）或INT_MIN（-2147483648），取决于该数值的正负。示例：输入："-42"输出：-42解析：这个问题与题目2类似，但需要处理更多的边界情况，例如字符串开头或结尾的空格，以及数值的溢出问题。处理步骤包括去除空格、判断正负号、遍历数字字符并转换为整数，最后处理溢出。答案：pythondefstrToInt(s:str)->int:s=s.strip()ifnots:return0sign=1i=0ifs[0]=='-':sign=-1i=1elifs[0]=='+':i=1num=0whilei<len(s)ands[i].isdigit():num=num10+int(s[i])i+=1num=signnum=max(min(num,2147483647),-2147483648)returnnum题目5（10分）题目：给定一个字符串s，找到其中最长的回文子串。可以假设s的最大长度为1000。示例：输入："babad"输出："bab"或"aba"解析：这个问题可以使用动态规划的方法来解决。具体思路是创建一个二维数组dp，其中dp[i][j]表示字符串从i到j的子串是否为回文。通过动态规划填充这个数组，并记录最长回文子串的起始位置和长度。答案：pythondeflongestPalindrome(s:str)->str:n=len(s)ifn==0:return""dp=[[False]nfor_inrange(n)]start,max_length=0,1foriinrange(n):dp[i][i]=Trueforiinrange(n-1):ifs[i]==s[i+1]:dp[i][i+1]=Truestart=imax_length=2forlengthinrange(3,n+1):foriinrange(n-length+1):j=i+length-1ifs[i]==s[j]anddp[i+1][j-1]:dp[i][j]=Truestart=imax_length=lengthreturns[start:start+max_length]数组处理类题目（共5题，每题10分）题目6（10分）题目：给定一个整数数组nums，返回所有可能的子集（幂集）。解集不能包含重复的子集。示例：输入：nums=[1,2,3]输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]解析：这个问题可以使用回溯算法来解决。具体思路是使用递归函数遍历所有可能的子集，每次选择是否包含当前元素，然后递归处理下一个元素。答案：pythondefsubsets(nums):res=[]subset=[]defbacktrack(index):res.append(subset.copy())foriinrange(index,len(nums)):subset.append(nums[i])backtrack(i+1)subset.pop()backtrack(0)returnres题目7（10分）题目：给定一个包含n个整数的数组nums，判断这个数组中是否存在三个元素a,b,c，使得a+b+c=0？请找出所有满足条件且不重复的三元组。示例：输入：nums=[-1,0,1,2,-1,-4]输出：[[-1,-1,2],[-1,0,1]]解析：这个问题可以使用排序加双指针的方法来解决。具体思路是首先对数组进行排序，然后使用固定指针遍历数组，对于每个固定指针，使用双指针在剩余部分查找和为0的三元组。答案：pythondefthreeSum(nums):nums.sort()res=[]n=len(nums)foriinrange(n):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal==0:res.append([nums[i],nums[left],nums[right]])whileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1eliftotal<0:left+=1else:right-=1returnres题目8（10分）题目：给定一个包含n个整数的数组nums，返回所有可能的三元组使得它们的和最接近给定的目标值target。假设每个输入都只有一个解。示例：输入：nums=[-1,2,1,-4],target=1输出：[-1,2,1]解析：这个问题与题目7类似，但需要找到和最接近目标值的三元组。具体思路是首先对数组进行排序，然后使用固定指针遍历数组，对于每个固定指针，使用双指针在剩余部分查找和最接近目标值的三元组。答案：pythondefthreeSumClosest(nums,target):nums.sort()n=len(nums)closest_sum=float('inf')foriinrange(n):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-1whileleft<right:total=nums[i]+nums[left]+nums[right]ifabs(total-target)<abs(closest_sum-target):closest_sum=totaliftotal<target:left+=1eliftotal>target:right-=1else:returntotalreturnclosest_sum题目9（10分）题目：给定一个包含n个整数的数组nums，判断这个数组中是否存在四个元素a,b,c,d，使得a+b+c+d=target？找出所有满足条件且不重复的四元组。示例：输入：nums=[1,0,-1,0,-2,2],target=0输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]解析：这个问题是题目7的扩展，需要找到四个元素的和为target的四元组。具体思路是首先对数组进行排序，然后使用两个固定指针遍历数组，对于每个固定指针，使用双指针在剩余部分查找和为target的四元组。答案：pythondeffourSum(nums,target):nums.sort()res=[]n=len(nums)foriinrange(n):ifi>0andnums[i]==nums[i-1]:continueforjinrange(i+1,n):ifj>i+1andnums[j]==nums[j-1]:continueleft,right=j+1,n-1whileleft<right:total=nums[i]+nums[j]+nums[left]+nums[right]iftotal==target:res.append([nums[i],nums[j],nums[left],nums[right]])whileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1eliftotal<target:left+=1else:right-=1returnres题目10（10分）题目：给定一个包含n个整数的数组nums，返回所有可能的两数之和等于给定目标值target的数对。解集不能包含重复的数对。示例：输入：nums=[1,2,3,4,5],target=7输出：[[1,6],[2,5],[3,4]]解析：这个问题可以使用哈希表的方法来解决。具体思路是使用哈希表记录每个数字及其索引，然后遍历数组，对于每个数字，检查target减去该数字的值是否已经在哈希表中，如果在，则找到一个数对。答案：pythondeftwoSum(nums,target):num_to_index={}res=[]fori,numinenumerate(nums):complement=target-numifcomplementinnum_to_index:res.append([complement,num])num_to_index[num]=ireturnres树和图类题目（共5题，每题10分）题目11（10分）题目：给定一个二叉搜索树（BST），找出其中值大于等于root.val的最小值节点。示例：输入：root=[5,3,6,2,4,null,7]输出：4解析：这个问题可以利用二叉搜索树的特点来解决。具体思路是如果当前节点的值大于等于root.val，则记录当前节点，并继续在左子树中查找；否则，在右子树中查找。答案：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefminNode(root,target):current=rootmin_val=float('inf')whilecurrent:ifcurrent.val>=target:min_val=min(min_val,current.val)current=current.leftelse:current=current.rightreturnmin_val题目12（10分）题目：给定一个二叉树的根节点root，返回它的最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。示例：输入：root=[3,9,20,null,null,15,7]输出：3解析：这个问题可以使用递归的方法来解决。具体思路是递归计算左子树和右子树的最大深度，然后取较大值加1作为当前节点的深度。答案：pythondefmaxDepth(root):ifnotroot:return0left_depth=maxDepth(root.left)right_depth=maxDepth(root.right)returnmax(left_depth,right_depth)+1题目13（10分）题目：给定一个二叉树，判断它是否是高度平衡的二叉树。对于每个节点，其左右子树的高度差不超过1。示例：输入：root=[3,9,20,null,null,15,7]输出：true解析：这个问题可以使用递归的方法来解决。具体思路是递归计算左右子树的高度，如果高度差超过1，则不是高度平衡的二叉树；否则，继续递归检查左右子树。答案：pythondefisBalanced(root):defcheck(node):ifnotnode:return0,Trueleft_height,left_balanced=check(node.left)right_height,right_balanced=check(node.right)balanced=left_balancedandright_balancedandabs(left_height-right_height)<=1returnmax(left_height,right_height)+1,balancedreturncheck(root)[1]题目14（10分）题目：给定一个二叉树，返回它的中序遍历。例如，给定二叉树[1,null,2,3]，返回[1,3,2]。示例：输入：root=[1,null,2,3]输出：[1,3,2]解析：这个问题可以使用递归或迭代的方法来解决。具体思路是先遍历左子树，然后访问根节点，最后遍历右子树。答案：pythondefinorderTraversal(root):res=[]definorder(node):ifnode:inorder(node.left)res.append(node.val)inorder(node.right)inorder(root)returnres题目15（10分）题目：给定一个无向图，判断它是否是二分图。一个二分图是将图分成两个独立的集合U和V，使得所有的边都只连接U中的一个顶点和V中的一个顶点。示例：输入：graph=[[1,3],[0,2],[1,3],[0,2]]输出：true解析：这个问题可以使用图的染色方法来解决。具体思路是使用两种颜色对图进行染色，如果能够成功染色，则图是二分图；否则，不是。答案：pythondefisBipartite(graph):color={}defdfs(node,c):ifnodeincolor:returncolor[node]==ccolor[node]=creturnall(dfs(nei,notc)forneiingraph[node])fornodeinrange(len(graph)):ifnodenotincolor:ifnotdfs(node,True):returnFalsereturnTrue动态规划类题目（共5题，每题10分）题目16（10分）题目：给定一个非负整数数组nums，返回一个数组answer，其中answer[i]等于nums中除nums[i]之外其他数字的乘积。示例：输入：nums=[1,2,3,4]输出：[24,12,8,6]解析：这个问题可以使用动态规划的方法来解决。具体思路是首先计算每个元素左边所有元素的乘积，然后计算每个元素右边所有元素的乘积，最后将左边和右边的乘积相乘得到结果。答案：pythondefproductExceptSelf(nums):n=len(nums)left=[1]nright=[1]nanswer=[1]nforiinrange(1,n):left[i]=left[i-1]nums[i-1]foriinrange(n-2,-1,-1):right[i]=right[i+1]nums[i+1]foriinrange(n):answer[i]=left[i]right[i]returnanswer题目17（10分）题目：给定一个字符串s和一个整数k，返回s中长度为k的无重复字符的最长子串的长度。示例：输入：s="abcabcbb",k=3输出：3解析：这个问题可以使用滑动窗口的方法来解决。具体思路是使用两个指针表示窗口的左右边界，通过移动右指针扩展窗口，如果窗口中的字符数量超过k，则移动左指针缩小窗口。记录过程中窗口的最大长度。答案：pythondeflengthOfLongestSubstringKDist(s,k):ifk==0:return0char_map={}left=0max_length=0distinct=0forrightinrange(len(s)):ifs[right]inchar_map:char_map[s[right]]+=1else:char_map[s[right]]=1distinct+=1whiledistinct>k:char_map[s[left]]-=1ifchar_map[s[left]]==0:distinct-=1left+=1max_length=max(max_length,right-left+1)returnmax_length题目18（10分）题目：给定一个字符串s和一个整数k，返回s中长度为k的无重复字符的最长子串的长度。示例：输入：s="abcabcbb",k=3输出：3解析：这个问题与题目17类似，但需要找到长度为k的无重复字符的最长子串。具体思路是使用滑动窗口的方法，确保窗口中的字符数量不超过k，并记录窗口的最大长度。答案：pythondeflengthOfLongestSubstringKDist(s,k):ifk==0:return0char_map={}left=0max_length=0distinct=0forrightinrange(len(s)):ifs[right]inchar_map:char_map[s[right]]+=1else:char_map[s[right]]=1distinct+=1whiledistinct>k:char_map[s[left]]-=1ifchar_map[s[left]]==0:distinct-=1left+=1max_length=max(max_length,right-left+1)returnmax_length题目19（10