力扣91~95题
题91（中等）：
分析：
无语了，不知道什么时候开始中等题都做得有压力了。。。
找点规律用动态规划
python代码：
class Solution:
def numDecodings(self, s: str) -> int:
#采用动态数组
flag=0
s_len=len(s)
auto_list=[0 for i in range(s_len+1)]
auto_list[0]=1
for i in range(s_len):
if s[i]=='0':
if i>0:
if flag==1 or flag==2:
auto_list[i+1]=auto_list[i-1]
flag=0
continue
else:
return 0
else:
return 0
if flag==1:
auto_list[i+1]=auto_list[i]+auto_list[i-1]
elif flag==2:
if s[i]<='6':
auto_list[i+1]=auto_list[i]+auto_list[i-1]
else:
auto_list[i+1]=auto_list[i]
else:
auto_list[i+1]=auto_list[i]
if s[i]=='1':
flag=1
continue
elif s[i]=='2':
flag=2
continue
else:
flag=0
return auto_list[-1]
题92（中等）：
分析：
刚开始我真的想直接用数组接，然后翻转，后面还是挑战一下链表的操作吧，例图还没了。。。
python代码：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
#借用3个指针，p,q ---》 p保存left左边的，q右边的
if left==right:
return head
new_head=ListNode(next=head)
p=new_head
q=None
r=None
tail=None
i=1
while i<left:
#找到如图2的位置
if p!=None:
p=p.next
i+=1
if p!=None:
#指向如图2
q=p.next
tail=q
if q!=None:
#指向如图3
r=q.next
i=0
while i<=right-left:
q.next=p.next
p.next=q
q=r
if i!=right-left:
r=r.next
i+=1
tail.next=r
return new_head.next
题93（中等）：复原 IP 地址
python代码：
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
# ip地址应该要有3个点，分成4份，长度肯定有限制，所以采用递归的方法
res = []
def callback(s, k, ip_list):
# s是剩余的字符串，k是还要分割的点数
# ip_list是现在以及存好的数据
if len(s) < k or 3 * k < len(s):
return
if k == 1:
# 如果k为0，判断s，如果数字大于255，无效
if len(s) > 3:
return
else:
if len(s) > 1 and s[0] == '0':
return
if int(s) > 255:
return
ip_list.append(s)
res.append('.'.join(ip_list))
return
if s[0] > '2':
cut = 2 if len(s) > 2 else len(s)
else:
cut = 3 if len(s) > 3 else len(s)
if s[0] == '0':
new_ip_list = ip_list.copy()
new_ip_list.append('0')
callback(s[1:], k - 1, new_ip_list)
return
for i in range(cut):
if len(s) - i - 1 > (k - 1) * 3:
continue
if int(s[:i + 1])>255:
return
new_ip_list = ip_list.copy()
new_ip_list.append(s[:i + 1])
callback(s[i + 1:], k - 1, new_ip_list)
callback(s, 4, [])
return res题94（简单）：
python代码：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
#第一个递归做法(中序遍历是先左再中后右)
# res=[]
# def callback(root):
# if root==None:
# return
# callback(root.left)
# res.append(root.val)
# print(root.val)
# callback(root.right)
# callback(root)
# return res
#迭代，模拟栈结构？
node_stack=[]
p=root
res=[]
while 1:
if p==None and node_stack==[]:
break
#先将左边的进去
if p!=None:
node_stack.append(p)
p=p.left
else:
#左是空
p=node_stack.pop()
res.append(p.val)
p=p.right
return res
题95（中等）：
分析：
说实话没看懂题目，就不写这题，分享一个别人的
python代码：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
def generate_trees(n):
if n == 0:
return []
return generate_trees_recursively(1, n)
def generate_trees_recursively(start, end):
trees = []
if start > end:
trees.append(None)
return trees
for i in range(start, end + 1):
# 生成所有可能的左子树
left_trees = generate_trees_recursively(start, i - 1)
# 生成所有可能的右子树
right_trees = generate_trees_recursively(i + 1, end)
# 将左子树和右子树组合起来，并与当前根节点连接
for l in left_trees:
for r in right_trees:
current_tree = TreeNode(i)
current_tree.left = l
current_tree.right = r
trees.append(current_tree)
return trees
trees = generate_trees(n)
return trees