2026年程序員面試中常見的算法問題解析一、數(shù)組與字符串問題（共5題，每題8分）1.題目：給定一個包含重復(fù)數(shù)字的數(shù)組，返回所有不重復(fù)的全排列。例如，輸入`[1,1,2]`，輸出`[[1,1,2],[1,2,1],[2,1,1]]`。要求：不能使用庫函數(shù)，時間復(fù)雜度盡可能低。2.題目：實現(xiàn)一個函數(shù)，判斷一個字符串是否是另一個字符串的子串，忽略大小寫。例如，`isSubstring("Hello","lo")`返回`true`。要求：不能使用庫函數(shù)，空間復(fù)雜度O(1)。3.題目：給定一個字符串，找到所有唯一字符的最長子串長度。例如，`"abcabcbb"`的最長無重復(fù)字符子串是`"abc"`，返回`3`。要求：時間復(fù)雜度O(n)，空間復(fù)雜度O(1)。4.題目：實現(xiàn)一個函數(shù)，將字符串中的每個字母移動到下一個字母（'z'變?yōu)?a'），其他字符不變。例如，`nextLetter("abcz")`返回`"bcda"`。要求：不能使用庫函數(shù)，時間復(fù)雜度O(n)。5.題目：給定一個包含字母和數(shù)字的字符串，統(tǒng)計每個字母出現(xiàn)的次數(shù)，并按字母順序排序。例如，`"aabbc"`返回`{'a':2,'b':2,'c':1}`。要求：不能使用庫函數(shù)，時間復(fù)雜度O(nlogn)。二、鏈表問題（共4題，每題10分）1.題目：實現(xiàn)一個鏈表，包含頭節(jié)點，支持`addFirst`和`addLast`操作。要求：時間復(fù)雜度O(1)，空間復(fù)雜度O(1)。2.題目：刪除鏈表的倒數(shù)第n個節(jié)點。例如，給定鏈表`1->2->3->4->5`和`n=2`，返回`1->2->3->5`。要求：不能使用額外空間，時間復(fù)雜度O(n)。3.題目：判斷鏈表是否存在環(huán)，并返回環(huán)的入口節(jié)點。例如，`1->2->3->2`存在環(huán)，返回`2`。要求：不能使用額外空間，時間復(fù)雜度O(n)。4.題目：合并兩個有序鏈表，返回合并后的有序鏈表。例如，`1->3->5`和`2->4->6`，返回`1->2->3->4->5->6`。要求：時間復(fù)雜度O(n)，空間復(fù)雜度O(1)。三、棧與隊列問題（共3題，每題9分）1.題目：用棧實現(xiàn)隊列。即支持`enqueue`和`dequeue`操作。要求：時間復(fù)雜度O(1)，空間復(fù)雜度O(n)。2.題目：用隊列實現(xiàn)棧。即支持`push`和`pop`操作。要求：時間復(fù)雜度O(1)，空間復(fù)雜度O(n)。3.題目：給定一個表達(dá)式，用兩個棧判斷括號是否匹配。例如，`"(()())"`返回`true`，`"(()"`返回`false`。要求：不能使用庫函數(shù)，時間復(fù)雜度O(n)。四、樹與圖問題（共4題，每題10分）1.題目：二叉樹的最大深度。例如，`[3,9,20,null,null,15,7]`的最大深度是`3`。要求：遞歸或迭代均可，時間復(fù)雜度O(n)。2.題目：二叉樹的層序遍歷。例如，`[3,9,20,null,null,15,7]`的層序遍歷是`[3,9,20,15,7]`。要求：使用隊列，時間復(fù)雜度O(n)。3.題目：給定一個無向圖，判斷是否存在環(huán)。例如，`[[1,2],[2,3],[3,4],[4,2]]`存在環(huán)。要求：使用深度優(yōu)先搜索，時間復(fù)雜度O(n)。4.題目：二叉搜索樹的最小深度。例如，`[2,2,5,null,null,5,null,4]`的最小深度是`2`。要求：遞歸或迭代均可，時間復(fù)雜度O(n)。五、動態(tài)規(guī)劃問題（共3題，每題12分）1.題目：給定一個整數(shù)數(shù)組，返回連續(xù)子數(shù)組的最大和。例如，`[-2,1,-3,4,-1,2,1,-5,4]`的最大和是`6`（`[4,-1,2,1]`）。要求：時間復(fù)雜度O(n)，空間復(fù)雜度O(1)。2.題目：爬樓梯問題。給定`n`階樓梯，每次可以爬1或2階，返回爬到頂部的方案數(shù)。例如，`n=3`的方案數(shù)是`3`。要求：動態(tài)規(guī)劃，時間復(fù)雜度O(n)，空間復(fù)雜度O(1)。3.題目：最長公共子序列。給定兩個字符串，返回它們的最長公共子序列。例如，`"abcde"`和`"ace"`的最長公共子序列是`"ace"`。要求：動態(tài)規(guī)劃，時間復(fù)雜度O(mn)，空間復(fù)雜度O(mn)。六、貪心算法問題（共3題，每題12分）1.題目：給定一個非負(fù)數(shù)組，每個元素代表爬樓梯的步數(shù)，返回最少需要多少步可以爬到頂部。例如，`[2,3,1,1,4]`的最少步數(shù)是`2`（`1->2`或`1->1->2`）。要求：貪心算法，時間復(fù)雜度O(n)，空間復(fù)雜度O(1)。2.題目：區(qū)間調(diào)度問題。給定若干區(qū)間，選擇最多不重疊的區(qū)間。例如，`[[1,3],[2,4],[3,5]]`可以選擇`[1,3]`和`[3,5]`。要求：貪心算法，時間復(fù)雜度O(nlogn)。3.題目：分?jǐn)?shù)背包問題。給定若干物品，每個物品有價值和重量，背包容量為`W`，返回最大總價值。例如，`[[60,10],[100,20],[120,30]]`，`W=50`，最大價值是`180`（選擇`60`和`120`）。要求：貪心算法，時間復(fù)雜度O(nlogn)。七、數(shù)學(xué)與位運算問題（共3題，每題9分）1.題目：判斷一個數(shù)是否是2的冪。例如，`4`是，`5`不是。要求：不能使用庫函數(shù)，時間復(fù)雜度O(1)。2.題目：給定一個數(shù)`n`，計算`n!`的末尾有多少個0。例如，`10!`的末尾有`2`個0。要求：時間復(fù)雜度O(logn)。3.題目：交換兩個數(shù)的值，不能使用臨時變量。例如，`a=5`，`b=10`，交換后`a=10`，`b=5`。要求：位運算，時間復(fù)雜度O(1)。答案與解析一、數(shù)組與字符串問題1.全排列：思路：回溯法。使用哈希集合記錄已使用的數(shù)字，避免重復(fù)。代碼：pythondefpermuteUnique(nums):res=[]used=[False]len(nums)defbacktrack(path):iflen(path)==len(nums):res.append(path.copy())returnforiinrange(len(nums)):ifused[i]:continueifi>0andnums[i]==nums[i-1]andnotused[i-1]:continueused[i]=Truepath.append(nums[i])backtrack(path)path.pop()used[i]=Falsenums.sort()backtrack([])returnres2.判斷子串：思路：滑動窗口。忽略大小寫后比較。代碼：pythondefisSubstring(s1,s2):s1,s2=s1.lower(),s2.lower()iflen(s2)>len(s1):returnFalseforiinrange(len(s1)-len(s2)+1):ifs1[i:i+len(s2)]==s2:returnTruereturnFalse3.最長無重復(fù)子串：思路：滑動窗口。使用哈希集合記錄字符，移動右指針。代碼：pythondeflengthOfLongestSubstring(s):char_set=set()left=0max_len=0forrightinrange(len(s)):whiles[right]inchar_set:char_set.remove(s[left])left+=1char_set.add(s[right])max_len=max(max_len,right-left+1)returnmax_len4.字母移動：思路：遍歷字符串，將字母轉(zhuǎn)換為下一個字母。代碼：pythondefnextLetter(s):res=[]forcins:if'a'<=c<='z':res.append(chr(ord(c)+1)ifc!='z'else'a')elif'A'<=c<='Z':res.append(chr(ord(c)+1)ifc!='Z'else'A')else:res.append(c)return''.join(res)5.字母統(tǒng)計排序：思路：遍歷字符串統(tǒng)計字母，排序后返回字典。代碼：pythondefletterCount(s):count={}forcins:ifc.isalpha():count[c]=count.get(c,0)+1sorted_count=dict(sorted(count.items()))returnsorted_count二、鏈表問題1.鏈表操作：思路：使用頭尾指針。代碼：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextclassMyLinkedList:def__init__(self):self.head=ListNode(0)self.tail=self.headdefaddFirst(self,val):node=ListNode(val)node.next=self.head.nextself.head.next=nodeifself.tail==self.head:self.tail=nodedefaddLast(self,val):node=ListNode(val)self.tail.next=nodeself.tail=node2.刪除倒數(shù)第n個節(jié)點：思路：快慢指針。代碼：pythondefremoveNthFromEnd(head,n):dummy=ListNode(0,head)fast=slow=dummyfor_inrange(n+1):fast=fast.nextwhilefast:fast=fast.nextslow=slow.nextslow.next=slow.next.nextreturndummy.next3.判斷環(huán)：思路：快慢指針。代碼：pythondefdetectCycle(head):slow=fast=headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextifslow==fast:slow=headwhileslow!=fast:slow=slow.nextfast=fast.nextreturnslowreturnNone4.合并有序鏈表：思路：遞歸或迭代。代碼：pythondefmergeTwoLists(l1,l2):dummy=ListNode(0)current=dummywhilel1andl2:ifl1.val<l2.val:current.next=l1l1=l1.nextelse:current.next=l2l2=l2.nextcurrent=current.nextcurrent.next=l1orl2returndummy.next三、棧與隊列問題1.棧實現(xiàn)隊列：思路：使用兩個棧，一個用于入隊，一個用于出隊。代碼：pythonclassMyQueue:def__init__(self):self.in_stack=[]self.out_stack=[]defpush(self,x):self.in_stack.append(x)defpop(self):self.move()returnself.out_stack.pop()defmove(self):ifnotself.out_stack:whileself.in_stack:self.out_stack.append(self.in_stack.pop())2.隊列實現(xiàn)棧：思路：使用兩個隊列，一個用于入隊，一個用于出隊。代碼：pythonclassMyStack:def__init__(self):self.in_queue=[]self.out_queue=[]defpush(self,x):self.in_queue.append(x)defpop(self):self.move()returnself.out_queue.pop(0)defmove(self):ifnotself.out_queue:whileself.in_queue:self.out_queue.append(self.in_queue.pop(0))self.in_queue,self.out_queue=self.out_queue,self.in_queue3.括號匹配：思路：棧。代碼：pythondefisValid(s):stack=[]mapping={')':'(','}':'{',']':'['}forcins:ifcinmapping:ifstackandstack[-1]==mapping[c]:stack.pop()else:returnFalseelse:stack.append(c)returnnotstack四、樹與圖問題1.二叉樹最大深度：遞歸：pythondefmaxDepth(root):ifnotroot:return0return1+max(maxDepth(root.left),maxDepth(root.right))迭代：pythondefmaxDepth(root):ifnotroot:return0queue=[root]depth=0whilequeue:level_size=len(queue)for_inrange(level_size):node=queue.pop(0)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)depth+=1returndepth2.層序遍歷：pythondeflevelOrder(root):ifnotroot:return[]queue=[root]res=[]whilequeue:node=queue.pop(0)res.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)returnres3.圖的環(huán)判斷：pythondefhasCycle(graph):visited=set()rec_stack=set()defdfs(node):ifnodeinrec_stack:returnTrueifnodeinvisited:returnFalsevisited.add(node)rec_stack.add(node)forneighboringraph[node]:ifdfs(neighbor):returnTruerec_stack.remove(node)returnFalsefornodeingraph:ifdfs(node):returnTruereturnFalse4.二叉搜索樹最小深度：pythondefminDepth(root):ifnotroot:return0ifnotroot.left:return1+minDepth(root.right)ifnotroot.right:return1+minDepth(root.left)return1+min(minDepth(root.left),minDepth(root.right))五、動態(tài)規(guī)劃問題1.最大子數(shù)組和：pythondefmaxSubArray(nums):max_sum=nums[0]current_sum=nums[0]fornuminnums[1:]:current_sum=max(num,current_sum+num)max_sum=max(max_sum,current_sum)returnmax_sum2.爬樓梯：pythondefclimbStairs(n):ifn==1:return1dp=[0](n+1)dp[1],dp[2]=1,2foriinrange(3,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]3.最長公共子序列：pythondeflongestCommonSubsequence(text1,text2):m,n=len(text1),len(text2)dp=[[0](n+1)for_inrange(m+1)]foriinrange(1,m+1):forjinrange(1,n+1):iftext1[i-1]==text2[j-1]:dp[i][j]=dp[i-1][j-1]+1else:dp[i][j]=max(dp[i-1][j],dp[i][j-1])return