记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
目录
10/7 871. 最低加油次数
依次经过加油站 将能够加的油放入大顶堆中
如果无法到达加油站 从能够加的油中选出最多的加入
def minRefuelStops(target, startFuel, stations):
"""
:type target: int
:type startFuel: int
:type stations: List[List[int]]
:rtype: int
"""
import heapq
fuel = startFuel
pre = 0
ans = 0
stations.append([target,0])
l = []
for loc,f in stations:
v = loc-pre
fuel -= v
while fuel<0 and l:
tmp = -heapq.heappop(l)
ans +=1
fuel += tmp
if fuel < 0:
return -1
heapq.heappush(l,-f)
pre = loc
return 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-1
while j>=0 and nums[j]|x!=nums[j]:
nums[j] |= x
ans = min(ans,abs(nums[j]-k))
j-=1
return ans
10/10 3162. 优质数对的总数 I
遍历每一对数是否优质
def numberOfPairs(nums1, nums2, k):
"""
:type nums1: List[int]
:type nums2: List[int]
:type k: int
:rtype: int
"""
ans = 0
for n1 in nums1:
for n2 in nums2:
if n1%(n2*k)==0:
ans+=1
return 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 math
cnt={}
for num in nums1:
if num%k>0:
continue
num = num//k
for d in range(1,int(math.sqrt(num))+1):
if num%d>0:
continue
cnt[d] = cnt.get(d,0)+1
if d**2<num:
cnt[num//d]=cnt.get(num//d,0)+1
ans = 0
for num in nums2:
ans += cnt.get(num,0)
return ans
10/12 3158. 求出出现两次数字的 XOR 值
从头遍历 记录出现过的数字 如果出现第二次则将其异或
def duplicateNumbersXOR(nums):
"""
:type nums: List[int]
:rtype: int
"""
ans = 0
s =set()
for num in nums:
if num in s:
ans ^= num
s.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")]*n
for 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]