翼度科技»论坛 编程开发 python 查看内容

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

4

主题

4

帖子

12

积分

新手上路

Rank: 1

积分
12
332:重新岸炮行程
链接:332. 重新安排行程 - 力扣(LeetCode)
机场字典:{起飞机场:[到达机场的列表]}
去重:到达机场列表,i>0时,当前机场和上一个机场相等,continue
  1. 1 class Solution:
  2. 2     def findItinerary(self, tickets: List[List[str]]) -> List[str]:
  3. 3         if(not tickets):   return tickets
  4. 4         targets={}
  5. 5         for i in tickets:
  6. 6             if(i[0] not in targets.keys()): targets[i[0]]=[]
  7. 7             targets[i[0]].append(i[1])
  8. 8         for i in targets: targets[i].sort()
  9. 9         re=['JFK']
  10. 10         self.backtracking(len(tickets),targets,re,"JFK")
  11. 11         return re
  12. 12     def backtracking(self,lens,targets,re,tic):
  13. 13         if(len(re)==lens+1):    return True
  14. 14         if(tic not in targets or not targets[tic]): return False
  15. 15         for i,dest  in enumerate(targets[tic]):
  16. 16             if(i>0 and dest==targets[tic][i-1]):    continue
  17. 17             targets[tic].pop(i)
  18. 18             re.append(dest)
  19. 19             if(self.backtracking(lens,targets,re,dest)):    return True
  20. 20             targets[tic].insert(i, dest)
  21. 21             re.pop()
  22. 22         return False
复制代码
findItinerary51:N皇后
链接:51. N 皇后 - 力扣(LeetCode)
for遍历行
递归列
同一列没有Q,45°    135°对角线没有Q,可以放
  1. 1 import copy
  2. 2 class Solution:
  3. 3     def solveNQueens(self, n: int) -> List[List[str]]:
  4. 4         if(not n):  return []
  5. 5         #预置棋盘,所有位置均可以放
  6. 6         path=[]
  7. 7         for i in range(n):
  8. 8             path.append(copy.deepcopy(['.']*n))
  9. 9         re=[]
  10. 10         self.backtracking(n,re,path,0)
  11. 11         return re
  12. 12     def backtracking(self,n,re,path,startID):
  13. 13         #一次遍历完成
  14. 14         if(startID==n):
  15. 15             re.append(self.get_result(path))
  16. 16             return
  17. 17         for i in range(n):
  18. 18             #是否可以放Q
  19. 19             if(self.isValid(startID,i,n,path)):
  20. 20                 path[startID][i]='Q'
  21. 21                 self.backtracking(n,re,path,startID+1)
  22. 22                 #回溯棋盘
  23. 23                 path[startID][i]='.'
  24. 24
  25. 25     def isValid(self,x,y,n,path):
  26. 26         #一列有Q
  27. 27         for i in range(n):
  28. 28             if('Q' == path[i][y]): return False
  29. 29         i=x-1
  30. 30         j=y-1
  31. 31         #45°对角线
  32. 32         while i>=0 and j>=0:
  33. 33             if(path[i][j]=='Q'):  return False
  34. 34             i-=1
  35. 35             j-=1
  36. 36         i=x-1
  37. 37         j=y+1
  38. 38         #135°对角线
  39. 39         while i>=0 and j<n:
  40. 40             if(path[i][j]=='Q'):  return False
  41. 41             i-=1
  42. 42             j+=1
  43. 43         return True
  44. 44     def get_result(self,path):
  45. 45         re=[]
  46. 46         for i in path:
  47. 47             s=''
  48. 48             for j in i:
  49. 49                 s+=j
  50. 50             re.append(s)
  51. 51         return re
复制代码
solveSudoku=================================================================================================================
不行,脑壳疼,换哈希啃啃

 242:有效的字母异位词
链接:242. 有效的字母异位词 - 力扣(LeetCode)
  1. 1 class Solution:
  2. 2     def solveSudoku(self, board: List[List[str]]) -> None:
  3. 3         """
  4. 4         Do not return anything, modify board in-place instead.
  5. 5         """
  6. 6         for i in range(len(board)):
  7. 7             for j in range(len(board[0])):
  8. 8                 if(board[i][j]!='.'):   continue
  9. 9                 for k in range(1,10):
  10. 10                     if(self.isValid(i,j,str(k),board)):
  11. 11                         board[i][j]=str(k)
  12. 12                         if self.solveSudoku(board):    return True
  13. 13                         board[i][j]='.'
  14. 14                 return False
  15. 15         return True
  16. 16     def isValid(self,x,y,k,board):
  17. 17         #行
  18. 18         if k in board[x]:   return False
  19. 19         #列
  20. 20         for i in range(9):
  21. 21             if board[i][y]==k:  return False
  22. 22         xi=x-x%3
  23. 23         yj=y-y%3
  24. 24         #9宫
  25. 25         for i in range(xi,xi+3):
  26. 26             for j in range(yj,yj+3):
  27. 27                 if board[i][j]==k:  return False
  28. 28         return True
复制代码
isAnagram349:两个数组的交集
链接:349. 两个数组的交集 - 力扣(LeetCode)
  1. 1 class Solution:
  2. 2     def isAnagram(self, s: str, t: str) -> bool:
  3. 3         if(len(s)!=len(t)): return False
  4. 4         for i in s:
  5. 5             if s.count(i)!=t.count(i):  return False
  6. 6         return True
复制代码
intersection202:快乐数
链接:202. 快乐数 - 力扣(LeetCode)
  1. 1 class Solution:  
  2. 2     def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:  
  3. 3         nums1=list(set(nums1))  
  4. 4         nums2=list(set(nums2))  
  5. 5         re=[]  
  6. 6         for i in nums1:  
  7. 7             if(i in nums2): re.append(i)  
  8. 8         return re  
复制代码
isHappy 

来源:https://www.cnblogs.com/xiaoruru/p/18001692
免责声明:由于采集信息均来自互联网,如果侵犯了您的权益,请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?立即注册

x

举报 回复 使用道具