day30| 332+51+37-526互联

332. 重新安排行程

题目简述：

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票必须都用一次且只能用一次。

思路

1. 利用字典储存所有路线

2. 每选择一条路线，就删除字典中的对应路线，看最后能否遍历完所有路线

3. 如果不能，就回溯；能就返回True

4. 字典序排序的实现使用sort函数实现，在选择路线的时候，优先选择排序后，靠前的路线

代码如下：

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        tree = {}
        total = len(tickets) # 总共有多少条航线（几张机票）
        # 生成一个字典 key是起飞机场，val是key可以到达的机场
        for airline in tickets:
            start = airline[0]
            end = airline[1]
            if start in tree:
                tree[start].append(end)
            else:
                tree[start] = [end]
        
        # 始发机场一定是JFK
        ans = ['JFK']
        # 开始 DFS
        def dfs(total,start='JFK'):
            # 如果剩余航线，即行程图没有边剩下，即可获得结果
            if total == 0:  # no ticket left
                return True
            # 如果还有行乘没有走完
            # 且当前start是一个起飞机场，即有航线是从这里起飞
            if start in tree:
                # 字典序排序  
                tree[start].sort()
                # 从起飞机场选择一个 落地机场降落
                for _ in tree[start]:
                    # 处理落地机场
                    end = tree[start].pop(0)
                    ans.append(end)
                    total -= 1
                    # 如果飞到当前落地机场，能完成所有行乘
                    if dfs(total,end):
                        return True
                    # 如果飞到当前落地机场，不能完成所有行乘
                    # 回溯当前落地机场
                    else:
                        total += 1
                        ans.pop()
                        tree[start].append(end)
            return False

        dfs(total)
        return ans

51. N皇后

题目简述

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

思路：

1. 设计一个函数专门判断当前位置是否可行，可以放皇后

2. 设计一个函数存储解法

3. 设计一个回溯函数不断row+1往深层走，再回溯

代码如下：

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        checkerboard=[0 for _ in range(n)]
        res=[]

        # 检查当前位置是否可行
        def check(row,column):
            # 遍历之前的行
            for row_p in range(row):
                # 检查是否在同一列
                if checkerboard[row_p]==column:
                    return False
                # 检查右上方是否有，行数+列数的值是否相等
                if checkerboard[row_p]+row_p==row+column:
                    return False
                # 检查左上方是否有,行数的差值与列数的差值是否相等
                if row-row_p==column-checkerboard[row_p]:
                    return False
            return True
        
        def draw_q(k):
            arr=[]
            for i in range(k-1):
                arr.append('.')
            arr.append('Q')
            for i in range(k,n):
                arr.append('.')
            return ''.join(i for i in arr)
        
        def dfs(checkerboard,row,path):
            if row==n:
                res.append(path[:])
                return
            
            for col in range(n):
                if check(row,col):
                    tmp=draw_q(col+1)
                    checkerboard[row]=col
                    path.append(tmp)
                    dfs(checkerboard,row+1,path)
                    path.pop()
                    checkerboard[row]=0
            return

        dfs(checkerboard,0,[])
        return res

关键难点在判断当前位置是否可行上面

37. 解数独

题目简述：

编写一个程序，通过填充空格来解决数独问题。

数独的解法需遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。

思路：

1. 用line[i]，column[j]，block[x][y]分别表示第i行，第j列，第（x,y）给九宫格中填写数字的情况。

2. 九宫格的范围为0<=x<=2，以及0<=y<=2

3. 也即第i行，第j列的各自位于第（[i/3],[j/3]）个九宫格中，其中[]表示向下取整

代码如下

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        def dfs(pos: int):
            nonlocal valid
            if pos == len(spaces):
                valid = True
                return
            
            i, j = spaces[pos]
            for digit in range(9):
                if line[i][digit] == column[j][digit] == block[i // 3][j // 3][digit] == False:
                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True
                    board[i][j] = str(digit + 1)
                    dfs(pos + 1)
                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = False
                if valid:
                    return
            
        line = [[False] * 9 for _ in range(9)]
        column = [[False] * 9 for _ in range(9)]
        block = [[[False] * 9 for _a in range(3)] for _b in range(3)]
        valid = False
        spaces = list()

        for i in range(9):
            for j in range(9):
                if board[i][j] == ".":
                    spaces.append((i, j))
                else:
                    digit = int(board[i][j]) - 1
                    line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True

        dfs(0)

dayos_day dayos day 30