記錄了初步解題思路 以及本地實(shí)現(xiàn)代碼；并不一定為最優(yōu) 也希望大家能一起探討 一起進(jìn)步

---

10/21 910. 最小差值 II

從小到大排列 小的盡量+k 大的-k
最小值mi 最大值ma
從頭遍歷位置i 假設(shè)nums[i]是最大一個(gè)+k的值
那么當(dāng)前情況最大值為 max(nums[i]+k,ma-k)
最小值為min(nums[i+1]-k,mi+k)
更新當(dāng)前情況的差值

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. 構(gòu)成整天的下標(biāo)對(duì)數(shù)目 I

計(jì)算每個(gè)小時(shí)除以24的余數(shù)
余數(shù)相加為24的可以匹配
余數(shù)為0和12 在自己組內(nèi)匹配

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. 構(gòu)成整天的下標(biāo)對(duì)數(shù)目 II

計(jì)算每個(gè)小時(shí)除以24的余數(shù)
余數(shù)相加為24的可以匹配
余數(shù)為0和12 在自己組內(nèi)匹配

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. 找到連續(xù)贏 K 場(chǎng)比賽的第一位玩家

從頭遍歷 i 直至遇到大于他的j
如果此時(shí)已經(jīng)贏了k場(chǎng)那么返回i
否則從j開(kāi)始繼續(xù)往后贏
如果到最后還沒(méi)有達(dá)到k 此時(shí)的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. 執(zhí)行操作可獲得的最大總獎(jiǎng)勵(lì) I

從小到大排序
dp[k]表示獎(jiǎng)勵(lì)k是否可以獲得
最大值為mx 能夠得到的獎(jiǎng)勵(lì)不超過(guò)2*m-1
對(duì)于當(dāng)前值x 最多可以到達(dá)k=x~2x-1 如果k-x存在 那么說(shuō)明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. 執(zhí)行操作可獲得的最大總獎(jiǎng)勵(lì) II

從小到大排序 dp[k]判斷獎(jiǎng)勵(lì)k是否可以獲得
遍歷value x 對(duì)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. 冗余連接

并查集
遍歷每一條邊 比樹多一條邊
如果兩個(gè)點(diǎn)已經(jīng)連通說(shuō)明這條邊是多余的

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 []

---