卖小女孩的火柴 发表于 2024-2-1 17:34:15

Leetcode刷题第七天-回溯-哈希

332:重新岸炮行程
链接:332. 重新安排行程 - 力扣(LeetCode)
机场字典:{起飞机场:[到达机场的列表]}
去重:到达机场列表,i>0时,当前机场和上一个机场相等,continue
1 class Solution:
2   def findItinerary(self, tickets: List]) -> List:
3         if(not tickets):   return tickets
4         targets={}
5         for i in tickets:
6             if(i not in targets.keys()): targets]=[]
7             targets].append(i)
8         for i in targets: targets.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): return False
15         for i,destin enumerate(targets):
16             if(i>0 and dest==targets):    continue
17             targets.pop(i)
18             re.append(dest)
19             if(self.backtracking(lens,targets,re,dest)):    return True
20             targets.insert(i, dest)
21             re.pop()
22         return FalsefindItinerary51:N皇后
链接:51. N 皇后 - 力扣(LeetCode)
for遍历行
递归列
同一列没有Q,45°    135°对角线没有Q,可以放
1 import copy
2 class Solution:
3   def solveNQueens(self, n: int) -> List]:
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='Q'
21               self.backtracking(n,re,path,startID+1)
22               #回溯棋盘
23               path='.'
24
25   def isValid(self,x,y,n,path):
26         #一列有Q
27         for i in range(n):
28             if('Q' == path): return False
29         i=x-1
30         j=y-1
31         #45°对角线
32         while i>=0 and j>=0:
33             if(path=='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=='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 resolveSudoku=================================================================================================================
不行,脑壳疼,换哈希啃啃

 242:有效的字母异位词
链接:242. 有效的字母异位词 - 力扣(LeetCode)
1 class Solution:
2   def solveSudoku(self, board: List]) -> 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)):
8               if(board!='.'):   continue
9               for k in range(1,10):
10                     if(self.isValid(i,j,str(k),board)):
11                         board=str(k)
12                         if self.solveSudoku(board):    return True
13                         board='.'
14               return False
15         return True
16   def isValid(self,x,y,k,board):
17         #行
18         if k in board:   return False
19         #列
20         for i in range(9):
21             if board==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==k:return False
28         return TrueisAnagram349:两个数组的交集
链接:349. 两个数组的交集 - 力扣(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 Trueintersection202:快乐数
链接:202. 快乐数 - 力扣(LeetCode)
1 class Solution:
2   def intersection(self, nums1: List, nums2: List) -> List:
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 reisHappy 

来源:https://www.cnblogs.com/xiaoruru/p/18001692
免责声明:由于采集信息均来自互联网,如果侵犯了您的权益,请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容,谢谢合作!
页: [1]
查看完整版本: Leetcode刷题第七天-回溯-哈希