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

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

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

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

class ListNode(object):def __init__(self, val=0, next=None):self.val = valself.next = next
def mergeNodes(head):""":type head: Optional[ListNode]:rtype: Optional[ListNode]"""ans = headcur = anspre = 0while head:if head.val==0:if pre!=0:cur = cur.nextcur.val = prepre = 0else:pre+=head.valhead = head.nextcur.next=Nonereturn 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 = 0for j in range(n):suf = 0for k in range(n-1,j,-1):if nums[k]<nums[j]:ans += pre[nums[k]]*sufelse:suf+=1for x in range(nums[j]+1,n+1):pre[x]+=1return 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 nans = 0l = 0mx=[0]*(n+1)for r,p in enumerate(prizePositions):while p-prizePositions[l]>k:l+=1ans = 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 = 0for x in nums[(n+1)//2:]:if nums[ind]*2<=x:ind+=1return 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 = 0n=len(chargeTimes)s = 0q=[]i=0for 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+=1ans=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 = 0st,ed =0,0for s,e in nums:if s>ed:if ed>0:ans += ed-st+1st,ed = s,eelse:ed = max(ed,e)ans += ed-st+1return ans