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

---