当前位置：首页 > article >正文

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

article 2024/10/10 3:30:55

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

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 0
        elif i in ds:
            ans = min(dp(i+d)+c for d,c in zip(du,costs))
            mem[i]=ans
            return ans
        else:
            ans = dp(i+1)
            mem[i]=ans
            return ans
    return 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 -1
    
    def check(s):
        t = 0
        for i in range(n-1):
            t += (dist[i]+s-1)//s
        t*=s
        t+=dist[-1]
        return t*100<=hr*s
    
    l,r=1,10**7
    while l<r:
        mid = l+(r-l)//2
        if check(mid):
            r=mid
        else:
            l=mid+1
    return 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 = 0
        for t in time:
            cnt += s//t
            if cnt>=totalTrips:
                return True
        return False
    l=1
    r=totalTrips*max(time)
    while l<r:
        mid =l+(r-l)//2
        if check(mid):
            r = mid
        else:
            l = mid+1
    return 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 = remain
            start = (i+1)%(len(gas))
    if remain<0:
        return -1
    return start