2026年程序員面試算法題解析大全字符串處理類題目（共5題，每題10分）題目1（10分）題目：給定兩個字符串s和t，判斷t是否是s的子序列?？梢约僭O(shè)兩個字符串均由小寫字母組成。你可以假設(shè)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分）題目：字符串轉(zhuǎn)換整數(shù)（atoi）。請你實現(xiàn)一個atoi函數(shù)，將字符串轉(zhuǎn)換成整數(shù)。首先，你需要根據(jù)下面的規(guī)則去除字符串的前導(dǎo)空格。之后，你需要根據(jù)下面的規(guī)則判斷如何處理接下來的字符：1.如果第一個非空字符不是一個數(shù)字，則返回0。2.如果第一個非空字符是正號或負(fù)號，則將它的符號與后面盡可能多的連續(xù)數(shù)字相乘。這就意味著，如果第一個非空字符是負(fù)號或正號，則它后面的所有連續(xù)數(shù)字都將乘以-1或+1。3.字符串中后續(xù)出現(xiàn)的任何非數(shù)字字符都將被忽略。你可以假設(shè)給定的字符串只包含空格字符、數(shù)字字符和正號或負(fù)號。示例：輸入："-42"輸出：-42解析：這個問題需要按照規(guī)定的步驟進行處理。首先去除前導(dǎo)空格，然后判斷第一個字符是否為正負(fù)號，接著遍歷字符串中的數(shù)字字符，并轉(zhuǎn)換為整數(shù)。需要注意處理數(shù)字溢出的問題。答案：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分）題目：給定一個字符串，請你找出其中不含有重復(fù)字符的長度最長的子串。例如，給定"abcabcbb"，最長無重復(fù)字符的子串是"abc"，長度為3。示例：輸入："abcabcbb"輸出：3解析：這個問題可以使用滑動窗口的方法來解決。具體思路是使用兩個指針表示窗口的左右邊界，通過移動右指針擴展窗口，如果遇到重復(fù)字符則移動左指針縮小窗口。記錄過程中窗口的最大長度。答案：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分）題目：將一個字符串轉(zhuǎn)換成一個整數(shù)，這個整數(shù)表示字符串所表示的數(shù)值。你可以假定字符串中可能存在正負(fù)號，并且忽略開頭和結(jié)尾的空格。如果字符串的數(shù)值超過32位整數(shù)的范圍，則返回INT_MAX（2147483647）或INT_MIN（-2147483648），取決于該數(shù)值的正負(fù)。示例：輸入："-42"輸出：-42解析：這個問題與題目2類似，但需要處理更多的邊界情況，例如字符串開頭或結(jié)尾的空格，以及數(shù)值的溢出問題。處理步驟包括去除空格、判斷正負(fù)號、遍歷數(shù)字字符并轉(zhuǎn)換為整數(shù)，最后處理溢出。答案：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，找到其中最長的回文子串?？梢约僭O(shè)s的最大長度為1000。示例：輸入："babad"輸出："bab"或"aba"解析：這個問題可以使用動態(tài)規(guī)劃的方法來解決。具體思路是創(chuàng)建一個二維數(shù)組dp，其中dp[i][j]表示字符串從i到j(luò)的子串是否為回文。通過動態(tài)規(guī)劃填充這個數(shù)組，并記錄最長回文子串的起始位置和長度。答案：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]數(shù)組處理類題目（共5題，每題10分）題目6（10分）題目：給定一個整數(shù)數(shù)組nums，返回所有可能的子集（冪集）。解集不能包含重復(fù)的子集。示例：輸入：nums=[1,2,3]輸出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]解析：這個問題可以使用回溯算法來解決。具體思路是使用遞歸函數(shù)遍歷所有可能的子集，每次選擇是否包含當(dāng)前元素，然后遞歸處理下一個元素。答案：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個整數(shù)的數(shù)組nums，判斷這個數(shù)組中是否存在三個元素a,b,c，使得a+b+c=0？請找出所有滿足條件且不重復(fù)的三元組。示例：輸入：nums=[-1,0,1,2,-1,-4]輸出：[[-1,-1,2],[-1,0,1]]解析：這個問題可以使用排序加雙指針的方法來解決。具體思路是首先對數(shù)組進行排序，然后使用固定指針遍歷數(shù)組，對于每個固定指針，使用雙指針在剩余部分查找和為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個整數(shù)的數(shù)組nums，返回所有可能的三元組使得它們的和最接近給定的目標(biāo)值target。假設(shè)每個輸入都只有一個解。示例：輸入：nums=[-1,2,1,-4],target=1輸出：[-1,2,1]解析：這個問題與題目7類似，但需要找到和最接近目標(biāo)值的三元組。具體思路是首先對數(shù)組進行排序，然后使用固定指針遍歷數(shù)組，對于每個固定指針，使用雙指針在剩余部分查找和最接近目標(biāo)值的三元組。答案：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個整數(shù)的數(shù)組nums，判斷這個數(shù)組中是否存在四個元素a,b,c,d，使得a+b+c+d=target？找出所有滿足條件且不重復(fù)的四元組。示例：輸入：nums=[1,0,-1,0,-2,2],target=0輸出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]解析：這個問題是題目7的擴展，需要找到四個元素的和為target的四元組。具體思路是首先對數(shù)組進行排序，然后使用兩個固定指針遍歷數(shù)組，對于每個固定指針，使用雙指針在剩余部分查找和為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個整數(shù)的數(shù)組nums，返回所有可能的兩數(shù)之和等于給定目標(biāo)值target的數(shù)對。解集不能包含重復(fù)的數(shù)對。示例：輸入：nums=[1,2,3,4,5],target=7輸出：[[1,6],[2,5],[3,4]]解析：這個問題可以使用哈希表的方法來解決。具體思路是使用哈希表記錄每個數(shù)字及其索引，然后遍歷數(shù)組，對于每個數(shù)字，檢查target減去該數(shù)字的值是否已經(jīng)在哈希表中，如果在，則找到一個數(shù)對。答案：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的最小值節(jié)點。示例：輸入：root=[5,3,6,2,4,null,7]輸出：4解析：這個問題可以利用二叉搜索樹的特點來解決。具體思路是如果當(dāng)前節(jié)點的值大于等于root.val，則記錄當(dāng)前節(jié)點，并繼續(xù)在左子樹中查找；否則，在右子樹中查找。答案：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分）題目：給定一個二叉樹的根節(jié)點root，返回它的最大深度。二叉樹的深度為根節(jié)點到最遠葉子節(jié)點的最長路徑上的節(jié)點數(shù)。示例：輸入：root=[3,9,20,null,null,15,7]輸出：3解析：這個問題可以使用遞歸的方法來解決。具體思路是遞歸計算左子樹和右子樹的最大深度，然后取較大值加1作為當(dāng)前節(jié)點的深度。答案：pythondefmaxDepth(root):ifnotroot:return0left_depth=maxDepth(root.left)right_depth=maxDepth(root.right)returnmax(left_depth,right_depth)+1題目13（10分）題目：給定一個二叉樹，判斷它是否是高度平衡的二叉樹。對于每個節(jié)點，其左右子樹的高度差不超過1。示例：輸入：root=[3,9,20,null,null,15,7]輸出：true解析：這個問題可以使用遞歸的方法來解決。具體思路是遞歸計算左右子樹的高度，如果高度差超過1，則不是高度平衡的二叉樹；否則，繼續(xù)遞歸檢查左右子樹。答案：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]解析：這個問題可以使用遞歸或迭代的方法來解決。具體思路是先遍歷左子樹，然后訪問根節(jié)點，最后遍歷右子樹。答案：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動態(tài)規(guī)劃類題目（共5題，每題10分）題目16（10分）題目：給定一個非負(fù)整數(shù)數(shù)組nums，返回一個數(shù)組answer，其中answer[i]等于nums中除nums[i]之外其他數(shù)字的乘積。示例：輸入：nums=[1,2,3,4]輸出：[24,12,8,6]解析：這個問題可以使用動態(tài)規(guī)劃的方法來解決。具體思路是首先計算每個元素左邊所有元素的乘積，然后計算每個元素右邊所有元素的乘積，最后將左邊和右邊的乘積相乘得到結(jié)果。答案：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和一個整數(shù)k，返回s中長度為k的無重復(fù)字符的最長子串的長度。示例：輸入：s="abcabcbb",k=3輸出：3解析：這個問題可以使用滑動窗口的方法來解決。具體思路是使用兩個指針表示窗口的左右邊界，通過移動右指針擴展窗口，如果窗口中的字符數(shù)量超過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和一個整數(shù)k，返回s中長度為k的無重復(fù)字符的最長子串的長度。示例：輸入：s="abcabcbb",k=3輸出：3解析：這個問題與題目17類似，但需要找到長度為k的無重復(fù)字符的最長子串。具體思路是使用滑動窗口的方法，確保窗口中的字符數(shù)量不超過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