LeetCode 每日一题 2024/10/7-2024/10/13

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

---

10/7 871. 最低加油次数

依次经过加油站 将能够加的油放入大顶堆中
如果无法到达加油站 从能够加的油中选出最多的加入

def minRefuelStops(target, startFuel, stations):""":type target: int:type startFuel: int:type stations: List[List[int]]:rtype: int"""import heapqfuel = startFuelpre = 0ans = 0stations.append([target,0])l = []for loc,f in stations:v = loc-prefuel -= vwhile fuel<0 and l:tmp = -heapq.heappop(l)ans +=1fuel += tmpif fuel < 0:return -1heapq.heappush(l,-f)pre = locreturn ans

---

10/8 1436. 旅行终点站

target存储所有出现的终点站
source存储所有出现的起点
从target中找到一个未出现在source中的点即为最终终点站

def destCity(paths):""":type paths: List[List[str]]:rtype: str"""target = set()source = set()for s,t in paths:source.add(s)target.add(t)for loc in target:if loc not in source:return loc

---

10/9 3171. 找到按位或最接近 K 的子数组

遍历数组尾nums[i]
从后往前遍历j [j~i]
如果x为nums[j]子集 后续已经在i=j时处理过不需要继续进行

def minimumDifference(nums, k):""":type nums: List[int]:type k: int:rtype: int"""ans=float("inf")for i,x in enumerate(nums):ans = min(ans,abs(x-k))j = i-1while j>=0 and nums[j]|x!=nums[j]:nums[j] |= xans = min(ans,abs(nums[j]-k))j-=1return ans

---

10/10 3162. 优质数对的总数 I

遍历每一对数是否优质

def numberOfPairs(nums1, nums2, k):""":type nums1: List[int]:type nums2: List[int]:type k: int:rtype: int"""ans = 0for n1 in nums1:for n2 in nums2:if n1%(n2*k)==0:ans+=1return ans

---

10/11 3164. 优质数对的总数 II

nums1优质的必须能被k整除
除以k后 统计nums1中每个数的所有因子个数 cnt[c]
只要nums2中数值num的优质数对就是以num为因子统计到的个数cnt[num]

def numberOfPairs(nums1, nums2, k):""":type nums1: List[int]:type nums2: List[int]:type k: int:rtype: int"""import mathcnt={}for num in nums1:if num%k>0:continuenum = num//kfor d in range(1,int(math.sqrt(num))+1):if num%d>0:continuecnt[d] = cnt.get(d,0)+1if d**2<num:cnt[num//d]=cnt.get(num//d,0)+1            ans = 0for num in nums2:ans += cnt.get(num,0)return ans

---

10/12 3158. 求出出现两次数字的 XOR 值

从头遍历 记录出现过的数字 如果出现第二次则将其异或

def duplicateNumbersXOR(nums):""":type nums: List[int]:rtype: int"""ans = 0s =set()for num in nums:if num in s:ans ^= nums.add(num)return ans

---

10/13 1884. 鸡蛋掉落-两枚鸡蛋

动态规划
dp[i]表示i层需要的最少操作次数
选择k往下扔
如果没有碎那么答案在[k+1,i] i-k层建筑中 等同于dp[i-k]
如果碎了答案在[1,k-1] 依次试需要k-1次

def twoEggDrop(n):""":type n: int:rtype: int"""dp=[0]+[float("inf")]*nfor i in range(1,n+1):for k in range(1,i+1):dp[i] = min(dp[i],max(k-1,dp[i-k])+1)return dp[n]

---