代码随想录27期|Python|Day30|回溯算法|332.重新安排行程|51. N皇后|37. 解数独

本篇题目理解即可。

332.?重新安排行程

本题需要理解题意：给出的每一个ticket实际上是边，每一个元素是节点，所以实际上是一个深度优先问题。如果使用回溯的话，和之前的排列是属于一个类型，但是中间的判断稍微不同。

1.模版写法（used数组）

1、参数和返回值：参数和排列问题基本一致，path保存的是节点，加入了used数组，深度伴随，还需要传入上一层的目的地用来判断衔接；返回值是bool类型，因为找到一个就可以返回

2、终止条件：需要走过“使用过”全部的机票，也就是经历全部的边，也就是节点数==边数+1即可，此时将path添加到res，返回一个True表明找到了一条满足条件的

3、中间层处理：需要注意的是如何取出节点并使之衔接。tickets的每一个数组对表示的是[出发点，目的地]，也就是说除了用used判断这张ticket使用过以外，还需要判断当前的出发点是否就是上一层的目的地

class Solution(object):
    def findItinerary(self, tickets):
        """
        :type tickets: List[List[str]]
        :rtype: List[str]
        """
        tickets.sort()  # 先排序，保证找到的第一个就是最小的字典序
        res = []
        cur = "JFK"
        path = ["JFK"]
        used = [0] * len(tickets)
        self.backtracking(tickets, res, path, cur, used)
        return res[0]

    def backtracking(self, tickets, res, path, cur, used):
        if len(path) == len(tickets) + 1:
            res.append(path[:])
            return True

        for i, ticket in enumerate(tickets):
            if used[i] == 0 and ticket[0] == cur:  # 当前机票没用而且现在机票的出发点是上一层传入的目的地
                used[i] = 1
                path.append(ticket[1])
                find_route = self.backtracking(tickets, res, path, ticket[1], used)
                path.pop()
                used[i] = 0
                if find_route:  # 只要找到一个True的路径，一直往上返回即可
                    return True

2.字典写法（顺序遍历）

但是这样的写法比较容易超时，可以使用defaultdict来储存“出发点：目的地1，目的地2...”。

?此外有一些defaultdict的使用细节需要注意。

class Solution(object):
    def findItinerary(self, tickets):
        """
        :type tickets: List[List[str]]
        :rtype: List[str]
        """
        # 构造“出发地：目的地1，目的地2...”
        targets = defaultdict(list)
        for ticket in tickets:
            targets[ticket[0]].append(ticket[1])  # 添加每一个出发地的目的地
        for start_point in targets:
            targets[start_point].sort()  # 对目的地进行排序
        res = []
        path = ["JFK"]
        ticket_num = len(tickets)
        self.backtracking(res, path, targets, ticket_num)
        return res[0]

    def backtracking(self, res, path, targets, ticket_num):
        if len(path) == ticket_num + 1:  # 等价于tickets的长度
            res.append(path[:])
            return True

        cur_airport = path[-1]  # 获取上一个机场
        destinations = targets[cur_airport]  # 获取它的全部目的地
        for i, destination in enumerate(destinations):
            targets[cur_airport].pop(i)  # 直接在targets里弹出
            path.append(destination)
            self.backtracking(res, path, targets, ticket_num)
            targets[cur_airport].insert(i, destination)
            path.pop()
        return False

3.字典写法（逆序入栈）

以上两种方法都是存在会爆内存或者运行时间超了，所以需要一个更高效的算法，介绍一下Hierholzer方法：逆序入栈。

本题可以归类于一个“欧拉图”，也就是求解一个一笔画问题。

那么，什么时候一笔画会终止？显然是遇到“死胡同”的时候，也就是对于一个节点（飞机场），它的进入边和输出边都是1，也即这个点只能走一次，所以如果存在死胡同，必然是它导致的（但不是这个点）

什么是“逆序入栈”？也就是先遍历，后入栈。先遍历节点的全部分枝之后，再把这个点加入栈中。显然，这里需要while来判断是否穷尽了节点所有的边。输出的时候也是逆序打印。

class Solution(object):
    def findItinerary(self, tickets):
        """
        :type tickets: List[List[str]]
        :rtype: List[str]
        """
        targets = defaultdict(list)
        for ticket in tickets:
            targets[ticket[0]].append(ticket[1])
        for depart in targets:
            targets[depart].sort(reverse = True)  # 目的地按照字典逆序保存是为了后面逆序输出的时候按照字典序输出
        res = []
        self.backtracking("JFK", targets, res)
        return res[::-1]
    
    def backtracking(self, cur_airport, targets, res):
        # 在当前节点的全部目的地没有被遍历完的时候，是不会加入该节点的
        while targets[cur_airport]:
            # 依次弹出目的地
            next_airport = targets[cur_airport].pop()  # 字典支持在循环中进行修改
            # dfs进入下一层递归（此时res还没有加入新的节点）
            self.backtracking(next_airport, targets, res)
        res.append(cur_airport)

