延庆网站制作,wordpress调用不同头部文件,创建全国文明城市应知应会知识,在百度做橱柜网站332 重新安排行程
给你一份航线列表 tickets #xff0c;其中 tickets[i] [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK#xff08;肯尼迪国际机场#xff09;出发的先生#xff0c;所以该行程必须从 JFK …332 重新安排行程
给你一份航线列表 tickets 其中 tickets[i] [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK肯尼迪国际机场出发的先生所以该行程必须从 JFK 开始。如果存在多种有效的行程请你按字典排序返回最小的行程组合。
例如行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小排序更靠前。 假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
# 回溯used
def backtracking(tickets,used,path,cur,result):if len(path)len(tickets)1:result.append(path[:]) # 因为剪枝对应下面找到一个路径就返回不能return path[:]return True for i,ticket in enumerate(tickets):if ticket[0]cur and used[i]False:used[i]Truepath.append(ticket[1])statebacktracking(tickets,used,path,ticket[1],result)path.pop()used[i]Falseif state:return True # 找到一个路径就行不需要再搜索
def findItinerary(tickets:List[List[str]])-List[str]:tickets.sort() #字母小的排在前面used[False]*len(tickets)path[JFK]result[]backtracking(tickets,used,path,JKF,result):return result[0]# 回溯字典
# 待搞懂
def findItinerary(tickets):targetdefaultdict(list)for ticket in tickets:target[ticket[0]].append(ticket[1])for airport in target:target[airport].sort()path[JFK]backtracking(target,path,len(tickets))return path def backtracking(target,path,ticketNum):if len(path)ticketNum1:return Trueairportpath[-1]destinationstarget[airport]for i,dest in enumerate(destinations):target[airport].pop(i)path.append(dest)if backtracking(target,path,ticketNum):return Truetarget[airport].insert(i,dest)path.pop()return False51 N皇后
按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。
给你一个整数 n 返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
def solveNQueens(n:int)-List[List[str]]:result[]chessboard[.*n for _ in range(n)] # 原本n*n - 1*nbacktracking(n,0,chessboard,result)return [[.join(row)for row in solution]for solution in result] def backtracking(n,row,chessboard,result):if rown:result.append(chessboard[:])return for col in range(n):if isValid(row,col,chessboard):chessboard[row]chessboard[row][:col]Qchessboard[row][col1:]backtracking(n,row1,chessboard,result)chessboard[row]chessboard[row][:col].chessboard[row][col1:]def isValid(row,col,chessboard):# 是否同一列出现多个Q for i in range(row):if chessboard[i][col]Q: return False # 是否45度角出现多个Qi,jrow-1,col-1while i0 and j0:if chessboard[i][j]Q:return Falsei-1j-1# 是否135度角出现多个Qi,jrow-1,col1while i0 and jlen(chessboard):if chessboard[i][j]Q:return Falsei-1j1return True
37 解数独
编写一个程序通过填充空格来解决数独问题。
数独的解法需 遵循如下规则
数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。请参考示例图 数独部分空格内已填入了数字空白格用 ‘.’ 表示。
def backtracking(board)-bool:for i in range(len(board)):#行for j in range(len(board[0])):#列if board[i][j]!.:continuefor k in range(1,10):if isValid(i,j,k,board):board[i][j]str(k)if backtracking(board):return Trueboard[i][j].return False #1-9都不能成功填入无解返回Faslereturn True
def isValid(row,col,val,board)-bool:for i in range(9):if board[row][i]str(val):return Falsefor j in range(9):if board[j][col]str(val):return False# 根据row、col判断在第几个子子宫格内start_row(row//3)*3start_col(col//3)*3for i in range(start_row,start_row3):for j in range(start_col,start_col3):if board[i][j]str(val):return Falsereturn True
def solveSudoku(board:List[List[str]])-None:backtracking(board)
