LeetCode 每日一题 2023/11/27-2023/12/3
记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
目录
- 11/27 907. 子数组的最小值之和
- 11/28 1670. 设计前中后队列
- 11/29 2336. 无限集中的最小数字
- 11/30 1657. 确定两个字符串是否接近
- 12/1 2661. 找出叠涂元素
- 12/2 1094. 拼车
- 12/3 1423. 可获得的最大点数
11/27 907. 子数组的最小值之和
对于某位置i arr[i]对答案的贡献 需要找到min(b)=arr[i]的数组
在i位置左侧有连续l个数大于arr[i] ,i位置右侧有连续r个大于arr[i]
那么子数组一共有m=(l+1)(r+1)个 min(b) = arr[i]
所以i位置的数贡献了m次 marr[i]
找左侧大于等于自己的个数
右侧同样的方法 为防止重复计算 右侧严格大于自己
def sumSubarrayMins(arr):
"""
:type arr: List[int]
:rtype: int
"""
MOD = 10**9+7
ans = 0
n = len(arr)
stack = []
l = [0]*n
r = [0]*n
for i,v in enumerate(arr):
while stack and v<=arr[stack[-1]]:
stack.pop()
if stack:
l[i] = i - stack[-1]
else:
l[i] = i+1
stack.append(i)
stack = []
for i in range(n-1,-1,-1):
while stack and arr[i]<arr[stack[-1]]:
stack.pop()
if stack:
r[i] = stack[-1]-i
else:
r[i] = n-i
stack.append(i)
for i in range(n):
ans = (ans+l[i]*r[i]*arr[i])%MOD
return ans
11/28 1670. 设计前中后队列
将队列分为前后两部分处理
class FrontMiddleBackQueue(object):
def __init__(self):
self.num = 0
self.l = []
self.r = []
def pushFront(self, val):
"""
:type val: int
:rtype: None
"""
self.num +=1
self.l = [val]+self.l
if len(self.l)>len(self.r):
self.r = [self.l[-1]]+self.r
self.l = self.l[:-1]
def pushMiddle(self, val):
"""
:type val: int
:rtype: None
"""
self.num += 1
if len(self.l)==len(self.r):
self.r = [val]+self.r
else:
self.l.append(val)
def pushBack(self, val):
"""
:type val: int
:rtype: None
"""
self.num += 1
self.r.append(val)
if len(self.r)>len(self.l)+1:
self.l.append(self.r[0])
self.r = self.r[1:]
def popFront(self):
"""
:rtype: int
"""
v = -1
if self.num==0:
return v
if len(self.l)>0:
v = self.l[0]
self.l = self.l[1:]
else:
v = self.r[0]
self.r = self.r[1:]
self.num -=1
if len(self.r)>len(self.l)+1:
self.l.append(self.r[0])
self.r = self.r[1:]
return v
def popMiddle(self):
"""
:rtype: int
"""
v = -1
if self.num==0:
return v
if len(self.l)==len(self.r):
v = self.l[-1]
self.l = self.l[:-1]
else:
v = self.r[0]
self.r = self.r[1:]
self.num-=1
return v
def popBack(self):
"""
:rtype: int
"""
v = -1
if self.num==0:
return v
v=self.r[-1]
self.num-=1
self.r = self.r[:-1]
if len(self.l)>len(self.r):
self.r = [self.l[-1]]+self.r
self.l = self.l[:-1]
return v
11/29 2336. 无限集中的最小数字
记录已经丢弃的数集合 s
记录当前最小数 cur
class SmallestInfiniteSet(object):
def __init__(self):
self.s = set()
self.cur = 1
def popSmallest(self):
"""
:rtype: int
"""
v = self.cur
self.s.add(v)
self.cur += 1
while self.cur in self.s:
self.cur+=1
return v
def addBack(self, num):
"""
:type num: int
:rtype: None
"""
if num in self.s:
self.s.remove(num)
if num < self.cur:
self.cur = num
11/30 1657. 确定两个字符串是否接近
统计所有出现次数 只要次数相同 两个字符串即接近
def closeStrings(word1, word2):
"""
:type word1: str
:type word2: str
:rtype: bool
"""
from collections import Counter
if len(word1)!=len(word2):
return False
return set(word1)==set(word2) and Counter(Counter(word1).values())==Counter(Counter(word2).values())
12/1 2661. 找出叠涂元素
遍历矩阵记录每个数的位置
遍历arr 记录每行每列当前未被涂色的个数
def firstCompleteIndex(arr, mat):
"""
:type arr: List[int]
:type mat: List[List[int]]
:rtype: int
"""
m,n=len(mat),len(mat[0])
mem = {}
for i in range(m):
for j in range(n):
mem[mat[i][j]]=(i,j)
row = [n]*m
col = [m]*n
for i,v in enumerate(arr):
a,b = mem[v]
row[a]-=1
col[b]-=1
if row[a]==0 or col[b]==0:
return i
12/2 1094. 拼车
最小堆储存需要下车的信息(t,num) 在位置t需要下num个人
当前为f 将所有小于等于f的下车人数都下车
def carPooling(trips, capacity):
"""
:type trips: List[List[int]]
:type capacity: int
:rtype: bool
"""
import heapq
trips.sort(key = lambda x:(x[1],x[2]))
cur = 0
m = []
for num,f,t in trips:
while m and m[0][0]<=f:
loc,v = heapq.heappop(m)
cur -= v
cur += num
if cur>capacity:
return False
heapq.heappush(m, (t,num))
return True
12/3 1423. 可获得的最大点数
取前后k个数 剩余中间n-k个数
滑动窗口判断n-k个数和最小
def maxScore(cardPoints, k):
"""
:type cardPoints: List[int]
:type k: int
:rtype: int
"""
total = sum(cardPoints)
l = len(cardPoints)-k
cur = sum(cardPoints[:l])
s = cur
for i in range(len(cardPoints)-l):
print(cur,cardPoints[i],cardPoints[i+l])
cur = cur-cardPoints[i]+cardPoints[i+l]
s = min(s,cur)
return total - s