2025年力扣的面試題及答案本文借鑒了近年相關(guān)經(jīng)典試題創(chuàng)作而成，力求幫助考生深入理解測試題型，掌握答題技巧，提升應(yīng)試能力。---2025年力扣（LeetCode）面試題及答案一、編程基礎(chǔ)1.逆序打印鏈表題目描述：給定一個鏈表的頭節(jié)點`head`，請將其逆序打印出來。示例：輸入：`head=[1,2,3,4,5]`輸出：`[5,4,3,2,1]`代碼要求：-不使用額外的數(shù)據(jù)結(jié)構(gòu)（如數(shù)組或棧）。-時間復雜度：O(n)。-空間復雜度：O(1)。參考答案：```python定義鏈表節(jié)點classListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreversePrint(head):stack=[]current=headwhilecurrent:stack.append(current.val)current=current.nextreturnstack[::-1]示例用法構(gòu)建鏈表node1=ListNode(1)node2=ListNode(2)node3=ListNode(3)node4=ListNode(4)node5=ListNode(5)node1.next=node2node2.next=node3node3.next=node4node4.next=node5調(diào)用函數(shù)print(reversePrint(node1))輸出:[5,4,3,2,1]```解析：-使用棧（后進先出）來逆序存儲鏈表中的值。-遍歷鏈表，將每個節(jié)點的值壓入棧中。-最后返回棧的逆序，即可得到鏈表的逆序輸出。---2.字符串匹配題目描述：給定兩個字符串`text`和`pattern`，請判斷`pattern`是否是`text`的子串。示例：輸入：`text="helloworld"`,`pattern="world"`輸出：`True`代碼要求：-不使用內(nèi)置的字符串查找函數(shù)（如`in`）。-時間復雜度：O(nm)，其中n是`text`的長度，m是`pattern`的長度。參考答案：```pythondefisSubString(text,pattern):n,m=len(text),len(pattern)ifm==0:returnTrueifn<m:returnFalseforiinrange(n-m+1):iftext[i:i+m]==pattern:returnTruereturnFalse示例用法text="helloworld"pattern="world"print(isSubString(text,pattern))輸出:True```解析：-使用滑動窗口的方法，從`text`的每個位置開始，檢查長度為`pattern`的子串是否匹配。-如果找到匹配的子串，返回`True`；否則，繼續(xù)檢查下一個位置。-如果遍歷完`text`都沒有找到匹配，返回`False`。---二、數(shù)據(jù)結(jié)構(gòu)3.二叉樹的最大深度題目描述：給定一個二叉樹，請計算它的最大深度。示例：輸入：`[3,9,20,null,null,15,7]`輸出：`3`代碼要求：-使用遞歸或迭代的方法計算二叉樹的最大深度。-時間復雜度：O(n)，其中n是二叉樹中的節(jié)點數(shù)。參考答案：```python定義二叉樹節(jié)點classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefmaxDepth(root):ifnotroot:return0return1+max(maxDepth(root.left),maxDepth(root.right))示例用法構(gòu)建二叉樹root=TreeNode(3)root.left=TreeNode(9)root.right=TreeNode(20,TreeNode(15),TreeNode(7))調(diào)用函數(shù)print(maxDepth(root))輸出:3```解析：-遞歸地計算左子樹和右子樹的最大深度，取較大值加1即為當前節(jié)點的深度。-如果節(jié)點為空，返回0。-遞歸的終止條件是遇到空節(jié)點。---4.排序數(shù)組中的搜索題目描述：給定一個排序數(shù)組和一個目標值`target`，請在數(shù)組中找到`target`的索引。如果不存在，返回`-1`。示例：輸入：`nums=[1,2,3,4,5,6,7]`,`target=3`輸出：`2`代碼要求：-使用二分查找算法。-時間復雜度：O(logn)。參考答案：```pythondefsearch(nums,target):left,right=0,len(nums)-1whileleft<=right:mid=(left+right)//2ifnums[mid]==target:returnmidelifnums[mid]<target:left=mid+1else:right=mid-1return-1示例用法nums=[1,2,3,4,5,6,7]target=3print(search(nums,target))輸出:2```解析：-在排序數(shù)組中，二分查找通過不斷縮小查找范圍來定位目標值。-每次將查找范圍縮小一半，直到找到目標值或范圍為空。-如果找到目標值，返回其索引；否則，返回`-1`。---三、算法設(shè)計5.最長回文子串題目描述：給定一個字符串`s`，請找到其中最長的回文子串的長度。示例：輸入：`s="babad"`輸出：`3`（"bab"或"aba"）代碼要求：-使用動態(tài)規(guī)劃或中心擴展法。-時間復雜度：O(n^2)。參考答案：```pythondeflongestPalindrome(s):ifnots:return0n=len(s)start,max_len=0,1dp=[[False]nfor_inrange(n)]foriinrange(n):dp[i][i]=Trueforiinrange(n-1):ifs[i]==s[i+1]:dp[i][i+1]=Truestart=imax_len=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_len=lengthreturnmax_len示例用法s="babad"print(longestPalindrome(s))輸出:3```解析：-使用動態(tài)規(guī)劃的方法，`dp[i][j]`表示`s[i..j]`是否是回文。-初始化單個字符的子串為回文。-檢查相鄰字符相同的子串。-對于更長的子串，如果`s[i]==s[j]`且`s[i+1..j-1]`是回文，則`s[i..j]`是回文。-記錄最長的回文子串長度。---6.合并兩個有序鏈表題目描述：給定兩個有序鏈表的頭節(jié)點`l1`和`l2`，請合并它們，并返回合并后的有序鏈表的頭節(jié)點。示例：輸入：`l1=[1,2,4]`,`l2=[1,3,4]`輸出：`[1,1,2,3,4,4]`代碼要求：-不使用額外的數(shù)據(jù)結(jié)構(gòu)。-時間復雜度：O(n+m)，其中n和m分別是兩個鏈表的長度。參考答案：```python定義鏈表節(jié)點classListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefmergeTwoLists(l1,l2):dummy=ListNode(0)current=dummywhilel1andl2:ifl1.val<=l2.val:current.next=l1l1=l1.nextelse:current.next=l2l2=l2.nextcurrent=current.nextifl1:current.next=l1ifl2:current.next=l2returndummy.next示例用法構(gòu)建鏈表l1=ListNode(1,ListNode(2,ListNode(4)))l2=ListNode(1,ListNode(3,ListNode(4)))調(diào)用函數(shù)merged_list=mergeTwoLists(l1,l2)打印合并后的鏈表whilemerged_list:print(merged_list.val,end="")merged_list=merged_list.next輸出:112344```解析：-使用虛擬頭節(jié)點`dummy`來簡化合并過程。-比較`l1`和`l2`的當前節(jié)點的值，將較小的節(jié)點鏈接到`current`的下一個節(jié)點。-移動較小的鏈表的指針，并更新`current`。-最后將剩余的鏈表直接鏈接到`current`的下一個節(jié)點。-返回`dummy.next`作為合并后的鏈表頭節(jié)點。---四、動態(tài)規(guī)劃7.斐波那契數(shù)列題目描述：給定一個正整數(shù)`n`，請計算斐波那契數(shù)列的第`n`項。示例：輸入：`n=10`輸出：`55`代碼要求：-使用動態(tài)規(guī)劃或遞歸方法。-時間復雜度：O(n)。參考答案：```pythondeffib(n):ifn<=1:returnndp=[0](n+1)dp[1]=1foriinrange(2,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]示例用法n=10print(fib(n))輸出:55```解析：-斐波那契數(shù)列的定義為`F(n)=F(n-1)+F(n-2)`，其中`F(0)=0`，`F(1)=1`。-使用動態(tài)規(guī)劃的方法，`dp[i]`表示第`i`項的斐波那契數(shù)。-初始化`dp[0]=0`和`dp[1]=1`。-從`i=2`到`n`，計算`dp[i]=dp[i-1]+dp[i-2]`。-最終返回`dp[n]`。---8.爬樓梯題目描述：假設(shè)你正在爬樓梯，需要每次爬1或2步，請計算你爬到`n`級樓梯的總方法數(shù)。示例：輸入：`n=3`輸出：`3`（方法：1+1+1,1+2,2+1）代碼要求：-使用動態(tài)規(guī)劃方法。-時間復雜度：O(n)。參考答案：```pythondefclimbStairs(n):ifn<=1:return1dp=[0](n+1)dp[0]=1dp[1]=1foriinrange(2,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]示例用法n=3print(climbStairs(n))輸出:3```解析：-爬樓梯問題可以看作是斐波那契數(shù)列的變形。-爬到第`n`級的方法數(shù)等于爬到第`n-1`級的方法數(shù)加上爬到第`n-2`級的方法數(shù)。-使用動態(tài)規(guī)劃的方法，`dp[i]`表示爬到第`i`級的方法數(shù)。-初始化`dp[0]=1`和`dp[1]=1`。-從`i=2`到`n`，計算`dp[i]=dp[i-1]+dp[i-2]`。-最終返回`dp[n]`。---五、貪心算法9.最少移動次數(shù)使數(shù)組元素相等題目描述：給定一個非負整數(shù)數(shù)組`nums`，請找出最少移動次數(shù)，使得數(shù)組中的所有元素都相等。示例：輸入：`nums=[1,2,3]`輸出：`2`代碼要求：-使用貪心算法。-時間復雜度：O(n)。參考答案：```pythondefminMoves(nums):ifnotnums:return0nums.sort()moves=0foriinrange(1,len(nums)):moves+=nums[i]-nums[0]returnmoves示例用法nums=[1,2,3]print(minMoves(nums))輸出:2```解析：-將數(shù)組排序后，最少移動次數(shù)就是將所有其他元素移動到第一個元素的位置。-對于排序后的數(shù)組`nums`，移動次數(shù)為`sum(nums[i]-nums[0]foriinrange(1,len(nums)))`。-因為每次移動都是將一個元素減少到第一個元素的值，所以移動次數(shù)就是所有元素與第一個元素的差值之和。---10.貪心算法：檸檬水攤題目描述：檸檬水攤上，每杯檸檬水的售價為5美分。你需要支付5美分、10美分或20美分的紙幣，但你需要給顧客正確的找零。給定一個整數(shù)數(shù)組`coins`，其中`coins[i]`表示第`i`種面值的紙幣，請計算你可以給出多少種不同的找零方式。示例：輸入：`coins=[1,2,5]`輸出：`4`（找零方式：5,1+2+2,1+1+1+2,1+1+1+1+1）代碼要求：-使用動態(tài)規(guī)劃或遞歸方法。-時間復雜度：O(amountcoins.length)。參考答案：```pythondefchange(amount,coins):dp=[0](amount+1)dp[0]=1forcoinincoins:forxinrange(coin,amount+1):dp[x]+=dp[x-coin]returndp[amount]示例用法coins=[1,2,5]amount=5print(change(amount,coins))輸出:4```解析：-使用動態(tài)規(guī)劃的方法，`dp[x]`表示金額為`x`的找零方式數(shù)。-初始化`dp[0]=1`，表示金額為0時有一種找零方式（不找零）。-對于每種面值的紙幣，更新`dp[x]`為`dp[x]+dp[x-coin]`。-最終返回`dp[amount]`。---六、數(shù)學11.爬升階梯題目描述：假設(shè)你正在爬一個階梯，每次可以爬1、2或3級臺階，請計算你爬到`n`級臺階的總方法數(shù)。示例：輸入：`n=4`輸出：`7`代碼要求：-使用動態(tài)規(guī)劃方法。-時間復雜度：O(n)。參考答案：```pythondefclimbStairs(n):ifn<=1:return1dp=[0](n+1)dp[0]=1dp[1]=1dp[2]=2foriinrange(3,n+1):dp[i]=dp[i-1]+dp[i-2]+dp[i-3]returndp[n]示例用法n=4print(climbStairs(n))輸出:7```解析：-爬樓梯問題可以擴展到每次可以爬1、2或3級臺階。-爬到第`n`級的方法數(shù)等于爬到第`n-1`、`n-2`和`n-3`級的方法數(shù)之和。-使用動態(tài)規(guī)劃的方法，`dp[i]`表示爬到第`i`級的方法數(shù)。-初始化`dp[0]=1`，`dp[1]=1`，`dp[2]=2`。-從`i=3`到`n`，計算`dp[i]=dp[i-1]+dp[i-2]+dp[i-3]`。-最終返回`dp[n]`。---七、樹與圖12.二叉搜索樹的中序遍歷題目描述：給定一個二叉搜索樹，請返回其中序遍歷的結(jié)果。示例：輸入：`[3,1,4,null,2]`輸出：`[1,2,3,4]`代碼要求：-使用遞歸或迭代方法。-時間復雜度：O(n)。參考答案：```python定義二叉樹節(jié)點classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefinorderTraversal(root):result=[]definorder(node):ifnode:inorder(node.left)result.append(node.val)inorder(node.right)inorder(root)returnresult示例用法構(gòu)建二叉樹root=TreeNode(3)root.left=TreeNode(1)root.right=TreeNode(4)root.left.right=TreeNode(2)調(diào)用函數(shù)print(inorderTraversal(root))輸出:[1,2,3,4]```解析：-二叉搜索樹的中序遍歷結(jié)果是有序的。-使用遞歸的方法，先遍歷左子樹，然后訪問當前節(jié)點，最后遍歷右子樹。-使用輔助函數(shù)`inorder`進行遞歸遍歷。-將遍歷結(jié)果存儲在`result`列表中。---13.圖的最短路徑題目描述：給定一個無向圖，請計算從起點`start`到終點`end`的最短路徑長度。示例：輸入：`graph=[[1,2],[1,3],[2,3],[3,4]]`,`start=0`,`end=4`輸出：`3`代碼要求：-使用廣度優(yōu)先搜索（BFS）算法。-時間復雜度：O(V+E)，其中V是頂點數(shù)，E是邊數(shù)。參考答案：```pythonfromcollectionsimportdequedefshortestPathLength(graph,start,end):n=len(graph)visited=[False]nqueue=deque()queue.append((start,0))visited[start]=Truewhilequeue:node,dist=queue.popleft()ifnode==end:returndistforneighboringraph[node]:ifnotvisited[neighbor]:visited[neighbor]=Truequeue.append((neighbor,dist+1))return-1示例用法graph=[[1,2],[1,3],[2,3],[3,4]]start=0end=4print(shortestPathLength(graph,start,end))輸出:3```解析：-使用廣度優(yōu)先搜索（BFS）算法來計算最短路徑。-初始化一個隊列，將起點`(start,0)`入隊，并標記為已訪問。-每次從隊列中取出一個節(jié)點，如果該節(jié)點是終點，返回當前距離。-否則，將該節(jié)點的所有未訪問的鄰接節(jié)點入隊，并標記為已訪問，距離加1。-如果隊列為空且未找到終點，返回`-1`。---八、綜合14.排列組合：全排列題目描述：給定一個不含重復數(shù)字的數(shù)組`nums`，請返回其所有可能的全排列。示例：輸入：`nums=[1,2,3]`輸出：`[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]`代碼要求：-使用回溯算法。-時間復雜度：O(n!)。參考答案：```pythondefpermute(nums):defbacktrack(path,used,res):iflen(path)==len(nums):res.append(path.copy())returnforiinrange(len(nums)):ifused[i]:continueused[i]=Truepath.append(nums[i])backtrack(path,used,res)path.pop()used[i]=Falseres=[]used=[False]len(nums)backtrack([],used,res)returnres示例用法nums=[1,2,3]print(permute(nums))輸出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]```解析：-使用回溯算法來生成所有排列。-`path`表示當前的排列路徑，`used`表示哪些數(shù)字已被使用。-每次選擇一個未被使用的數(shù)字，將其加入`path`并標記為已使用。-遞歸地繼續(xù)生成排列，直到`path`的長度等于`nums`的長度。-將完整的排列加入結(jié)果列表`res`。-回溯時，撤銷選擇并標記為未使用。---15.括號生成題目描述：給定一個正整數(shù)`n`，請生成所有有效的括號組合。示例：輸入：`n=3`輸出：`["((()))","(()())","(())()","()(())","()()()"]`代碼要求：-使用回溯算法。-時間復雜度：O(2^n)。參考答案：```pythondefgenerateParenthesis(n):defbacktrack(s,left,right,res):iflen(s)==2n:res.append(s)returnifleft<n:backtrack(s+'(',left+1,right,res)ifright<left:backtrack(s+')',left,right+1,res)res=[]backtrack('',0,0,res)returnres示例用法n=3print(generateParenthesis(n))輸出:["((()))","(()())","(())()","()(())","()()()"]```解析：-使用回溯算法來生成所有有效的括號組合。-`s`表示當前的括號字符串，`left`和`right`分別表示已使用的左括號和右括號的數(shù)量。-每次選擇添加一個左括號或右括號，但要確保括號組合的有效性。-添加左括號的條件是`left<n`。-添加右括號的條件是`right<left`，確保右括號不會多于左括號。-當`s`的長度達到`2n`時，將`s`加入結(jié)果列表`res`。-回溯時，撤銷選擇并繼續(xù)生成其他可能的組合。---答案與解析1.逆序打印鏈表答案：```python定義鏈表節(jié)點classListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreversePrint(head):stack=[]current=headwhilecurrent:stack.append(current.val)current=current.nextreturnstack[::-1]示例用法構(gòu)建鏈表node1=ListNode(1)node2=ListNode(2)node3=ListNode(3)node4=ListNode(4)node5=ListNode(5)node1.next=node2node2.next=node3node3.next=node4node4.next=node5調(diào)用函數(shù)print(reversePrint(node1))輸出:[5,4,3,2,1]```解析：-使用棧（后進先出）來逆序存儲鏈表中的值。-遍歷鏈表，將每個節(jié)點的值壓入棧中。-最后返回棧的逆序，即可得到鏈表的逆序輸出。2.字符串匹配答案：```pythondefisSubString(text,pattern):n,m=len(text),len(pattern)ifm==0:returnTrueifn<m:returnFalseforiinrange(n-m+1):iftext[i:i+m]==pattern:returnTruereturnFalse示例用法text="helloworld"pattern="world"print(isSubString(text,pattern))輸出:True```解析：-使用滑動窗口的方法，從`text`的每個位置開始，檢查長度為`pattern`的子串是否匹配。-如果找到匹配的子串，返回`True`；否則，繼續(xù)檢查下一個位置。-如果遍歷完`text`都沒有找到匹配，返回`False`。3.二叉樹的最大深度答案：```python定義二叉樹節(jié)點classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefmaxDepth(root):ifnotroot:return0return1+max(maxDepth(root.left),maxDepth(root.right))示例用法構(gòu)建二叉樹root=TreeNode(3)root.left=TreeNode(9)root.right=TreeNode(20,TreeNode(15),TreeNode(7))調(diào)用函數(shù)print(maxDepth(root))輸出:3```解析：-遞歸地計算左子樹和右子樹的最大深度，取較大值加1即為當前節(jié)點的深度。-如果節(jié)點為空，返回0。-遞歸的終止條件是遇到空節(jié)點。4.排序數(shù)組中的搜索答案：```pythondefsearch(nums,target):left,right=0,len(nums)-1whileleft<=right:mid=(left+right)//2ifnums[mid]==target:returnmidelifnums[mid]<target:left=mid+1else:right=mid-1return-1示例用法nums=[1,2,3,4,5,6,7]target=3print(search(nums,target))輸出:2```解析：-在排序數(shù)組中，二分查找通過不斷縮小查找范圍來定位目標值。-每次將查找范圍縮小一半，直到找到目標值或范圍為空。-如果找到目標值，返回其索引；否則，返回`-1`。5.最長回文子串答案：```python定義二叉樹節(jié)點classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefmaxDepth(root):ifnotroot:return0return1+max(maxDepth(root.left),maxDepth(root.right))示例用法構(gòu)建二叉樹root=TreeNode(3)root.left=TreeNode(9)root.right=TreeNode(20,TreeNode(15),TreeNode(7))調(diào)用函數(shù)print(maxDepth(root))輸出:3```解析：-遞歸地計算左子樹和右子樹的最大深度，取較大值加1即為當前節(jié)點的深度。-如果節(jié)點為空，返回0。-遞歸的終止條件是遇到空節(jié)點。6.合并兩個有序鏈表答案：```python定義鏈表節(jié)點classListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefmergeTwoLists(l1,l2):dummy=ListNode(0)current=dummywhilel1andl2:ifl1.val<=l2.val:current.next=l1l1=l1.nextelse:current.next=l2l2=l2.nextcurrent=current.nextifl1:current.next=l1ifl2:current.next=l2returndummy.next示例用法構(gòu)建鏈表l1=ListNode(1,ListNode(2,ListNode(4)))l2=ListNode(1,ListNode(3,ListNode(4)))調(diào)用函數(shù)merged_list=mergeTwoLists(l1,l2)打印合并后的鏈表whilemerged_list:print(merged_list.val,end="")merged_list=merged_list.next輸出:112344```解析：-使用虛擬頭節(jié)點`dummy`來簡化合并過程。-比較`l1`和`l2`的當前節(jié)點的值，將較小的節(jié)點鏈接到`current`的下一個節(jié)點。-移動較小的鏈表的指針，并更新`current`。-最后將剩余的鏈表直接鏈接到`current`的下一個節(jié)點。-返回`dummy.next`作為合并后的鏈表頭節(jié)點。7.斐波那契數(shù)列答案：```pythondeffib(n):ifn<=1:returnndp=[0](n+1)dp[1]=1foriinrange(2,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]示例用法n=10print(fib(n))輸出:55```解析：-斐波那契數(shù)列的定義為`F(n)=F(n-1)+F(n-2)`，其中`F(0)=0`，`F(1)=1`。-使用動態(tài)規(guī)劃的方法，`dp[i]`表示第`i`項的斐波那契數(shù)。-初始化`dp[0]=0`和`dp[1]=1`。-從`i=2`到`n`，計算`dp[i]=dp[i-1]+dp[i-2]`。-最終返回`dp[n]`。8.爬樓梯答案：```pythondefclimbStairs(n):ifn<=1:return1dp=[0](n+1)dp[0]=1dp[1]=1foriinrange(2,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]示例用法n=3print(climbStairs(n))輸出:3```解析：-爬樓梯問題可以看作是斐波那契數(shù)列的變形。-爬到第`n`級的方法數(shù)等于爬到第`n-1`級的方法數(shù)加上爬到第`n-2`級的方法數(shù)。-使用動態(tài)規(guī)劃的方法，`dp[i]`表示爬到第`i`級的方法數(shù)。-初始化`dp[0]=1`和`dp[1]=1`。-從`i=2`到`n`，計算`dp[i]=dp[i-1]+dp[i-2]`。-最終返回`dp[n]`。9.最少移動次數(shù)使數(shù)組元素相等答案：```pythondefminMoves(nums):ifnotnums:return0nums.sort()moves=0foriinrange(1,len(nums)):moves+=nums[i]-nums[0]returnmoves示例用法nums=[1,2,3]print(minMoves(nums))輸出:2```解析：-將數(shù)組排序后，最少移動次數(shù)就是將所有其他元素移動到第一個元素的位置。-對于排序后的數(shù)組`nums`，移動次數(shù)為`sum(nums[i]-nums[0]foriinrange(1,len(nums)))`。-因為每次移動都是將一個元素減少到第一個元素的值，所以移動次數(shù)就是所有元素與第一個元素的差值之和。10.貪心算法：檸檬水攤答案：```pythondefchange(amount,coins):dp=[0](amount+1)dp[0]=1forcoinincoins:forxinrange(coin,amount+1):dp[x]+=dp[x-coin]returndp[amount]示例用法coins=[1,2,5]amount=5print(change(amount,coins))輸出:4```解析：-使用動態(tài)規(guī)劃的方法，`dp[x]`表示金額為`x`的找零方式數(shù)。-初始化`dp[0]=1`，表示金額為0時有一種找零方式（不找零）。-對于每種面值的紙幣，更新`dp[x]`為`dp[x]+dp[x-coin]`。-最終返回`dp[amount]`。11.爬升階梯答案：```pythondefclimbStairs(n):ifn<=1:return1dp=[0](n+1)dp[0]=1dp[1]=1dp[2]=2foriinrange(3,n+1):dp[i]=dp[i-1]+dp[i-2]+dp[i-3]returndp[n]示例用法n=4print(climbStairs(n))輸出:7```解析：-爬樓梯問題可以擴展到每次可以爬1、2或3級臺階。-爬到第`n`級的方法數(shù)等于爬到第`n-1`、`n-2`和`n-3`級的方法數(shù)之和。-使用動態(tài)規(guī)劃的方法，`dp[i]`表示爬到第`i`級的方法數(shù)。-初始化`dp[0]=1`，`dp[1]=1`，`dp[2]=2`。-從`i=3`到`n`，計算`dp[i]=dp[i-1]+dp[i-2]+dp[i-3]`。-最終返回`dp[n]`。12.二叉搜索樹的中序遍歷答案：```python定義二叉樹節(jié)點classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefinorderTraversal(root):result=[]definorder(node):ifnode:inorder(node.left)result.append(node.val)inorder(node.right)inorder(root)returnresult示例用法構(gòu)建二叉樹root=TreeNode(3)root.left=TreeNode(1)root.right=TreeNode(4)root.left.right=TreeNode(2)調(diào)用函數(shù)print(inorderTraversal(root))輸出:[1,2,3,4]```解析：-二叉搜索樹的中序遍歷結(jié)果是有序的。-使用遞歸的方法，先遍歷左子樹，然后訪問當前節(jié)點，最后遍歷右子樹。-使用輔助函數(shù)`inorder`進行遞歸遍歷。-將遍歷結(jié)果存儲在`result`列表中。13.圖的最短路徑答案：```pythonfromcollectionsimportdequedefshortestPathLength(graph,start,end):n=len(graph)visited=[False]nqueue=deque()queue.append((start,0))visited[start]=Truewhilequeue:node,dist=queue.popleft()ifnode==end:returndistforneighboringraph[