本文主要是介绍Day53力扣打卡,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
打卡记录
重新规划路线(dfs)
链接
class Solution:def dfs(self, x: int, parent: int, e: List[List[List[int]]]) -> int:res = 0for edge in e[x]:if edge[0] == parent:continueres += edge[1] + self.dfs(edge[0], x, e)return resdef minReorder(self, n: int, connections: List[List[int]]) -> int:e = [[] for _ in range(n)]for edge in connections:e[edge[0]].append([edge[1], 1])e[edge[1]].append([edge[0], 0])return self.dfs(0, -1, e)
回路计数(DP状态压缩)
链接
import os
import sys
import mathn = 21
st = [[False] * n for _ in range(n)]
for i in range(0, n, 2):for j in range(i + 1, n):if math.gcd(i + 1, j + 1) == 1:st[i][j] = st[j][i] = Truef = [[0] * n for _ in range(1 << n)]
f[1][0] = 1for i in range(1 << n):for j in range(n):if not (i >> j) & 1:continuefor k in range(n):if (i >> k) & 1 and st[k][j]:f[i][j] += f[i - (1 << j)][k]ans = 0
for i in range(n):ans += f[-1][i]
print(ans)
这篇关于Day53力扣打卡的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!