2022 1 月

20220102

动态规划解题套路框架

完成

509. 斐波那契数（简单）

322. 零钱兑换（中等）

20220103

回溯算法解题套路框架

使用回溯法完成 n 皇后

51. N皇后（困难）

  1. class Solution:
  2.     def solveNQueens(self, n: int) -> List[List[str]]:
  3.         board = [["." for j in range(n)]for i in range(n)]
  4.         sit = 0
  5.         ans = []
  6.         def valid( i , j):
  7.             ti, tj = i, j
  8.             while 0 <= ti < n and 0 <= tj < n:
  9.                 if board[ti][tj] == "Q":
  10.                     return False
  11.                 ti -= 1
  12.                 tj -= 1
  14.             ti, tj = i, j
  15.             while 0 <= ti < n and 0 <= tj < n:
  16.                 if board[ti][tj] == "Q":
  17.                     return False
  18.                 ti -= 1
  20.             ti, tj = i, j
  21.             while 0 <= ti < n and 0 <= tj < n:
  22.                 if board[ti][tj] == "Q":
  23.                     return False
  24.                 ti -= 1
  25.                 tj += 1
  26.             return True
  28.         def dfs(n_sit, row):
  29.             # print(f"----------{n_sit} {row}")
  30.             if n_sit == n:
  31.                 # 摆完一轮了
  32.                 # print(board)
  33.                 ans.append(["".join(line) for line in board])
  34.                 # exit()
  35.                 return 
  36.             i = row
  37.             for j in range(n):
  38.                 if valid(i, j):
  39.                     # print(f"choose {i} {j}")
  40.                     board[i][j] = "Q"
  41.                     # print(board)
  42.                     dfs(n_sit + 1, row + 1)
  43.                     # break
  44.                     board[i][j] = "."
  45.                     # print(f"remove {i} {j}")
  46.                     # print(board)
  47.         dfs(sit, 0)
  48.         return ans

20220104

BFS 算法解题套路框架

BFS和DFS相比，BFS空间复杂度高，以满二叉树为例子，最高时O(n)的空间复杂度，DFS最多时O(logn)的空间复杂度。

111. 二叉树的最小深度（简单）

  1. # Definition for a binary tree node.
  2. # class TreeNode:
  3. #     def __init__(self, val=0, left=None, right=None):
  4. #         self.val = val
  5. #         self.left = left
  6. #         self.right = right
  7. class Solution:
  8.     def minDepth(self, root: TreeNode) -> int:
  9.         ans = 0
  10.         que = collections.deque()
  11.         que.append(root)
  12.         if not root:
  13.             return 0
  14.         while que:
  15.             ans += 1
  16.             n = len(que)
  17.             # print(que)
  18.             # print(n)
  19.             for i in range(n):
  20.                 node = que.popleft()
  21.                 if not node.left and not node.right:
  22.                     return ans
  23.                 if node.left:
  24.                     que.append(node.left)
  25.                 if node.right:
  26.                     que.append(node.right)
  29.         return ans

20220105

752.打开转盘锁

bfs 结合备忘录，必须有备忘录，否则会重复搜索元素陷入死循环。
时间复杂度：最多存储 10000次个节点
空间复杂度：最多搜索 10000次，

  1. class Solution:
  2.     def openLock(self, deadends: List[str], target: str) -> int:
  3.         que = collections.deque()
  4.         que.append("0000")
  5.         ans = 0
  6.         visit = [0] * 10000
  7.         visit[0] = 1
  8.         while que:
  9.             n = len(que)
  10.             # 每次取出队列中的所有元素，每次队列中的元素代表一步操作内的所有状态
  11.             for i in range(n):
  12.                 node = que.popleft()
  13.                 # 不能出现的序列跳过
  14.                 if node in deadends:
  15.                     continue
  16.                 # 结束条件
  17.                 if node == target:
  18.                     return ans
  19.                 # 每拿到一个元素，可以逐个字符旋转，形成8个新的状态
  20.                 for i in range(4):
  21.                     up, down  = self.next(node[i])
  22.                     # print(f"---------{i} {up} {down}")
  23.                     if i == 3:
  24.                         new = node[:i] + up 
  25.                         if visit[int(new)] == 0:
  26.                             que.append(new)
  27.                             visit[int(new)] = 1
  28.                         new = node[:i] + down
  29.                         if visit[int(new)] == 0:
  30.                             que.append(new)
  31.                             visit[int(new)] = 1
  32.                     else:
  33.                         new = node[:i] + up + node[i + 1:]
  34.                         if visit[int(new)] == 0:
  35.                             que.append(new)
  36.                             visit[int(new)] = 1
  37.                         new = node[:i] + down + node[i + 1:]
  38.                         if visit[int(new)] == 0:
  39.                             que.append(new)
  40.                             visit[int(new)] = 1
  41.             ans += 1
  42.             # if ans == 2:
  43.             #     break
  44.         return -1
  46.     def next(self, s):
  47.         s_up = (int(s) + 1 ) % 10
  48.         s_down = (10 + int(s) - 1 ) % 10
  49.         return [str(s_up), str(s_down)]

BFS 算法框架

  1. def BFS(target):
  2.     que = collections.deque()
  3.     que.append("start")
  4.     visit = [0] * 10000
  5.     visit[0] = 1
  6.     while que:
  7.         n = len(que)
  8.         for i in range(n):
  9.             node = que.popleft()
  10.             # 遍历下层元素，向四周扩散
  11.             for i in range(4):
  12.                 new = node + i
  13.                 # 结束条件
  14.                 if new == target:
  15.                     return ans
  16.                 que.append(new)
  17.         ans += 1
  18.     return

