LeetCode 每日一题 2024/9/9-2024/9/15
记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
目录
- 9/9 2181. 合并零之间的节点
- 9/10 2552. 统计上升四元组
- 9/11 2555. 两个线段获得的最多奖品
- 9/12 2576. 求出最多标记下标
- 9/13 2398. 预算内的最多机器人数目
- 9/14 2390. 从字符串中移除星号
- 9/15 2848. 与车相交的点
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