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

LeetCode 每日一题 2024/9/9-2024/9/15

article 2024/11/14 12:43:24

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

9/9 2181. 合并零之间的节点

从头遍历 pre记录两个零之间节点之和
cur记录当前更新节点和数值前一个位置
如果遇到0 判断这个0之前是否有节点和如果有则更新cur

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def mergeNodes(head):
    """
    :type head: Optional[ListNode]
    :rtype: Optional[ListNode]
    """
    ans = head
    cur = ans
    pre = 0
    while head:
        if head.val==0:
            if pre!=0:
                cur = cur.next
                cur.val = pre
                pre = 0
        else:
            pre+=head.val
        head = head.next
    cur.next=None
    return ans.next

9/10 2552. 统计上升四元组

(i,j,k,l)
遍历j
统计i<j nums[i]<nums[k] i的个数
k<l nums[j]<nums[l] l的个数
且nums[k]<nums[j]
使用pre[x]表示0~j-1中小于x的个数可以快速得到j左侧小于nums[k]的个数
k从后往前统计大于nums[j]的个数
相乘即为该j得到的结果

def countQuadruplets(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    n=len(nums)
    pre=[0]*(n+1)
    ans = 0
    for j in range(n):
        suf = 0
        for k in range(n-1,j,-1):
            if nums[k]<nums[j]:
                ans += pre[nums[k]]*suf
            else:
                suf+=1
        for x in range(nums[j]+1,n+1):
            pre[x]+=1
    return ans

9/11 2555. 两个线段获得的最多奖品

滑动窗口
第二条线段右端点为pos[r] 第一条线段左端点为pos[l]
定义mx[i+1]表示第一条线段右端点<=pos[i] 最多覆盖奖品数

def maximizeWin(prizePositions, k):
    """
    :type prizePositions: List[int]
    :type k: int
    :rtype: int
    """
    n=len(prizePositions)
    
    if k*2+1>=(prizePositions[-1]-prizePositions[0]):
        return n
    ans = 0
    l = 0
    mx=[0]*(n+1)
    for r,p in enumerate(prizePositions):
        while p-prizePositions[l]>k:
            l+=1
        ans = max(ans,mx[l]+r-l+1)
        mx[r+1] = max(mx[r],r-l+1)
    return ans

9/12 2576. 求出最多标记下标

从小到大排序
总共有n个数最多有n//2对
ind为当前考虑的位置
从最小值ind=0开始寻找比他2大的数x
x从中间(n+1)//2开始寻找即可
找到第一个满足条件的那么再考虑第二小的数值以此类推
最终将ind2即为匹配总个数

def maxNumOfMarkedIndices(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    nums.sort()
    n =len(nums)
    ind = 0
    for x in nums[(n+1)//2:]:
        if nums[ind]*2<=x:
            ind+=1
    return ind*2

9/13 2398. 预算内的最多机器人数目

连续的机器人双指针[i,j]为运行的机器人坐标
单调递减队列q用来维护区间内chargetime最大值
s为当前区域内runningcost之和
遍历j 如果当前[i,j]不满足条件则将i往右移动

def maximumRobots(chargeTimes, runningCosts, budget):
    """
    :type chargeTimes: List[int]
    :type runningCosts: List[int]
    :type budget: int
    :rtype: int
    """
    ans = 0
    n=len(chargeTimes)
    s = 0
    q=[]
    i=0
    for j in range(n):
        s += runningCosts[j]
        while q and chargeTimes[q[-1]]<=chargeTimes[j]:
            q.pop()
        q.append(j)
        while i<=j and (j-i+1)*s+chargeTimes[q[0]]>budget:
            if q and q[0]==i:
                q = q[1:]
            s -= runningCosts[i]
            i+=1
        ans=max(ans,j-i+1)
    return ans

9/14 2390. 从字符串中移除星号

用栈来存放字符遇到星号则出栈一个字符

def removeStars(s):
    """
    :type s: str
    :rtype: str
    """
    st = []
    for c in s:
        if c=="*" :
            if st:
                st.pop()
        else:
            st.append(c)
    return "".join(st)

9/15 2848. 与车相交的点

将起点从小到大排序
依次计算起点是否在当前区域内是否可以扩展当前区域的终点
如果不再则计算新的区域起点

def numberOfPoints(nums):
    """
    :type nums: List[List[int]]
    :rtype: int
    """
    nums.sort()
    ans = 0
    st,ed =0,0
    for s,e in nums:
        if s>ed:
            if ed>0:
                ans += ed-st+1
            st,ed = s,e
        else:
            ed = max(ed,e)
    ans += ed-st+1
    return ans