北京网站建设设计公司浩森宇特,做商贸网站,宁波外贸公司一览表,中山祥云网站建设记录了初步解题思路 以及本地实现代码#xff1b;并不一定为最优 也希望大家能一起探讨 一起进步 目录 9/30 1845. 座位预约管理系统10/1 983. 最低票价10/2 1870. 准时到达的列车最小时速10/3 1928. 规定时间内到达终点的最小花费10/4 1227. 飞机座位分配概率10/5 2187. 完成…记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步 目录 9/30 1845. 座位预约管理系统10/1 983. 最低票价10/2 1870. 准时到达的列车最小时速10/3 1928. 规定时间内到达终点的最小花费10/4 1227. 飞机座位分配概率10/5 2187. 完成旅途的最少时间10/6 134. 加油站 9/30 1845. 座位预约管理系统 最小堆 import heapq
class SeatManager(object):def __init__(self, n)::type n: intself.l [i for i in range(1,n1)]heapq.heapify(self.l)def reserve(self)::rtype: intreturn heapq.heappop(self.l)def unreserve(self, seatNumber)::type seatNumber: int:rtype: Noneheapq.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: intdsset(days)du [1,7,30]mem{}def dp(i):if i in mem:return mem[i]if i365:return 0elif i in ds:ans min(dp(id)c for d,c in zip(du,costs))mem[i]ansreturn anselse:ans dp(i1)mem[i]ansreturn ansreturn dp(1) 10/2 1870. 准时到达的列车最小时速 二分寻找最小时速 check检查当前速度s是否能准时到达 保留两位小数将结果都乘以100 def minSpeedOnTime(dist, hour)::type dist: List[int]:type hour: float:rtype: intnlen(dist)hrround(hour*100)if hr100*(n-1):return -1def check(s):t 0for i in range(n-1):t (dist[i]s-1)//st*stdist[-1]return t*100hr*sl,r1,10**7while lr:mid l(r-l)//2if check(mid):rmidelse:lmid1return l10/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: intnlen(passingFees)dp [[float(inf)]*n for _ in range(maxTime1)]dp[0][0]passingFees[0]for t in range(1,maxTime1):for i,j,c in edges:if ct: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,maxTime1))return -1 if ansfloat(inf) else ans 10/4 1227. 飞机座位分配概率 f(3)三人情况 如果第一位乘客做在位置1上 1/3 第三位乘客一定坐在自己位置 如果第一位乘客坐在位置2上 1/3 第二位乘客坐在位置1上 1/2 第三位乘客坐在自己位置 1/31/31/21/2 f(4)四人同理 1/41/4f(3)1/4*f(2)1/2 如果n1 那么概率100% 否则50% def nthPersonGetsNthSeat(n)::type n: int:rtype: floatreturn 1 if n1 else 0.5 10/5 2187. 完成旅途的最少时间 每辆车都需要不停的开 对时间进行二分查找 check检查在时间s内是否满足 def minimumTime(time, totalTrips)::type time: List[int]:type totalTrips: int:rtype: inttime.sort()def check(s):cnt 0for t in time:cnt s//tif cnttotalTrips:return Truereturn Falsel1rtotalTrips*max(time)while lr:mid l(r-l)//2if check(mid):r midelse:l mid1return l 10/6 134. 加油站 可以从头记录gas 和cost的差值 记录油箱内的油 最终剩余不能为负数 找到中途油最小的时候 可以为负数 那么后一位必定可以完成 def canCompleteCircuit(gas, cost)::type gas: List[int]:type cost: List[int]:rtype: intremain,start,mingas 0,0,float(inf)for i in range(len(gas)):remain gas[i]-cost[i]if remainmingas:mingas remainstart (i1)%(len(gas))if remain0:return -1return start
