Leetcode刷题第七天-回溯-哈希
332:重新岸炮行程
机场字典:{起飞机场:[到达机场的列表]}
去重:到达机场列表,i>0时,当前机场和上一个机场相等,continue
1 class Solution: 2 def findItinerary(self, tickets: List[List[str]]) -> List[str]: 3 if(not tickets): return tickets 4 targets={} 5 for i in tickets: 6 if(i[0] not in targets.keys()): targets[i[0]]=[] 7 targets[i[0]].append(i[1]) 8 for i in targets: targets[i].sort() 9 re=['JFK'] 10 self.backtracking(len(tickets),targets,re,"JFK") 11 return re 12 def backtracking(self,lens,targets,re,tic): 13 if(len(re)==lens+1): return True 14 if(tic not in targets or not targets[tic]): return False 15 for i,dest in enumerate(targets[tic]): 16 if(i>0 and dest==targets[tic][i-1]): continue 17 targets[tic].pop(i) 18 re.append(dest) 19 if(self.backtracking(lens,targets,re,dest)): return True 20 targets[tic].insert(i, dest) 21 re.pop() 22 return False
51:N皇后
for遍历行
递归列
同一列没有Q,45° 135°对角线没有Q,可以放
1 import copy 2 class Solution: 3 def solveNQueens(self, n: int) -> List[List[str]]: 4 if(not n): return [] 5 #预置棋盘,所有位置均可以放 6 path=[] 7 for i in range(n): 8 path.append(copy.deepcopy(['.']*n)) 9 re=[] 10 self.backtracking(n,re,path,0) 11 return re 12 def backtracking(self,n,re,path,startID): 13 #一次遍历完成 14 if(startID==n): 15 re.append(self.get_result(path)) 16 return 17 for i in range(n): 18 #是否可以放Q 19 if(self.isValid(startID,i,n,path)): 20 path[startID][i]='Q' 21 self.backtracking(n,re,path,startID+1) 22 #回溯棋盘 23 path[startID][i]='.' 24 25 def isValid(self,x,y,n,path): 26 #一列有Q 27 for i in range(n): 28 if('Q' == path[i][y]): return False 29 i=x-1 30 j=y-1 31 #45°对角线 32 while i>=0 and j>=0: 33 if(path[i][j]=='Q'): return False 34 i-=1 35 j-=1 36 i=x-1 37 j=y+1 38 #135°对角线 39 while i>=0 and j<n: 40 if(path[i][j]=='Q'): return False 41 i-=1 42 j+=1 43 return True 44 def get_result(self,path): 45 re=[] 46 for i in path: 47 s='' 48 for j in i: 49 s+=j 50 re.append(s) 51 return re
37:解数独
(⊙﹏⊙)双层for循环中再加一层for循环,然后居然就过了
怎么说
1 class Solution: 2 def solveSudoku(self, board: List[List[str]]) -> None: 3 """ 4 Do not return anything, modify board in-place instead. 5 """ 6 for i in range(len(board)): 7 for j in range(len(board[0])): 8 if(board[i][j]!='.'): continue 9 for k in range(1,10): 10 if(self.isValid(i,j,str(k),board)): 11 board[i][j]=str(k) 12 if self.solveSudoku(board): return True 13 board[i][j]='.' 14 return False 15 return True 16 def isValid(self,x,y,k,board): 17 #行 18 if k in board[x]: return False 19 #列 20 for i in range(9): 21 if board[i][y]==k: return False 22 xi=x-x%3 23 yj=y-y%3 24 #9宫 25 for i in range(xi,xi+3): 26 for j in range(yj,yj+3): 27 if board[i][j]==k: return False 28 return True
=================================================================================================================
不行,脑壳疼,换哈希啃啃
242:有效的字母异位词
链接:242. 有效的字母异位词 - 力扣(LeetCode)
1 class Solution: 2 def isAnagram(self, s: str, t: str) -> bool: 3 if(len(s)!=len(t)): return False 4 for i in s: 5 if s.count(i)!=t.count(i): return False 6 return True
349:两个数组的交集
链接:349. 两个数组的交集 - 力扣(LeetCode)
1 class Solution: 2 def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: 3 nums1=list(set(nums1)) 4 nums2=list(set(nums2)) 5 re=[] 6 for i in nums1: 7 if(i in nums2): re.append(i) 8 return re
202:快乐数
1 class Solution: 2 def isHappy(self, n: int) -> bool: 3 hashcode=[n] 4 sums=0 5 while True: 6 if(not n): 7 if(sums==1): return True 8 if(sums in hashcode): return False 9 hashcode.append(sums) 10 n,sums=sums,n 11 else: 12 m=n%10 13 n=n//10 14 sums+=m*m