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

9/25 460. LFU 缓存

freqMap 以频率为索引 存放一个双向链表 每个节点存放key,value,freq
keyMap 以key为索引存放在freqMap中的位置

from collections import defaultdict 
class Node:def __init__(self, key, val, pre=None, nex=None, freq=0):self.pre = preself.nex = nexself.freq = freqself.val = valself.key = keydef insert(self, nex):nex.pre = selfnex.nex = self.nexself.nex.pre = nexself.nex = nexdef create_linked_list():head = Node(0, 0)tail = Node(0, 0)head.nex = tailtail.pre = headreturn (head, tail)class LFUCache:def __init__(self, capacity: int):self.capacity = capacityself.size = 0self.minFreq = 0self.freqMap = defaultdict(create_linked_list)self.keyMap = {}def delete(self, node):if node.pre:node.pre.nex = node.nexnode.nex.pre = node.preif node.pre is self.freqMap[node.freq][0] and node.nex is self.freqMap[node.freq][-1]:self.freqMap.pop(node.freq)return node.keydef increase(self, node):node.freq += 1self.delete(node)self.freqMap[node.freq][-1].pre.insert(node)if node.freq == 1:self.minFreq = 1elif self.minFreq == node.freq - 1:head, tail = self.freqMap[node.freq - 1]if head.nex is tail:self.minFreq = node.freqdef get(self, key: int) -> int:if key in self.keyMap:self.increase(self.keyMap[key])return self.keyMap[key].valreturn -1def put(self, key: int, value: int) -> None:if self.capacity != 0:if key in self.keyMap:node = self.keyMap[key]node.val = valueelse:node = Node(key, value)self.keyMap[key] = nodeself.size += 1if self.size > self.capacity:self.size -= 1deleted = self.delete(self.freqMap[self.minFreq][0].nex)self.keyMap.pop(deleted)self.increase(node)

9/26 2582. 递枕头

n个人 经过2n-2次回到开始的人

def passThePillow( n, time):""":type n: int:type time: int:rtype: int"""time = time%(2*n-2)ans = 1+timeif ans>n:ans = n-(ans-n)return ans

9/27 1333. 餐厅过滤器

先按照rating和id排序
然后筛选符合条件的餐馆

def filterRestaurants(restaurants, veganFriendly, maxPrice, maxDistance):""":type restaurants: List[List[int]]:type veganFriendly: int:type maxPrice: int:type maxDistance: int:rtype: List[int]"""restaurants.sort(key=lambda x:(-x[1],-x[0]))ans = []for idx,_,v,p,dist in restaurants:if v>=veganFriendly and p<=maxPrice and dist<=maxDistance:ans.append(idx)return ans

9/28 2251. 花期内花的数目

差分数组 开花时+1 凋谢时-1

def fullBloomFlowers(flowers, people):""":type flowers: List[List[int]]:type people: List[int]:rtype: List[int]"""from collections import Counterdiff = Counter()for s,e in flowers:diff[s]+=1diff[e+1]-=1t = sorted(diff.keys())n = len(people)j=0s=0ans = [0]*nfor p,i in sorted(zip(people,range(n))):while j<len(t) and t[j]<=p:s+=diff[t[j]]j+=1ans[i] = sreturn ans

9/29 605. 种花问题

从头遍历 查看最多能种多少

def canPlaceFlowers(flowerbed, n):""":type flowerbed: List[int]:type n: int:rtype: bool"""cur = 0m=len(flowerbed)if m==1:if flowerbed[0]==0:cur+=1return cur>=nif flowerbed[0]==flowerbed[1]==0:cur+=1flowerbed[0]=1if flowerbed[m-1]==flowerbed[m-2]==0:cur+=1flowerbed[m-1]=1    if cur>=n:return Truefor i in range(1,len(flowerbed)-1):if flowerbed[i-1]==flowerbed[i]==flowerbed[i+1]==0:cur+=1flowerbed[i]=1if cur>=n:return Truereturn False

9/30 2136. 全部开花的最早一天

无论播种顺序 种花时间总和是不变的
先种生长时间最长的花

def earliestFullBloom(plantTime, growTime):""":type plantTime: List[int]:type growTime: List[int]:rtype: int"""ans=0t=0for p,g in sorted(zip(plantTime,growTime),key=lambda x:-x[1]):t+=pans = max(ans,t+g)return ans

10/1