LeetCode 每日一题 2024/10/14-2024/10/20

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

---

10/14 887. 鸡蛋掉落

动态规划
1.dp[K][N]代表K个鸡蛋 N层最坏情况的最少次数
2.dp[k][m]=n k个鸡蛋 可以扔m次 最坏情况下最多可以测n层楼
dp[k][m] = 1+ dp[k,m-1]#没碎+dp[k-1,m-1]#碎了

def superEggDrop(K, N):""":type K: int:type N: int:rtype: int"""mem={}def dp(K,N):if K==1:return Nif N==0:return 0if (K,N) in mem:return mem[(K,N)]res = float('INF')lo,hi=1,Nwhile lo<=hi:mid=lo+(hi-lo)//2broken = dp(K-1,mid-1) #碎了not_broken = dp(K,N-mid),  #没碎if broken>not_broken:hi = mid -1res = min(res,broken+1)else:lo = mid+1res = min(res,not_broken+1)mem[(K,N)]=resreturn resreturn dp(K,N)def superEggDrop2(K, N):""":type K: int:type N: int:rtype: int"""dp = [[0]*(N+1) for _ in range(K+1)]m = 0while dp[K][m]<N:m+=1for k in range(1,K+1):dp[k][m] = dp[k][m-1] + dp[k-1][m-1]+1return m

---

10/15 3200. 三角形的最大高度

分别判断红、蓝先放第一排的两种情况

def maxHeightOfTriangle(red, blue):""":type red: int:type blue: int:rtype: int"""def check(odd,even):cur = 1while True:print(odd,even,cur)if cur%2==1:if odd>=cur:odd-=curelse:breakelse:if even>=cur:even-=curelse:breakcur+=1return cur-1return max(check(red,blue),check(blue,red))

---

10/16 3194. 最小元素和最大元素的最小平均值

从小到大排列 依次求平均值

def minimumAverage(nums):""":type nums: List[int]:rtype: float"""nums.sort()ans = nums[-1]n=len(nums)for i in range(n//2):ans = min(ans,(nums[i]+nums[n-1-i])*1.0/2)return ans

---

10/17 3193. 统计逆序对的数目

https://leetcode.cn/problems/count-the-number-of-inversions/solutions/2946689/tong-ji-ni-xu-dui-de-shu-mu-by-leetcode-qsk7r/?envType=daily-question&envId=2024-10-18

def numberOfPermutations(n, requirements):""":type n: int:type requirements: List[List[int]]:rtype: int"""MOD=10**9+7req = {0:0}for end,cnt in requirements:req[end]=cntif req[0]>0:return 0mem = {}def dfs(end,cnt):ans = 0if (end,cnt) in mem:return mem[(end,cnt)]if cnt<0:return 0if end==0:return 1if end-1 in req:r = req[end-1]if r<=cnt<=end+r:ans = dfs(end-1,r)mem[(end,cnt)]=ansreturn anselse:mem[(end,cnt)]=ansreturn anselse:if cnt>end:ans = (dfs(end,cnt-1)-dfs(end-1,cnt-1-end)+dfs(end-1,cnt))%MODmem[(end,cnt)]=ansreturn anselse:ans = (dfs(end,cnt-1) + dfs(end-1,cnt)) % MODmem[(end,cnt)]=ansreturn ansreturn dfs(n-1,req[n-1])

---

10/18 3191. 使二进制数组全部等于 1 的最少操作次数 I

对于同个位置起始的操作两次等于没有操作 所以每个位置起始的操作最多1次
对不同的几个操作 顺序并不会改变最后的操作结果
所以从左到右操作即可
从头到尾遍历 遇到0进行翻转
最后查看数组最后两位是否为1

def minOperations(nums):""":type nums: List[int]:rtype: int"""ans=0for i in range(len(nums)-2):if nums[i]==0:nums[i+1]^=1nums[i+2]^=1ans+=1return ans if nums[-1] and nums[-2] else -1

---

10/19 3192. 使二进制数组全部等于 1 的最少操作次数 II

最左侧的0必须进行反转操作
为了使得反转次数最少 从左至右依次判断
遇到0就需要反转

def minOperations(nums):""":type nums: List[int]:rtype: int"""ans = 0for num in nums:if (num+ans)%2==0:ans+=1return ans

---

10/20 908. 最小差值 I

找到当前最大值a 最小值 b
a可以减小k b可以增加k
a-b的差值最多可以减少2k

def smallestRangeI(nums, k):""":type nums: List[int]:type k: int:rtype: int"""return max(0,max(nums)-min(nums)-2*k)

---