LeetCode 每日一题 2024/9/30-2024/10/6

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

---

9/30 1845. 座位预约管理系统

最小堆

import heapq
class SeatManager(object):def __init__(self, n):""":type n: int"""self.l = [i for i in range(1,n+1)]heapq.heapify(self.l)def reserve(self):""":rtype: int"""return heapq.heappop(self.l)def unreserve(self, seatNumber):""":type seatNumber: int:rtype: None"""heapq.heappush(self.l, seatNumber)

---

10/1 983. 最低票价

dp(i) 表示从第i天到最后花的钱
如果i不需要出行 不买票
如果i需要出行 考虑买三种通行证哪种情况最优

def mincostTickets(days, costs):""":type days: List[int]:type costs: List[int]:rtype: int"""ds=set(days)du = [1,7,30]mem={}def dp(i):if i in mem:return mem[i]if i>365:return 0elif i in ds:ans = min(dp(i+d)+c for d,c in zip(du,costs))mem[i]=ansreturn anselse:ans = dp(i+1)mem[i]=ansreturn ansreturn dp(1)

---

10/2 1870. 准时到达的列车最小时速

二分寻找最小时速
check检查当前速度s是否能准时到达
保留两位小数将结果都乘以100

def minSpeedOnTime(dist, hour):""":type dist: List[int]:type hour: float:rtype: int"""n=len(dist)hr=round(hour*100)if hr<=100*(n-1):return -1def check(s):t = 0for i in range(n-1):t += (dist[i]+s-1)//st*=st+=dist[-1]return t*100<=hr*sl,r=1,10**7while l<r:mid = l+(r-l)//2if check(mid):r=midelse:l=mid+1return l

---

10/3 1928. 规定时间内到达终点的最小花费

dp[t][i]表示用t分钟到达城市i需要的最少通行费用
遍历时间t 在时间t内遍历所有的边 更新可以走的路

def minCost(maxTime, edges, passingFees):""":type maxTime: int:type edges: List[List[int]]:type passingFees: List[int]:rtype: int"""n=len(passingFees)dp = [[float("inf")]*n for _ in range(maxTime+1)]dp[0][0]=passingFees[0]for t in range(1,maxTime+1):for i,j,c in edges:if c<=t:dp[t][i]=min(dp[t][i],dp[t-c][j]+passingFees[i])dp[t][j]=min(dp[t][j],dp[t-c][i]+passingFees[j])ans = min(dp[t][n-1] for t in range(1,maxTime+1))return -1 if ans==float("inf") else ans

---

10/4 1227. 飞机座位分配概率

f(3)三人情况：
如果第一位乘客做在位置1上 1/3 第三位乘客一定坐在自己位置
如果第一位乘客坐在位置2上 1/3 第二位乘客坐在位置1上 1/2 第三位乘客坐在自己位置
1/3+1/31/2=1/2
f(4)四人同理 1/4+1/4f(3)+1/4*f(2)=1/2
如果n=1 那么概率100% 否则50%

def nthPersonGetsNthSeat(n):""":type n: int:rtype: float"""return 1 if n==1 else 0.5

---

10/5 2187. 完成旅途的最少时间

每辆车都需要不停的开
对时间进行二分查找
check检查在时间s内是否满足

def minimumTime(time, totalTrips):""":type time: List[int]:type totalTrips: int:rtype: int"""time.sort()def check(s):cnt = 0for t in time:cnt += s//tif cnt>=totalTrips:return Truereturn Falsel=1r=totalTrips*max(time)while l<r:mid =l+(r-l)//2if check(mid):r = midelse:l = mid+1return l

---

10/6 134. 加油站

可以从头记录gas 和cost的差值 记录油箱内的油 最终剩余不能为负数
找到中途油最小的时候 可以为负数
那么后一位必定可以完成

def canCompleteCircuit(gas, cost):""":type gas: List[int]:type cost: List[int]:rtype: int"""remain,start,mingas = 0,0,float('inf')for i in range(len(gas)):remain += gas[i]-cost[i]if remain<mingas:mingas = remainstart = (i+1)%(len(gas))if remain<0:return -1return start

---