LeetCode 每日一题 2024/10/21-2024/10/27

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

---

10/21 910. 最小差值 II

从小到大排列 小的尽量+k 大的-k
最小值mi 最大值ma
从头遍历位置i 假设nums[i]是最大一个+k的值
那么当前情况最大值为 max(nums[i]+k,ma-k)
最小值为min(nums[i+1]-k,mi+k)
更新当前情况的差值

def smallestRangeII(nums, k):""":type nums: List[int]:type k: int:rtype: int"""nums.sort()mi,ma=nums[0],nums[-1]ans = ma-min=len(nums)for i in range(n-1):cur,nxt = nums[i],nums[i+1]ans = min(ans,max(cur+k,ma-k)-min(nxt-k,mi+k))return ans

---

10/22 3184. 构成整天的下标对数目 I

计算每个小时除以24的余数
余数相加为24的可以匹配
余数为0和12 在自己组内匹配

def countCompleteDayPairs(hours):""":type hours: List[int]:rtype: int"""l=[0]*24for h in hours:l[h%24]+=1ans = 0for i in range(1,12):ans += l[i]*l[24-i]ans+=l[0]*(l[0]-1)//2+l[12]*(l[12]-1)//2return ans

---

10/23 3185. 构成整天的下标对数目 II

计算每个小时除以24的余数
余数相加为24的可以匹配
余数为0和12 在自己组内匹配

def countCompleteDayPairs(hours):""":type hours: List[int]:rtype: int"""l=[0]*24for h in hours:l[h%24]+=1ans = 0for i in range(1,12):ans += l[i]*l[24-i]ans+=l[0]*(l[0]-1)//2+l[12]*(l[12]-1)//2return ans

---

10/24 3175. 找到连续赢 K 场比赛的第一位玩家

从头遍历 i 直至遇到大于他的j
如果此时已经赢了k场那么返回i
否则从j开始继续往后赢
如果到最后还没有达到k 此时的i必定是最大值 返回

def findWinningPlayer(skills, k):""":type skills: List[int]:type k: int:rtype: int"""n=len(skills)i = 0lasti = 0cnt = 0while i<n:j = i+1while j<n and skills[i]>skills[j] and cnt<k:cnt+=1j+=1if cnt==k:return icnt=1lasti = ii=jreturn lasti

---

10/25 3180. 执行操作可获得的最大总奖励 I

从小到大排序
dp[k]表示奖励k是否可以获得
最大值为mx 能够得到的奖励不超过2*m-1
对于当前值x 最多可以到达k=x~2x-1 如果k-x存在 那么说明k可以得到

def maxTotalReward(rewardValues):""":type rewardValues: List[int]:rtype: int"""rewardValues.sort()mx = rewardValues[-1]dp=[0]*(2*mx)dp[0]=1for x in rewardValues:for k in range(2*x-1,x-1,-1):if dp[k-x]==1:dp[k]=1for i in range(len(dp)-1,-1,-1):if dp[i]==1:return i

---

10/26 3181. 执行操作可获得的最大总奖励 II

从小到大排序 dp[k]判断奖励k是否可以获得
遍历value x 对k=x,2x-1一次查看

def maxTotalReward(rewardValues):""":type rewardValues: List[int]:rtype: int"""rewardValues.sort()if len(rewardValues)>=2 and rewardValues[-2]==rewardValues[-1]-1:return 2*rewardValues[-1]-1dp = 1for x in rewardValues:dp |= (dp & ((1<<x)-1))<<xreturn dp.bit_length()-1

---

10/27 684. 冗余连接

并查集
遍历每一条边 比树多一条边
如果两个点已经连通说明这条边是多余的

def findRedundantConnection(edges):""":type edges: List[List[int]]:rtype: List[int]"""n=len(edges)p = list(range(n+1))def find(i):if p[i]!=i:p[i]=find(p[i])return p[i]def union(i,j):p[find(i)]=find(j)for i,j in edges:if find(i)!=find(j):union(i,j)else:return [i,j]return []

---