记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
目录
7/15 721. 账户合并
根据题目意思 只要两个账号中包含相同的邮箱地址 则认为两个账号可以合并
使用并查集
对每个邮箱创建一个终点邮箱
mailPos: {email:账号位置} 记录所有邮箱对应的账号位置 出现多次对应哪个位置都可以 因为认定为一个账号
rootSet: 存储每个邮箱的终点邮箱 若终点邮箱相同 则代表两个邮箱在同一个账号中
find:
寻找邮箱i的终点邮箱 并返回
union:
寻找邮箱i,j的终点邮箱
若不同
则将i的终点变为j的终点 及将i,j变为同一个账号
遍历已有的账号
将一个账号内的邮箱合并 这里和第一个邮箱合并
结果生成：
遍历所有存在的邮箱
找到其终点邮箱 dic内key为终点邮箱的账号位置 将这个邮箱加入其中
最后加入账号位置上的账号名称
def accountsMerge(accounts):
"""
:type accounts: List[List[str]]
:rtype: List[List[str]]
"""
from collections import defaultdict
mailPos = {mail:pos for pos,account in enumerate(accounts) for mail in account[1:]}
rootSet = {mail:mail for mail in mailPos}
def find(i):
while rootSet[i]!=i:
rootSet[i] = rootSet[rootSet[i]]
i = rootSet[i]
return i
def union(i,j):
if i!=j:
endi = find(i)
endj = find(j)
if endi!=endj:
rootSet[endi] = rootSet[j]
for account in accounts:
l = len(account)
for i in range(1,l):
email = account[i]
union(email,find(account[1]))
dic = defaultdict(set)
for mail in rootSet:
pos = mailPos[find(mail)]
dic[pos].add(mail)
ans = [[accounts[pos][0]]+sorted(mail) for pos,mail in dic.items()]
return ans
7/16 2956. 找到两个数组中的公共元素
遍历两个数组统计
判断元素 是否存在另一个数组中
def findIntersectionValues(nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
s1,s2 = set(nums1),set(nums2)
c1,c2 = 0,0
for v in nums1:
if v in s2:
c1+=1
for v in nums2:
if v in s1:
c2+=1
return [c1,c2]
7/17 2959. 关闭分部的可行集合数目
用n位二进制来代表当前情况保留节点的状态
枚举保留节点的状态 判断该状态下是否满足要求
def numberOfSets(n, maxDistance, roads):
"""
:type n: int
:type maxDistance: int
:type roads: List[List[int]]
:rtype: int
"""
g = [[float("inf")]*n for _ in range(n)]
for i in range(n):
g[i][i]=0
for x,y,v in roads:
g[x][y]= min(g[x][y],v)
g[y][x]= min(g[y][x],v)
f = [None]*n
def func(s):
for i,r in enumerate(g):
if s>>i &1:
f[i] = r.copy()
for k in range(n):
if (s>>k & 1) == 0:
continue
for i in range(n):
if (s>>i & 1) ==0 or f[i][k]==float("inf"):
continue
for j in range(n):
f[i][j] = min(f[i][j],f[i][k]+f[k][j])
for i,d in enumerate(f):
if (s>>i & 1)==0:
continue
for j,dd in enumerate(d):
if s>>j & 1 and dd>maxDistance:
return 0
return 1
return sum(func(s) for s in range(1<<n))
7/18 3112. 访问消失节点的最少时间
dijkstra
从0开始访问能够访问到的节点
小顶堆h存储(d,x)
d为访问到x节点需要的时间距离
每次取堆内最近能够访问到的节点
遍历该节点连接的其他节点 y
如果能在节点y消失前或者比已知更快到达 则更新节点y的结果
def minimumTime(n, edges, disappear):
"""
:type n: int
:type edges: List[List[int]]
:type disappear: List[int]
:rtype: List[int]
"""
import heapq
g = [[] for _ in range(n)]
for x,y,v in edges:
g[x].append((y,v))
g[y].append((x,v))
ans = [-1]*n
ans[0]=0
h = [(0,0)]
while h:
d,x = heapq.heappop(h)
if d>ans[x]:
continue
for y,v in g[x]:
newd = d+v
if newd < disappear[y] and (ans[y]<0 or ans[y]>newd):
ans[y]=newd
heapq.heappush(h, (newd,y))
return ans
7/19 3096. 得到更多分数的最少关卡数目
先求得完成所有关卡的分数total
从头开始记录每一关后得到的分数cur 同时减去cur为剩余的分数
判断当前分数是否大于剩余分数
def minimumLevels(possible):
"""
:type possible: List[int]
:rtype: int
"""
total = 0
for v in possible:
if v==1:
total +=1
else:
total -=1
cur = 0
num = 0
tag = False
for v in possible[:-1]:
num+=1
if v==1:
cur +=1
total -=1
else:
cur -=1
total +=1
if total<cur:
tag = True
break
return num if tag else -1
7/20
7/21