567.字符串的排列

  • 解题思路
    维持滑动窗口记录当前的匹配串，s2中出现s1的排列这个问题可以转化为，在滑动窗口中可以使用哪些字符以及这些字符可以使用几次，一个字典记录s1中字符出现次数。

然后遍历一遍s2，cnt 记录成功匹配的个数。
时间复杂度：O(n)
空间复杂度：O(n)

  • 代码
  1. class Solution:
  2.     def checkInclusion(self, s1: str, s2: str) -> bool:
  3.         l = 0
  4.         r = -1
  5.         n1 = len(s1)
  6.         dic = dict()
  7.         for i in range(n1):
  8.             if s1[i] in dic.keys():
  9.                 dic[s1[i]] += 1
  10.             else:
  11.                 dic.setdefault(s1[i], 1)
  12.         cnt = 0
  13.         n = len(s2)
  14.         while r < n - 1:
  15.             r += 1
  16.             # 出现不可用字符，直接舍弃之前的匹配
  17.             if s2[r] not in dic.keys():
  18.                 while s2[l] != s2[r]:
  19.                     dic[s2[l]] += 1
  20.                     cnt -= 1
  21.                     l += 1
  22.                 l += 1
  23.                 continue
  24.             # 出现可用字符但次数不够，则舍弃左侧字符直到出现一个可用字符
  25.             if dic[s2[r]] == 0: 
  26.                 while s2[l] != s2[r]:
  27.                     dic[s2[l]] += 1
  28.                     cnt -= 1
  29.                     l += 1
  30.                 l += 1
  31.             # 正常匹配一个字符
  32.             if dic[s2[r]] != 0:
  33.                 cnt += 1
  34.                 dic[s2[r]] -= 1
  35.             # 结束条件
  36.             if cnt == n1:
  37.                 return True
  38.         return False

20220106

Dijkstra 算法可以理解为BFS+DP table+优先队列

20220107

743. 网络延迟时间

  • 解题思路
    根据输入建图，从起始点开始使用BFS进行层序遍历，遍历时使用优先队列存储元素，同时使用dp table存储源节点到每个节点的距离。
    需要注意入队列时要把距离放在元素的第一位。
    时间复杂度：O(n)
    空间复杂度：O(n)
  • 代码 
  1. class Solution:
  2.     def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
  3.         import heapq
  4.         # 建图
  5.         gra = dict()
  6.         for (src, dst, val) in times:
  7.             if src in gra.keys():
  8.                 gra[src].append((dst, val))
  9.             else:
  10.                 gra.setdefault(src, [(dst, val)])
  11.         if k not in gra.keys():
  12.             return -1
  13.         # 初始化dp table
  14.         table = [float('inf')] * (n + 1)
  15.         table[0] = -1
  16.         table[k] = 0
  17.         que = [(0, k)]
  18.         while que:
  19.             # 优先队列pop距离最小的点
  20.             cur_val, cur_node = heapq.heappop(que)
  21.             if cur_node not in gra.keys():
  22.                 continue 
  23.             for next_node, next_val in gra[cur_node]:
  24.                 next_val += cur_val
  25.                 if next_val < table[next_node]:
  26.                     table[next_node] = next_val
  27.                     heapq.heappush(que, (next_val, next_node))
  28.         ans = max(table)
  29.         return ans if ans < float('inf') else -1

python 优先队列的使用

  1. import heapq
  2. que = []
  3. heapq.heappush(que, (1, 10))
  4. heapq.heappush(que, (2, 9))
  5. heapq.heappush(que, (2, 8))
  6. heapq.heappush(que, (3, 8))
  7. print(heapq.heappop(que))
  8. print(heapq.heappop(que))
  9. print(heapq.heappop(que))
  10. print(heapq.heappop(que))
  12. # 输出如下，因此我们可以知道元素排序是默认从第一个元素开始比较的。
  13. (1, 10)
  14. (2, 8)
  15. (2, 9)
  16. (3, 8)

Dijkstra

  • todo

1514. 概率最大的路径

  • 解题思路
    使用dijstra 计算src 到 dst 的最小路径，需要注意的是由于这题是无向图，所以建图的时候要双向都要存储。
    时间复杂度：o(n)
    空间复杂度：O(n)
  • 代码 
  1. class Solution:
  2.     def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
  3.         import heapq
  4.         # 建图
  5.         gra = dict()
  6.         for i, (src, dst) in enumerate(edges):
  7.             if src not in gra.keys():
  8.                 gra.setdefault(src, [(succProb[i], dst)])
  9.             else:
  10.                 gra[src].append((succProb[i], dst))
  11.             if dst not in gra.keys():
  12.                 gra.setdefault(dst, [(succProb[i], src)])
  13.             else:
  14.                 gra[dst].append((succProb[i], src))
  15.         # 初始化队列和table
  16.         que = [(0, start)]
  17.         table = [0] * n
  18.         table[start] = 0
  19.         while que:
  20.             # 因为heappo默认弹出最小值，所以存的时候 1-概率，保证弹出的概率值最大。
  21.             cur_p_sub, cur_node = heapq.heappop(que)
  22.             cur_p = 1 - cur_p_sub
  23.             if cur_node == end:
  24.                 return cur_p
  25.             if cur_node not in gra.keys():
  26.                 continue
  27.             for next_p, next_node in gra[cur_node]:
  28.                 next_p *= cur_p
  29.                 if next_p > table[next_node]:
  30.                     table[next_node] = next_p
  31.                     heapq.heappush(que, (1 - next_p, next_node))
  32.         return 0.0