LeetCode 每日一题 2024/8/26-2024/9/1

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

---

8/26 690. 员工的重要性

BFS

class Employee(object):def __init__(self, id, importance, subordinates):# It's the unique id of each node.# unique id of this employeeself.id = id# the importance value of this employeeself.importance = importance# the id of direct subordinatesself.subordinates = subordinatesdef getImportance(employees, id):""":type employees: Employee:type id: int:rtype: int"""if len(employees)==0:return 0dic = {}for v in employees:dic[v.id] = vret = 0l =[]l.append(id)while len(l)>0:n = l.pop(0)e = dic.get(n)ret += e.importancel.extend(e.subordinates)return ret

---

8/27 3134. 找出唯一性数组的中位数

共有m=1+2+…+n=n*(n+1)/2个费控连续子数组
中位数是第k=m//2个元素
对于一个子数组如果变长 它的不同元素个数不会变少
check(upper)检查小于upper数有多少个

def medianOfUniquenessArray(nums):""":type nums: List[int]:rtype: int"""import bisectfrom collections import defaultdictn=len(nums)k=(n*(n+1)//2+1)//2def check(upper):cnt = 0l = 0fre = defaultdict(int)for r,v in enumerate(nums):fre[v] +=1while len(fre)>upper:out = nums[l]fre[out]-=1if fre[out]==0:del fre[out]l+=1cnt += r-l+1if cnt>=k:return Truereturn Falsereturn bisect.bisect_left(range(len(set(nums))), True,1,key=check)

---

8/28 3144. 分割字符频率相等的最少子字符串

dp[i]记录以i结尾的前缀字符串最少平和字符串个数
对于每个i j从后往前遍历 m[x]存储字符x出现次数
对于子字符串s[j:i] 记录字符出现最大次数cnt
如果每个字符出现次数相同那么cnt*len(m)=字符串长度i-j+1

def minimumSubstringsInPartition(s):""":type s: str:rtype: int"""from collections import defaultdictn=len(s)dp = [float("inf")]*(n+1)dp[0]=0for i in range(1,n+1):m = defaultdict(int)cnt = 0for j in range(i,0,-1):m[s[j-1]]+=1cnt = max(cnt,m[s[j-1]])if cnt*len(m)==i-j+1 and dp[j-1]!=float("inf"):dp[i]=min(dp[i],dp[j-1]+1)return dp[n]

---

8/29 3142. 判断矩阵是否满足条件

判断第一行 相邻是否不同
判断每一列 是否相同

def satisfiesConditions(grid):""":type grid: List[List[int]]:rtype: bool"""n,m=len(grid),len(grid[0])for j in range(m):if j>0 and grid[0][j-1]==grid[0][j]:return Falsefor i in range(1,n):if grid[i-1][j]!=grid[i][j]:return Falsereturn True

---

8/30 3153. 所有数对中数位不同之和

依次统计每一位上所有数值的个数
n=len(nums)
如果数值x出现m次 那么有n-m种情况会出现该位是不同的
累加最后因为重复计算除以二

def sumDigitDifferences(nums):""":type nums: List[int]:rtype: int"""n=len(nums)ans = 0while nums[0]>0:m = [0]*10for i in range(n):m[nums[i]%10]+=1nums[i]//=10for x in range(10):ans += (n-m[x])*m[x]return ans//2

---

8/31 3127. 构造相同颜色的正方形

遍历四个正方形

def canMakeSquare(grid):""":type grid: List[List[str]]:rtype: bool"""from collections import defaultdictdef check(i,j):m = defaultdict(int)m[grid[i][j]]+=1m[grid[i+1][j]]+=1m[grid[i][j+1]]+=1m[grid[i+1][j+1]]+=1return m['W']>=3 or m['B']>=3return check(0,0) or check(0, 1) or check(1,0) or check(1,1)

---

9/1

---