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

记载了开端解题思绪 以及本地实当代码；并不肯定为最优 也渴望各人能一起探究 一起进步

---

7/15 721. 账户归并

   根据标题意思 只要两个账号中包罗雷同的邮箱地点 则以为两个账号可以归并
使用并查集
对每个邮箱创建一个尽头邮箱
mailPos: {email:账号位置} 记载全部邮箱对应的账号位置 出现多次对应哪个位置都可以 由于认定为一个账号
rootSet: 存储每个邮箱的尽头邮箱 若尽头邮箱雷同 则代表两个邮箱在同一个账号中
find:
探求邮箱i的尽头邮箱 并返回
union:
探求邮箱i,j的尽头邮箱
若差别
则将i的尽头变为j的尽头 及将i,j变为同一个账号
遍历已有的账号
将一个账号内的邮箱归并 这里和第一个邮箱归并
结果天生：
遍历全部存在的邮箱
找到其尽头邮箱 dic内key为尽头邮箱的账号位置 将这个邮箱参加此中
末了参加账号位置上的账号名称

1. def accountsMerge(accounts):
2.     """
3.     :type accounts: List[List[str]]
4.     :rtype: List[List[str]]
5.     """
6.     from collections import defaultdict
7.    
8.    
9.     mailPos = {mail:pos for pos,account in enumerate(accounts) for mail in account[1:]}
10.     rootSet = {mail:mail for mail in mailPos}
11.    
12.     def find(i):
13.         while rootSet[i]!=i:
14.             rootSet[i] = rootSet[rootSet[i]]
15.             i = rootSet[i]
16.         return i
17.         
18.    
19.     def union(i,j):
20.         if i!=j:
21.             endi = find(i)
22.             endj = find(j)
23.             if endi!=endj:
24.                 rootSet[endi] = rootSet[j]
25.    
26.     for account in accounts:
27.         l = len(account)
28.         for i in range(1,l):
29.             email = account[i]
30.             union(email,find(account[1]))
31.                
33.    
34.     dic = defaultdict(set)
35.     for mail in rootSet:
36.         pos = mailPos[find(mail)]
37.         dic[pos].add(mail)
38.    
39.     ans = [[accounts[pos][0]]+sorted(mail) for pos,mail in dic.items()]
40.     return ans

复制代码

---

7/16 2956. 找到两个数组中的公共元素

   遍历两个数组统计
判定元素 是否存在另一个数组中

1. def findIntersectionValues(nums1, nums2):
2.     """
3.     :type nums1: List[int]
4.     :type nums2: List[int]
5.     :rtype: List[int]
6.     """
7.     s1,s2 = set(nums1),set(nums2)
8.     c1,c2 = 0,0
9.     for v in nums1:
10.         if v in s2:
11.             c1+=1
12.     for v in nums2:
13.         if v in s1:
14.             c2+=1
15.     return [c1,c2]

复制代码

---

7/17 2959. 关闭分部的可行聚集数量

   用n位二进制来代表当前情况保存节点的状态
罗列保存节点的状态 判定该状态下是否满意要求

1. def numberOfSets(n, maxDistance, roads):
2.     """
3.     :type n: int
4.     :type maxDistance: int
5.     :type roads: List[List[int]]
6.     :rtype: int
7.     """
8.     g = [[float("inf")]*n for _ in range(n)]
9.     for i in range(n):
10.         g[i][i]=0
11.     for x,y,v in roads:
12.         g[x][y]= min(g[x][y],v)
13.         g[y][x]= min(g[y][x],v)
14.    
15.     f = [None]*n
16.     def func(s):
17.         for i,r in enumerate(g):
18.             if s>>i &1:
19.                 f[i] = r.copy()
20.         for k in range(n):
21.             if (s>>k & 1) == 0:
22.                 continue
23.             for i in range(n):
24.                 if (s>>i & 1) ==0 or f[i][k]==float("inf"):
25.                     continue
26.                 for j in range(n):
27.                     f[i][j] = min(f[i][j],f[i][k]+f[k][j])
28.         for i,d in enumerate(f):
29.             if (s>>i & 1)==0:
30.                 continue
31.             for j,dd in enumerate(d):
32.                 if s>>j & 1 and dd>maxDistance:
33.                     return 0
34.         return 1
35.     return sum(func(s) for s in range(1<<n))

