LeetCode 每日一题 2024/6/3-2024/6/9

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

6/3 1103. 分糖果 II

base记录当前已经完成了几轮
cur为当前轮需要消耗的总糖果数
当无法完全分一轮时结束 完成了base轮
此时对于i位置(从1开始)的人分到了
i+(i+n)+(i+n2)+…+(i+n(base-1))
=i*base+(base-1)base/2n 个糖果
最后将剩余糖果分一遍即可

def distributeCandies(candies, num_people):""":type candies: int:type num_people: int:rtype: List[int]"""n=num_peoples = (1+n)*n//2base = 0cur = swhile candies>=cur:candies -= curbase +=1cur += n*nans = [0]*nif base>0:ans = [base*(base-1)//2*n+(i+1)*(base) for i in range(n) ]for i in range(n):v = base*n+i+1if v>candies:v = candiescandies-=vans[i]+=vif candies==0:breakreturn ans

6/4 3067. 在带权树网络中统计可连接服务器对数目

g[x]存储节点x的邻居节点
pre记录已经处理过的节点中满足条件的个数
cnt为当前节点满足的个数 相乘即为总对数

def countPairsOfConnectableServers(edges, signalSpeed):""":type edges: List[List[int]]:type signalSpeed: int:rtype: List[int]"""n=len(edges)+1g = [[] for _ in range(n)]for u,v,w in edges:g[u].append((v,w))g[v].append((u,w))def dfs(p,root,cur):ans = 0if cur==0:ans+=1for v,cost in g[p]:if v!=root:ans += dfs(v,p,(cur+cost)%signalSpeed)return ansans = [0]*nfor i in range(n):pre = 0for v, cost in g[i]:cnt = dfs(v,i,cost%signalSpeed)ans[i]+=pre*cntpre+=cntreturn ans

6/5 3072. 将元素分配到两个数组中 II

假设nums中有m个不同的数值
将数组中的数从小到大离散到[1,m]
利用树状数组查询大于val的元素数量

def resultArray(nums):""":type nums: List[int]:rtype: List[int]"""class Tree:def __init__(self,n):self.v = [0]*ndef add(self,i):while i<len(self.v):self.v[i]+=1i += i&-idef get(self,i):ans = 0while i>0:ans += self.v[i]i&=i-1return ansn=len(nums)snums = sorted(nums)ind ={}for i,v in enumerate(snums):ind[v]=i+1arr1 = [nums[0]]arr2 = [nums[1]]t1 = Tree(n+1)t2 = Tree(n+1)t1.add(ind[nums[0]])t2.add(ind[nums[1]])for i in range(2,n):cnt1 = len(arr1)-t1.get(ind[nums[i]])cnt2 = len(arr2)-t2.get(ind[nums[i]])if cnt1>cnt2 or (cnt1==cnt2 and len(arr1)<=len(arr2)):arr1.append(nums[i])t1.add(ind[nums[i]])else:arr2.append(nums[i])t2.add(ind[nums[i]])return arr1+arr2

6/6 2938. 区分黑球与白球

将白球0移到左侧 黑球1移到右侧
对于每一个0 对于它左侧的所有1都需要交换一次
从头遍历 记录遇到的1的个数cnt
没遇到一个0都需要移动cnt次

def minimumSteps(s):""":type s: str:rtype: int"""ans=cnt=0for c in s:if c=='1':cnt +=1else:ans += cntreturn ans

6/7 3038. 相同分数的最大操作数目 I

依次判断

def maxOperations(nums):""":type nums: List[int]:rtype: int"""ans = 0v = 0while len(nums)>=2:if v==0:v = nums[0]+nums[1]elif v!=nums[0]+nums[1]:breakans+=1nums = nums[2:]return ans

6/8 3040. 相同分数的最大操作数目 II

共有三种情况考虑
func考虑从[i,j]区间内 分数为target能得到的操作数

def maxOperations(nums):""":type nums: List[int]:rtype: int"""mem={}def func(i,j,target):if (i,j,target) in mem:return mem[(i,j,target)]ans = 0if j-i>=1:if nums[i]+nums[i+1]==target:ans = max(ans,1+func(i+2,j,target))if nums[i]+nums[j]==target:ans = max(ans,1+func(i+1,j-1,target))if nums[j]+nums[j-1]==target:ans = max(ans,1+func(i,j-2,target))mem[(i,j,target)] = ansreturn ansans = 0n=len(nums)if len(nums)>=2:ans = max(ans,1+func(2,n-1,nums[0]+nums[1]),1+func(1,n-2,nums[0]+nums[-1]),1+func(0,n-3,nums[-1]+nums[-2]))return ans

6/9 312. 戳气球

动态规划
分别在前后加一个1方便计算
dp[i][j]表示区间i,j内气球能够得到最多硬币数
假设i,j内的k是最后一个被戳破的气球
状态转移为
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]+arr[i]*arr[k]*arr[j])

def maxCoins(nums):""":type nums: List[int]:rtype: int"""n=len(nums)arr = [1]+nums+[1]dp=[[0]*(n+2) for _ in range(n+2)]for i in range(n-1,-1,-1):for j in range(i+2,n+2):for k in range(i+1,j):dp[i][j] = max(dp[i][j],dp[i][k]+dp[k][j]+arr[i]*arr[k]*arr[j])return dp[0][-1]