51.?N 皇后

?形式上更像是一个模拟题，其中涉及到对于字符串的编辑操作。

1、确定返回值和参数：传入要修改的棋盘（相当于path），res，和棋盘大小n，由于是输出全部的方案，所以不需要返回值

2、终止条件：传入的row到了边界值n（row从0开始，但是传入下一层是+1的，所以是和n比较）

3、中间处理：按照行来回溯，每层按列遍历，先判断位置是否合法，再回溯

判断位置的函数需要判断三个位置：当前列、左上方45度、右上方45度。

class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        # 创建棋盘
        chessboard = ['.' * n for _ in range(n)]
        res =[]
        self.backtracking(0, res, chessboard, n)
        return res
    
    def backtracking(self, row, res, chessboard, n):
        # 终止条件：传入的row等于棋盘行数n
        if row == n:
            res.append(chessboard[:])
            return
        # 按照行来处理
        # 每行遍历列
        for col in range(n):
            # 满足条件进入递归
            if self.is_valid(chessboard, row, col, n):
                # 注意字符串修改的方式
                chessboard[row] = chessboard[row][:col] + 'Q' + chessboard[row][col+1:]
                self.backtracking(row + 1, res, chessboard, n)
                chessboard[row] = chessboard[row][:col] + '.' + chessboard[row][col+1:]  # 回溯
    
    def is_valid(self, chessboard, row, col, n):
        # 情况一：上方的行对应列有Q
        for i in range(row):
            if chessboard[i][col] == 'Q':
                return False
        # 情况二：左上方45度有Q
        i = row - 1
        j = col - 1
        while i >= 0 and j >= 0:
            if chessboard[i][j] == 'Q':
                return False
            i -= 1
            j -= 1
        # 情况三：右上方45度有Q
        i = row - 1
        j = col + 1
        while i >= 0 and j < n:
            if chessboard[i][j] == 'Q':
                return False
            i -= 1
            j += 1

        return True

?37.?解数独

和上面N皇后有一些区别，本题需要二维遍历（上面只要固定row找col就可以了）。此外每一个空都需要1～9遍历来尝试。

1、返回值和参数：由于是找到一个就返回，所以返回值是bool（本题需要注意True在False的外面，因为True是整个图都填完才可以向上返回，但是False是1～9没有返回True，也就是无法填返回的）

2、终止条件：终止条件是在没有return False的情况下走完了整个图（没有找到空位了，跳出循环），所以在叶子节点向上返回True

3、中间层操作：在每一行、每一列遍历，找到空位在1～9遍历是否合适，遇到合适的进入递归，没有的进入上一层，同时回溯

关于判断该位置数字是否合适的函数，有三个位置：

（1）行（2）列（3）九宫格（这里特别需要注意左上角起点坐标的获取方式）

class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: None Do not return anything, modify board in-place instead.
        """
        # 规定没有返回值，所以只要修改参数即可
        self.backtracking(board)
    
    def backtracking(self, board):
        # 进两层遍历（行列）
        for row in range(len(board)):
            for col in range(len(board)):
                if board[row][col] != '.':  # 如果当前是空，进入填充
                    continue
                for i in range(1, 10):  # 每个位置都用1～9尝试
                    if self.is_valid(board, row, col, i):  # 满足条件进递归
                        board[row][col] = str(i)
                        if self.backtracking(board):
                            return True  # 上一层True一直往上返回
                        board[row][col] = '.'  # 不满足回溯
                return False
        # 由于只有唯一解，所以找到就可以返回
        return True

    def is_valid(self, board, row, col, num):
        num = str(num)  # 先把num转换成字符串类型
        # 情况1：列重复
        for j in range(len(board)):
            if board[row][j] == num:
                return False
        # 情况2: 行重复
        for i in range(len(board)):
            if board[i][col] == num:
                return False
        # 情况3: 九宫格重复
        # 计算九宫格左上角坐标：整除3的商再乘以3
        start_row = (row // 3) * 3
        start_col = (col // 3) * 3
        # 行、列遍历
        for i in range(start_row, start_row + 3):
            for j in range(start_col, start_col + 3):
                if board[i][j] == num:
                    return False
        return True

第30天完结！🎉