复制代码

---

7/18 3112. 访问消散节点的最少时间

   dijkstra
从0开始访问可以或许访问到的节点
小顶堆h存储(d,x)
d为访问到x节点必要的时间隔断
每次取堆内迩来可以或许访问到的节点
遍历该节点毗连的其他节点 y
假如能在节点y消散前大概比已知更快到达 则更新节点y的结果

1. def minimumTime(n, edges, disappear):
2.     """
3.     :type n: int
4.     :type edges: List[List[int]]
5.     :type disappear: List[int]
6.     :rtype: List[int]
7.     """
8.     import heapq
9.     g = [[] for _ in range(n)]
10.     for x,y,v in edges:
11.         g[x].append((y,v))
12.         g[y].append((x,v))
13.    
14.     ans = [-1]*n
15.     ans[0]=0
16.     h = [(0,0)]
17.     while h:
18.         d,x = heapq.heappop(h)
19.         if d>ans[x]:
20.             continue
21.         for y,v in g[x]:
22.             newd = d+v
23.             if newd < disappear[y] and (ans[y]<0 or ans[y]>newd):
24.                 ans[y]=newd
25.                 heapq.heappush(h, (newd,y))
26.     return ans

复制代码

---

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

   先求得完玉成部关卡的分数total
重新开始记载每一关后得到的分数cur 同时减去cur为剩余的分数
判定当前分数是否大于剩余分数

1. def minimumLevels(possible):
2.     """
3.     :type possible: List[int]
4.     :rtype: int
5.     """
6.     total = 0
7.     for v in possible:
8.         if v==1:
9.             total +=1
10.         else:
11.             total -=1
12.     cur = 0
13.     num = 0
14.     tag = False
15.     for v in possible[:-1]:
16.         num+=1
17.         if v==1:
18.             cur +=1
19.             total -=1
20.         else:
21.             cur -=1
22.             total +=1
23.         if total<cur:
24.             tag = True
25.             break
26.     return num if tag else -1

复制代码

---

7/20 2850. 将石头分散到网格图的最少移动次数

   使用f记载石头可以移除的位置
使用t记载石头必要进入的位置
全分列f 依次盘算每种情况必要的步数

1. def minimumMoves(grid):
2.     """
3.     :type grid: List[List[int]]
4.     :rtype: int
5.     """
6.     import itertools
7.     f,t = [],[]
8.     for i,row in enumerate(grid):
9.         for j,cnt in enumerate(row):
10.             if cnt>1:
11.                 f.extend([(i, j)] * (cnt - 1))
12.             elif cnt==0:
13.                 t.append((i,j))
14.     ans=float("inf")
15.     for ff in itertools.permutations(f):
16.         total = 0
17.         for (x1,y1),(x2,y2) in zip(ff,t):
18.             total += abs(x1-x2)+abs(y1-y2)
19.         ans = min(ans,total)
20.     return ans
21.             

复制代码

---

7/21 1186. 删除一次得到子数组最大和

   动态规划
dp0表现arr末了删除0次的最大和
dp1表现arr末了删除1次的最大和
dp0 = max(dp0[i-1],0)+arr
dp1 = max(dp1[i-1]+arr,dp0[i-1])

1. def maximumSum(arr):
2.     """
3.     :type arr: List[int]
4.     :rtype: int
5.     """
6.     dp0,dp1=arr[0],0
7.     ans = dp0
8.     for i in range(1,len(arr)):
9.         dp1 = max(dp1+arr[i],dp0)
10.         dp0 = max(dp0,0)+arr[i]
11.         ans = max(ans,max(dp1,dp0))
12.     return ans

复制代码

---