LeetCode 每日一题 2023/11/6-2023/11/12

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

---

11/6 318. 最大单词长度乘积

l记录每个单词长度
s记录每个单词内所含字符
如果s[i] s[j]相交为空 说明单词word[i] word[j]不含相同字符

def maxProduct(words):""":type words: List[str]:rtype: int"""s = []l = []maxl = 0for word in words:l.append(len(word))maxl = max(maxl,len(word))s.append(set(word))n = len(words)ans = 0for i in range(n-1):for j in range(i,n):if l[i]*maxl<ans:breakif not s[i]&s[j]:ans = max(ans,l[i]*l[j])return ans

---

11/7 2586. 统计范围内的元音字符串数

依次判断

def vowelStrings(words, left, right):""":type words: List[str]:type left: int:type right: int:rtype: int"""s=set({'a','e','i','o','u'})ans = 0for i in range(left,right+1):w=words[i]if w[0] in s and w[len(w)-1] in s:ans+=1return ans

---

11/8 2609. 最长平衡子字符串

从头遍历记录连续0或1的个数

def findTheLongestBalancedSubstring(s):""":type s: str:rtype: int"""ans = 0if len(s)==0:return ansone = 0zero = 0pre = 0for c in s:if c=='0':pre = 0one = 0zero+=1else:pre = max(pre,zero)zero = 0one +=1ans = max(ans,2*min(pre,one))ans = max(ans,2*min(pre,one))return ans

---

11/9 2258. 逃离火灾

计算人到安全屋时间 以及安全屋隔壁的时间
火到安全屋的时间
判断人是否能比火先到安全屋的隔壁

def maximumMinutes(grid):""":type grid: List[List[int]]:rtype: int"""m,n=len(grid),len(grid[0])def bfs(l):t = [[-1]*n for _ in range(m)]for i,j in l:t[i][j]=0cur = 1while l:tmp = []for i,j in l:for x,y in (i-1,j),(i,j-1),(i+1,j),(i,j+1):if 0<=x<m and 0<=y<n and grid[x][y]==0 and t[x][y]<0:t[x][y] = curtmp.append((x,y))cur+=1l=tmpreturn t[-1][-1],t[-1][-2],t[-2][-1]m0,m1,m2=bfs([(0,0)])if m0<0:return -1fire = [(i,j) for i,g in enumerate(grid) for j,x in enumerate(g) if x==1]f0,f1,f2 =  bfs(fire)if f0<0:return 10**9d = f0-m0if d<0:return -1if m1!=-1 and m1+d<f1 or (m2!=-1 and m2+d<f2):return dreturn d-1

---

11/10 2300. 咒语和药水的成功对数

将药水强度从小到大排序
二分查找 咒语能够成功匹配的药水强度的位置

def successfulPairs(spells, potions, success):""":type spells: List[int]:type potions: List[int]:type success: int:rtype: List[int]"""n = len(potions)potions.sort()ans = []for s in spells:v = (success+s-1)//sl,r=0,n-1while l<r:mid = (l+r)//2if potions[mid]<v:l = mid+1else:r = midif s*potions[r]>=success:ans.append(n-r)else:ans.append(0)return ans

---

11/11 765. 情侣牵手

如果有k对情侣坐错 需要交换k-1次
并查集将坐错的情侣分区

def minSwapsCouples(row):""":type row: List[int]:rtype: int"""def find(pre,x):if pre[x]!=x:pre[x] = find(pre,pre[x])return pre[x]n = len(row)pre = list(range(n//2))num = [1]*(n//2)for i in range(0,n,2):x = find(pre,row[i]//2)y = find(pre,row[i+1]//2)if x!=y:pre[x]=ynum[y]+=num[x]ans = 0for i in range(n//2):if pre[i]==i:ans += num[i]-1return ans

---

11/12

---