先序遍历和后序遍历为什么不能唯一地确定一棵树？：





[https://blog.csdn.net/GYQJN/article/details/52709912](https://blog.csdn.net/GYQJN/article/details/52709912)

只有每个节点度为2或者0的时候前序和后序才能唯一确定一颗二叉树，只有一个子节点是无法确定的，因为你无法判断他是左子树还是右子树。

105. 从前序与中序遍历序列构造二叉树

[https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)

106. 从中序与后序遍历序列构造二叉树

[https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)

108. 根据前序和后序遍历构造二叉树

[https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/)



从来都是用来当填空题的。现在要求写程序。

比如：
```c
     A
  B     C
F      D  E
```

a=['A','B','F','C','D','E']   #前序样子

b=['F','B','A','D','C','E']   #中序样子

c=['F','B','D','E','C','A']  #后序样子

规律：

![在这里插入图片描述](/static/img/images/00964.png)

要点：树的前序遍历第一个是根节点。长度关系。子数递归满足此条件。


```python
from typing import List
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    def buildTreeFromPreorderInorder(self, preorder: List[str], inorder: List[str]) -> TreeNode:
        n = len(preorder)
        # 构造哈希映射，帮助我们快速定位根节点
        index = {element: i for i, element in enumerate(inorder)}
        def helper(preorder_left: int, preorder_right: int, inorder_left: int, inorder_right: int):
            if preorder_left > preorder_right:
                return None
            # 前序遍历中的第一个节点就是根节点
            preorder_root = preorder_left
            # 在中序遍历中定位根节点
            inorder_root = index[preorder[preorder_root]]
            # 先把根节点建立出来
            root = TreeNode(preorder[preorder_root])
            # 得到左子树中的节点数目
            size_left_subtree = inorder_root - inorder_left
            # 递归地构造左子树，并连接到根节点
            # 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
            root.left = helper(preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1)
            # 递归地构造右子树，并连接到根节点
            # 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
            root.right = helper(preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right)
            return root
        return helper(0, n - 1, 0, n - 1)
    def buildTreeFromInorderPostorder(self, inorder , postorder):
        temp=postorder[:]
        def helper(in_left, in_right):
            # 如果这里没有节点构造二叉树了，就结束
            if in_left > in_right:
                return None
            # 选择 post_idx 位置的元素作为当前子树根节点
            val = temp.pop()
            root = TreeNode(val)
            # 根据 root 所在位置分成左右两棵子树
            index = idx_map[val]
            # 构造右子树
            root.right = helper(index + 1, in_right)
            # 构造左子树
            root.left = helper(in_left, index - 1)
            return root
        # 建立（元素，下标）键值对的哈希表
        idx_map = {val: idx for idx, val in enumerate(inorder)}
        return helper(0, len(inorder) - 1)
    def constructFromPreorderPostorder(self, pre, post):
        if not pre:
            return None
        node = TreeNode(pre[0])
        if len(pre) == 1:
            return node
        i = post.index(pre[1])
        node.left = self.constructFromPreorderPostorder(pre[1:i + 2], post[:i + 1])
        node.right = self.constructFromPreorderPostorder(pre[i + 2:], post[i + 1:-1])
        return node
    def preorderTraversal(self, root: TreeNode) -> List[str]:
        def preorder(root: TreeNode):
            if not root:
                return
            res.append(root.val)
            preorder(root.left)
            preorder(root.right)
        res = list()
        preorder(root)
        return res
    def inorderTraversal(self, root: TreeNode) -> List[str]:
        def preorder(root: TreeNode):
            if not root:
                return
            preorder(root.left)
            res.append(root.val)
            preorder(root.right)
        res = list()
        preorder(root)
        return res
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        def postorder(root: TreeNode):
            if not root:
                return
            postorder(root.left)
            postorder(root.right)
            res.append(root.val)
        res = list()
        postorder(root)
        return res
a = ['A', 'B', 'F', 'C', 'D', 'E']  #前序样子
b = ['F', 'B', 'A', 'D', 'C', 'E']  #中序样子
c = ['F', 'B', 'D', 'E', 'C', 'A']  #后序样子
onexianxu=Solution().buildTreeFromInorderPostorder(b,c)
print('先序',Solution().preorderTraversal(onexianxu))
onezhong=Solution().constructFromPreorderPostorder(a, c)
print('中序',Solution().inorderTraversal(onezhong))
onehouxu=Solution().buildTreeFromPreorderInorder(a,b)
print('后序',Solution().postorderTraversal(onehouxu))
```

python 105. 从前序与中序遍历序列构造二叉树 106. 从中序与后序遍历序列构造二叉树 108. 根据前序和后序遍历构造二叉树

开始自己写了一个全排列，不优雅。





python有全排列的系统库：

> from itertools import permutations

题目描述

> 计算24点是一种扑克牌益智游戏，随机抽出4张扑克牌，通过加(+)，减(-)，乘(*),

> 除(/)四种运算法则计算得到整数24，本问题中，扑克牌通过如下字符或者字符串表示，其中，小写joker表示小王，大写JOKER表示大王： 

> 

>                    3 4 5 6 7 8 9 10 J Q K A 2 joker JOKER

> 

> 本程序要求实现：输入4张牌，输出一个算式，算式的结果为24点。 

> 

> 详细说明： 

> 

> 1.运算只考虑加减乘除运算，没有阶乘等特殊运算符号，友情提醒，整数除法要当心； 

> 2.牌面2~10对应的权值为2~10, J、Q、K、A权值分别为为11、12、13、1； 

> 3.输入4张牌为字符串形式，以一个空格隔开，首尾无空格；如果输入的4张牌中包含大小王，则输出字符串“ERROR”，表示无法运算； 

> 4.输出的算式格式为4张牌通过+-*/四个运算符相连，中间无空格，4张牌出现顺序任意，只要结果正确； 

> 5.输出算式的运算顺序从左至右，不包含括号，如1+2+3*4的结果为24

> 6.如果存在多种算式都能计算得出24，只需输出一种即可，如果无法得出24，则输出“NONE”表示无解。


python

```python
# 思路：对所有数字全排列，计算每种排列能否凑成24（题目默认按照先后顺序计算，即（(a+b)+c))+d模式。
# 如果joker 或 JOKER 在输入序列中，返回ERROR
# 当有一个满足的解时，返回；遍历完所有排列，如果没有满足的解，返回NONE
from itertools import permutations
while True:
    try:
        def check(exp):  # 为了排除中间/0的情况，并且若等式值为24，返回True
            try:
                return int(eval(exp) == 24)
            except:
                return False
        def game24(pokers):
            dic = {'A': '1', '2': '2', '3': '3', '4': '4', '5': '5', '6': '6', '7': '7', '8': '8', '9': '9', '10': '10',
                   'J': '11', 'Q': '12', 'K': '13'}
            ops = r'+-*/'
            exp = '((%s %s %s) %s %s )%s %s'  ## 这道题默认括号是这么加的
            for a in permutations(pokers):  ## nums 的全排列
                for op1 in ops:
                    for op2 in ops:
                        for op3 in ops:
                            if check(exp % (dic[a[0]], op1, dic[a[1]], op2, dic[a[2]], op3, dic[a[3]])):
                                result = a[0] + op1 + a[1] + op2 + a[2] + op3 + a[3]  ## 这题只需要求出一个满足要求的等式即可
                                return result
            return 'NONE'
        pokers = input().split(' ')
        if 'joker' in pokers or 'JOKER' in pokers:
            print('ERROR')
        else:
            print(game24(pokers))
    except:
        break
```

24点游戏的暴力美学

[https://blog.csdn.net/darkrabbit/article/details/89409548](https://blog.csdn.net/darkrabbit/article/details/89409548)






（1） 出栈序列共有多少种可能？

（2） 求出所有出栈（入栈）序列。

（3） 给出一个出栈序列，问栈的容量最少需要多少？

（4） 给出一个（或多个）出栈序列，问此序列是不是（哪一个序列不是）原序列混洗得到的？


![在这里插入图片描述](/static/img/images/00970.png)

python

题目描述

给定一个正整数N代表火车数量，0<N<10，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9编号，火车站只有一个方向进出，同时停靠在火车站的列车中，只有后进站的出站了，先进站的才能出站。

要求输出所有火车出站的方案，以字典序排序输出。
```python
while True:
    try:
        n = int(input())
        trains = [  str(1+i)  for i in range(n)]
        res = []
        def rec_trains(cur_idx, in_trains, out_trains):
            # 如果原始火车列表的最后一个元素已经进站，此时只能出站，将入站列表中的火车倒序加入出站火车中
            if trains[-1] in in_trains:
                res.append(' '.join(out_trains + in_trains[::-1]))
                return
            # 如果进站列表为空，此时只能进站，进站列表加上当前火车，出站列表不变
            elif in_trains == []:
                rec_trains(cur_idx + 1, in_trains + [trains[cur_idx]], out_trains)
            # 否则，就既有可能进站也有可能出站
            else:
                # 出站，当前火车索引不变，进站火车列表减去最后一个元素，出站列表加上进站列表刚刚出站的火车
                rec_trains(cur_idx, in_trains[:-1], out_trains + [in_trains[-1]])
                # 进站，当前火车索引加1，进站列表加上当前火车，出站列表不变
                rec_trains(cur_idx + 1, in_trains + [trains[cur_idx]], out_trains)
        rec_trains(0, [], [])
        res.sort()
        print(len(res))
    except:
        break
```

数据结构 栈混洗 个数 Stack Shuffling 卡特兰数

介绍：





[https://www.cnblogs.com/frankchenfu/p/7107019.html](https://www.cnblogs.com/frankchenfu/p/7107019.html)

应用

![在这里插入图片描述](/static/img/images/00971.png)

```python
import bisect
def max_order(lists):
    list_num = []
    list_max = []
    for i in lists:
        # bisect_left把i插入list_num，使得list_num还是升序，返回index。insort才是就地插入
        local = bisect.bisect_left(list_num, i)
        if local == len(list_num):  # 最后一个
            list_num.append(i)  # 最大值放最后
            list_max.append(local + 1)  # 记录每个元素插在哪个位置了
        else:
            list_num[local] = i  # 不是最大就替换，给后面更多机会
            list_max.append(local + 1)  # 记录每个元素插在哪个位置了
    return list_max
while True:
    try:
        people_num = int(input())
        height_list = list(map(int, input().split()))
        result_1 = max_order(height_list)  # 升序最长
        result_2 = max_order(height_list[::-1])[::-1]  # 降序最长
        print(people_num - max(map(sum, zip(result_1, result_2))) + 1)
    except BaseException as er:
        # print("fault line is", er.__traceback__.tb_lineno)
        break
```

输入

8

186 186 150 200 160 130 197 200

最后

result_1 

[1, 1, 1, 2, 2, 1, 3, 4]

result_2 

[3, 3, 2, 3, 2, 1, 1, 1]

所以要出队这么多人：

4

【算法题目】最长上升子序列 合唱队形 【动态规划】

推荐阅读：





百度百科：[https://baike.baidu.com/item/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/2416931?fr=aladdin#reference-\[9\]-841810-wrap](https://baike.baidu.com/item/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/2416931?fr=aladdin#reference-%5B9%5D-841810-wrap)

java实现：[https://blog.csdn.net/Cobbyer/article/details/108127742](https://blog.csdn.net/Cobbyer/article/details/108127742)

计算机常用算法与程序设计案例教程： [https://max.book118.com/html/2019/0122/6053000055002003.shtm](https://max.book118.com/html/2019/0122/6053000055002003.shtm)

知乎：[https://zhuanlan.zhihu.com/p/93857890](https://zhuanlan.zhihu.com/p/93857890)

## 1 0-1背包

![在这里插入图片描述](/static/img/images/00972.png)

对于输入

4件物品  背包能承受的最大重量为10

单体重量2  单体价值1

单体重量3  单体价值3

...
```python
4 10
1 1
3 3
4 5
7 9
```

动态规划：
```python
numandweight = list(map(int, input().split(' ')))  # 读取输入
N = numandweight[0]  # N件物品
V = numandweight[1]  # 背包能承受的最大重量为V
w = [0]  # 第一个元素无用  单体重量
c = [0]  # 第一个元素无用  单体价值
for i in range(N):
    temp = list(map(int, input().split(' ')))  # 读取输入
    w.append(temp[0])
    c.append(temp[1])
# 创建二维list
dp = []
for i in range(N + 1):
    dp.append([])
    for j in range(V + 1):
        dp[i].append(0)
for i in range(1, N + 1):  # 表示当前有第i个物品可以拿
    for j in range(1, V + 1):  # 表示当前背包的容量为j
        if j < w[i]:  # 如果当前背包容量j放不下重量为w[i]的物体
            dp[i][j] = dp[i - 1][j]  # 不拿 i 物品，此时背包价值依旧等于成功拿了上一个物体时的价值
        else:
            # 背包装得下，但是考虑一下值不值得拿，比较一下拿了和没拿前后背包价值的变化，取最大的方法
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i])
# 打印二维list
for i in range(len(dp)):
    print(dp[i])
```

输出dp：

```python
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 1, 3, 4, 4, 4, 4, 4, 4, 4]
[0, 1, 1, 3, 5, 6, 6, 8, 9, 9, 9]
[0, 1, 1, 3, 5, 6, 6, 9, 10, 10, 12]
```

dp表中每一个dp[i]的值只与dp[i-1]有关系，即后无效性原则。

 `dp[i][j]`表示前`i`件物品恰放入一个容量为`j`的背包可以获得的最大价值。

 `dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i])` 表示 考虑一下值不值得拿，比较一下拿了和没拿前后背包价值的变化，取最大的方法。

 整个dp只有最终的`dp[N][V]` 有意义，其他数据都是为了求出`dp[N][V]` 而做的变化。

改进代码：

```python
numandweight = list(map(int, input().split(' ')))  # 读取输入
N = numandweight[0]  # N件物品
V = numandweight[1]  # 背包能承受的最大重量为V
w = [0]  # 第一个元素无用  单体重量
c = [0]  # 第一个元素无用  单体价值
for i in range(N):
    temp = list(map(int, input().split(' ')))  # 读取输入
    w.append(temp[0])
    c.append(temp[1])
dp = [0 for i in range(V + 1) ]
for i in range(1, N + 1):  # 表示当前有第i个物品可以拿
    for j in range(V, 0, -1):  # 从后往前推
        if j >= w[i]:  # 如果当前背包容量j 可以放下 重量为w[i]的物体
            dp[j] = max(dp[j], dp[j - w[i]] + c[i])
    print(dp)
```

## 2 完全背包

问题描述：给定 N 种物品每种物品**都有无限件可用**，物品的重量为 w[i]，物品的价值为 c[i]。现挑选物品放入背包中，假定背包能承受的最大重量为 V，问应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

```python
numandweight = list(map(int, input().split(' ')))  # 读取输入
N = numandweight[0]  # N件物品
V = numandweight[1]  # 背包能承受的最大重量为V
w = [0]  # 第一个元素无用  单体重量
c = [0]  # 第一个元素无用  单体价值
for i in range(N):
    temp = list(map(int, input().split(' ')))  # 读取输入
    w.append(temp[0])
    c.append(temp[1])
# 创建二维list
dp = []
for i in range(N + 1):
    dp.append([])
    for j in range(V + 1):
        dp[i].append(0)
for i in range(1, N + 1):  # 表示当前有第i个物品可以拿
    for v in range(1, V + 1):  # 表示当前背包的容量为j
        dp[i][v]=0
        # 最多可以放nCount个物品i
        nCount = v // w[i]
        # 和01背包的区别就在这里，01
        # 背包只有两种状态：放与不放
        # 而完全背包可以放0到k个物品i，同样是取最大值
        for k in range(nCount+1):
            dp[i][v] = max(dp[i][v], dp[i - 1][v - k * w[i]] + k * c[i]) 
# 打印二维list
for i in range(len(dp)):
    print(dp[i])
```

输入：

```python
4 5
1 2
2 4
3 4
4 5
```

输出

```python
[0, 0, 0, 0, 0, 0]
[0, 2, 4, 6, 8, 10]
[0, 2, 4, 6, 8, 10]
[0, 2, 4, 6, 8, 10]
[0, 2, 4, 6, 8, 10]
```

## 3 多重背包

问题描述：给定 N 种物品每种物品 i 都有 s[i] 件可用，物品的重量为 w[i]，物品的价值为 c[i]。现挑选物品放入背包中，假定背包能承受的最大重量为 V，问应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

```python
numandweight = list(map(int, input().split(' ')))  # 读取输入
N = numandweight[0]  # N件物品
V = numandweight[1]  # 背包能承受的最大重量为V
w = [0]  # 第一个元素无用  单体重量
c = [0]  # 第一个元素无用  单体价值
s = [0]  # 第一个元素无用  有多少件
for i in range(N):
    temp = list(map(int, input().split(' ')))  # 读取输入
    w.append(temp[0])
    c.append(temp[1])
    s.append(temp[2])
# 创建二维list
dp = []
for i in range(N + 1):
    dp.append([])
    for j in range(V + 1):
        dp[i].append(0)
for i in range(1, N + 1):  # 表示当前有第i个物品可以拿
    for j in range(V,-1,-1 ):  # 表示当前背包的容量为j
        for k in range(0, s[i] + 1):
            if j>=k * w[i]:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[i]] + k * c[i])
# 打印二维list
for i in range(len(dp)):
    print(dp[i])
```

输入

```python
4 5
1 2 3
2 4 1
3 4 3
4 5 2
```

输出

```python
[0, 0, 0, 0, 0, 0]
[0, 2, 4, 6, 6, 6]
[0, 2, 4, 6, 8, 10]
[0, 2, 4, 6, 8, 10]
[0, 2, 4, 6, 8, 10]
```

背包问题 python 【动态规划】

环形链表  [https://leetcode-cn.com/problems/linked-list-cycle/](https://leetcode-cn.com/problems/linked-list-cycle/)





[https://www.cxyxiaowu.com/647.html](https://www.cxyxiaowu.com/647.html)

设置两个指针，一个每次走一步的慢指针和一个每次走两步的快指针。

如果不含有环，跑得快的那个指针最终会遇到 null，说明链表不含环

如果含有环，快指针会超慢指针一圈，和慢指针相遇，说明链表含有环。

![在这里插入图片描述](/static/img/images/01012.gif)

python
```python
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head or not head.next:
            return False  #空链表 或者 链表元素个数小于等于2
        #快慢指针
        slow = head
        fast = head.next
        while slow != fast:
            if not fast or not fast.next:  #快指针遇到null
                return False
            slow = slow.next
            fast = fast.next.next
        return True
a=ListNode(1)
b=ListNode(2)
c=ListNode(3)
d=ListNode(4)
a.next=b
b.next=c
c.next=d
d.next=b
print(Solution().hasCycle(a))
```

![在这里插入图片描述](/static/img/images/01013.png)

![在这里插入图片描述](/static/img/images/01014.png)

```python
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return None  # 空链表 或者 链表元素个数小于等于2
        # 快慢指针
        slow = head
        fast = head
        while (fast is not None):
            slow = slow.next
            if (fast.next is None):
                return None
            fast = fast.next.next
            if fast is slow:
                ptr = head
                while (ptr is not slow):
                    ptr = ptr.next
                    slow = slow.next
                return ptr
        return None
a = ListNode(1)
b = ListNode(2)
c = ListNode(3)
d = ListNode(4)
a.next = b
b.next = c
c.next = d
d.next = b
print(Solution().detectCycle(a).val)
```

141. 环形链表 142. 环形链表 II 使用快慢指针求解「环形链表」

[https://leetcode-cn.com/problems/trapping-rain-water/](https://leetcode-cn.com/problems/trapping-rain-water/)





![在这里插入图片描述](/static/img/images/01113.png)

动态编程

```python
from typing import List
class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        ans = 0
        size = len(height)
        left_max = [0] * size
        right_max = [0] * size
        # 从左到右看最高
        left_max[0] = height[0]
        for i in range(1, size):
            left_max[i] = max(height[i], left_max[i - 1])
        # 从右到左看最高
        right_max[size - 1] = height[size - 1]
        for i in range(size - 2, -1, -1):
            right_max[i] = max(height[i], right_max[i + 1])
        # 累加
        for i in range(1, size):
            ans += min(left_max[i], right_max[i]) - height[i]  # 本身有的一定高度需要减去
        return ans
print(Solution().trap([4, 2, 0, 3, 2, 5]))
```

双指针

```python
from typing import List
class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        ans = 0
        size = len(height)
        left = 0
        right = size - 1
        left_max = 0
        right_max = 0
        while (left < right):
            if height[left] < height[right]:
                if height[left] >= left_max:
                    left_max = height[left]
                else:
                    ans += (left_max - height[left])
                left += 1
            else:
                if height[right] >= right_max:
                    right_max = height[right]
                else:
                    ans += (right_max - height[right])
                right -= 1
        return ans
print(Solution().trap([4, 2, 0, 3, 2, 5]))
```

42. 接雨水 动态编程 双指针

![在这里插入图片描述](/static/img/images/01121.png)





```python
from typing import List
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        dp = []
        for i in range(len(nums)):
            dp.append(1)
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return len(dp)
print(Solution().lengthOfLIS([3, 2, 1, 1, 2]))
```

![在这里插入图片描述](/static/img/images/01122.png)

```python
from typing import List
from bisect import bisect_left
class Solution:
    def maxEnvelopes(self, arr: List[List[int]]) -> int:
        # sort increasing in first dimension and decreasing on second
        arr.sort(key=lambda x: (x[0], -x[1]))
        def lis(nums):
            dp = []
            for i in range(len(nums)):
                idx = bisect_left(dp, nums[i])
                if idx == len(dp):
                    dp.append(nums[i])
                else:
                    dp[idx] = nums[i]
            return len(dp)
        # extract the second dimension and run the LIS
        return lis([i[1] for i in arr])
print(Solution().maxEnvelopes([[5,4],[6,4],[6,7],[2,3]]))
```

300. 最长上升子序列（动态规划） 354. 俄罗斯套娃信封问题

![在这里插入图片描述](/static/img/images/01125.png)





```python
from typing import List
class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        SEG_COUNT = 4
        ans = list()
        segments = [0] * SEG_COUNT
        def dfs(segId: int, segStart: int):
            # 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
            if segId == SEG_COUNT:
                if segStart == len(s):
                    ipAddr = ".".join(str(seg) for seg in segments)
                    ans.append(ipAddr)
                return
            # 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
            if segStart == len(s):
                return
            # 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
            if s[segStart] == "0":
                segments[segId] = 0
                dfs(segId + 1, segStart + 1)
            # 一般情况，枚举每一种可能性并递归
            addr = 0
            for segEnd in range(segStart, len(s)):
                addr = addr * 10 + (ord(s[segEnd]) - ord("0"))
                if 0 < addr <= 0xFF:
                    segments[segId] = addr
                    dfs(segId + 1, segEnd + 1)
                else:
                    break
        dfs(0, 0)
        return ans
print(Solution().restoreIpAddresses("010010"))
```

93. 复原IP地址 （递归+回溯 ）

![在这里插入图片描述](/static/img/images/01126.png)






```python
from typing import List
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return list()
        phoneMap = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }
        def backtrack(index: int):
            if index == len(digits):
                combinations.append("".join(combination))
                return
            digit = digits[index]
            for letter in phoneMap[digit]:
                combination.append(letter)
                backtrack(index + 1)
                combination.pop()
        combination = list()
        combinations = list()
        backtrack(0)
        return combinations
print(Solution().letterCombinations("234"))
```