leetcode python刷题记录（十）（91~100）
leetcode python刷题记录（十）（91~100）
91. 解码方法
class Solution:def numDecodings(self, s: str) -> int:if not s or s[0]=='0':return 0n=len(s)dp=[0]*(n+1)dp[0]=1dp[1]=1for i in range(1,n):if s[i]=='0':if s[i-1]=='1' or s[i-1]=='2':dp[i+1]=dp[i-1]else:return 0else:if s[i-1]=='1' or (s[i-1]=='2' and '1'<=s[i]<='6'): # 可以自己单独解码也可以和上一位组合解码，所以s[i+1]=s[i]+s[i-1]dp[i+1]=dp[i]+dp[i-1]else:dp[i+1]=dp[i]return dp[n]
92. 反转链表 II
class Solution:def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:dummy=ListNode(0)dummy.next=headpre=dummyfor i in range(left-1):pre=pre.nextcur=pre.next# 头插法for i in range(right-left):temp1=cur.nexttemp2=temp1.nextcur.next=temp2temp1.next=pre.nextpre.next=temp1return dummy.next
93. 复原 IP 地址
class Solution:def restoreIpAddresses(self, s: str) -> List[str]:res=[]def dfs(start,temp):if len(temp)>4:return if start==len(s) and len(temp)==4:return res.append('.'.join(temp))for i in range(start,len(s)):if int(s[start:i+1])>255 or (s[start]=='0' and len(s[start:i+1])>=2):# 取出来的大于255，或者不是单个0，那么不满足要求returntemp.append(s[start:i+1])dfs(i+1,temp)temp.pop()dfs(0,[])return res
94. 二叉树的中序遍历
class Solution:def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:if not root:return []res,stack=[],[]while root or stack:# 先遍历左子树while root:stack.append(root)root=root.left# 到头了，返回上一级root=stack.pop()res.append(root.val)# 遍历右子树root=root.rightreturn res
95. 不同的二叉搜索树 II
读于一棵二叉搜索树来说，一个重要的性质就是它的中序遍历为升序，中序遍历的过程为左 -> 根 -> 右，如果给每个结点标记上编号，意思就是说所有左子树节点的编号一定小于根节点，所有右子树的结点编号大于根节点。在此题中给定了一个中序遍历顺序1 ~ n， 于是我们的思路如下：
- 先枚举根节点的位置，将问题划分为分别递归求解左边子树和右边子树
- 递归返回的是所有合法方案的集合，所以枚举每种合法的左右儿子
- 枚举左右儿子和根节点作为一种合法方案记录下来
class Solution:def generateTrees(self, n: int) -> List[Optional[TreeNode]]:def dfs(l,r):if l>r:return [None]res=[]for i in range(l,r+1):left=dfs(l,i-1)right=dfs(i+1,r)for l_child in left:for r_child in right:root=TreeNode(i)root.left=l_childroot.right=r_childres.append(root)return resreturn dfs(1,n)
96. 不同的二叉搜索树
class Solution:def numTrees(self, n: int) -> int:dp=[0]*(n+1)dp[0]=1for m in range(1,n+1): # 枚举长度for i in range(1,m+1): # 枚举root节点的位置dp[m]=dp[m]+dp[i-1]*dp[m-i] # dp[m]=左子树*右子树return dp[n]