瘦身网站开发目的,上海网站建设书生商友,同城做哪个网站推广效果好,首都之窗记录了初步解题思路 以及本地实现代码#xff1b;并不一定为最优 也希望大家能一起探讨 一起进步 目录 11/27 907. 子数组的最小值之和11/28 1670. 设计前中后队列11/29 2336. 无限集中的最小数字11/30 1657. 确定两个字符串是否接近12/1 2661. 找出叠涂元素12/2 1094. 拼车12…记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步 目录 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(l1)(r1)个 min(b) arr[i] 所以i位置的数贡献了m次 marr[i] 找左侧大于等于自己的个数 右侧同样的方法 为防止重复计算 右侧严格大于自己 def sumSubarrayMins(arr)::type arr: List[int]:rtype: intMOD 10**97ans 0n len(arr)stack []l [0]*nr [0]*nfor i,v in enumerate(arr):while stack and varr[stack[-1]]:stack.pop()if stack:l[i] i - stack[-1]else:l[i] i1stack.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 (ansl[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: Noneself.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: Noneself.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: Noneself.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: intv -1if self.num0: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: intv -1if self.num0: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: intv -1if self.num0:return vvself.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: intv self.curself.s.add(v)self.cur 1while self.cur in self.s:self.cur1return vdef addBack(self, num)::type num: int:rtype: Noneif 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: boolfrom 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: intm,nlen(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: boolimport 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 curcapacity: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: inttotal sum(cardPoints)l len(cardPoints)-kcur sum(cardPoints[:l])s curfor i in range(len(cardPoints)-l):print(cur,cardPoints[i],cardPoints[il])cur cur-cardPoints[i]cardPoints[il]s min(s,cur)return total - s
