网站建设ASP心得体会/友情连接出售

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

---

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+7ans = 0n = len(arr)stack = []l = [0]*nr = [0]*nfor 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+1stack.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]-ielse:r[i] = n-istack.append(i)for i in range(n):ans = (ans+l[i]*r[i]*arr[i])%MODreturn ans

---

11/28 1670. 设计前中后队列

将队列分为前后两部分处理

class FrontMiddleBackQueue(object):def __init__(self):self.num = 0self.l = []self.r = []def pushFront(self, val):""":type val: int:rtype: None"""self.num +=1self.l = [val]+self.lif len(self.l)>len(self.r):self.r = [self.l[-1]]+self.rself.l = self.l[:-1]def pushMiddle(self, val):""":type val: int:rtype: None"""self.num += 1if len(self.l)==len(self.r):self.r = [val]+self.relse:self.l.append(val)def pushBack(self, val):""":type val: int:rtype: None"""self.num += 1self.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 = -1if self.num==0:return vif 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 -=1if len(self.r)>len(self.l)+1:self.l.append(self.r[0])self.r = self.r[1:]return vdef popMiddle(self):""":rtype: int"""v = -1if self.num==0:return vif 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-=1return vdef popBack(self):""":rtype: int"""v = -1if self.num==0:return vv=self.r[-1]self.num-=1self.r = self.r[:-1]if len(self.l)>len(self.r):self.r = [self.l[-1]]+self.rself.l = self.l[:-1]return v

---

11/29 2336. 无限集中的最小数字

记录已经丢弃的数集合 s
记录当前最小数 cur

class SmallestInfiniteSet(object):def __init__(self):self.s = set()self.cur = 1def popSmallest(self):""":rtype: int"""v = self.curself.s.add(v)self.cur += 1while self.cur in self.s:self.cur+=1return vdef 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 Counterif len(word1)!=len(word2):return Falsereturn 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]*mcol = [m]*nfor i,v in enumerate(arr):a,b = mem[v]row[a]-=1col[b]-=1if 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 heapqtrips.sort(key = lambda x:(x[1],x[2]))cur = 0m = []for num,f,t in trips:while m and m[0][0]<=f: loc,v = heapq.heappop(m)cur -= vcur += numif cur>capacity:return Falseheapq.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)-kcur  = sum(cardPoints[:l])s = curfor 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

---