LeetCode 每日一题 2024/10/21-2024/10/27
记录了初步解题思路 以及本地实现代码;并不一定为最优 也希望大家能一起探讨 一起进步
目录
- 10/21 910. 最小差值 II
- 10/22 3184. 构成整天的下标对数目 I
- 10/23 3185. 构成整天的下标对数目 II
- 10/24 3175. 找到连续赢 K 场比赛的第一位玩家
- 10/25 3180. 执行操作可获得的最大总奖励 I
- 10/26
- 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
10/27