LeetCode 每日一题 2024/7/15-2024/7/21

记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步

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 defaultdictmailPos = {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 idef 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,0for v in nums1:if v in s2:c1+=1for v in nums2:if v in s1:c2+=1return [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]=0for x,y,v in roads:g[x][y]= min(g[x][y],v)g[y][x]= min(g[y][x],v)f = [None]*ndef 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:continuefor i in range(n):if (s>>i & 1) ==0 or f[i][k]==float("inf"):continuefor 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:continuefor j,dd in enumerate(d):if s>>j & 1 and dd>maxDistance:return 0return 1return 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 heapqg = [[] for _ in range(n)]for x,y,v in edges:g[x].append((y,v))g[y].append((x,v))ans = [-1]*nans[0]=0h = [(0,0)]while h:d,x = heapq.heappop(h)if d>ans[x]:continuefor y,v in g[x]:newd = d+vif newd < disappear[y] and (ans[y]<0 or ans[y]>newd):ans[y]=newdheapq.heappush(h, (newd,y))return ans

7/19 3096. 得到更多分数的最少关卡数目

先求得完成所有关卡的分数total
从头开始记录每一关后得到的分数cur 同时减去cur为剩余的分数
判断当前分数是否大于剩余分数

def minimumLevels(possible):""":type possible: List[int]:rtype: int"""total = 0for v in possible:if v==1:total +=1else:total -=1cur = 0num = 0tag = Falsefor v in possible[:-1]:num+=1if v==1:cur +=1total -=1else:cur -=1total +=1if total<cur:tag = Truebreakreturn num if tag else -1

7/20

7/21