LeetCode 每日一题 2023/9/25-2023/10/1

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

---

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 = pre
        self.nex = nex
        self.freq = freq
        self.val = val
        self.key = key
        
    def insert(self, nex):
        nex.pre = self
        nex.nex = self.nex
        self.nex.pre = nex
        self.nex = nex
    
def create_linked_list():
    head = Node(0, 0)
    tail = Node(0, 0)
    head.nex = tail
    tail.pre = head
    return (head, tail)

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.size = 0
        self.minFreq = 0
        self.freqMap = defaultdict(create_linked_list)
        self.keyMap = {}

    def delete(self, node):
        if node.pre:
            node.pre.nex = node.nex
            node.nex.pre = node.pre
            if node.pre is self.freqMap[node.freq][0] and node.nex is self.freqMap[node.freq][-1]:
                self.freqMap.pop(node.freq)
        return node.key
        
    def increase(self, node):
        node.freq += 1
        self.delete(node)
        self.freqMap[node.freq][-1].pre.insert(node)
        if node.freq == 1:
            self.minFreq = 1
        elif self.minFreq == node.freq - 1:
            head, tail = self.freqMap[node.freq - 1]
            if head.nex is tail:
                self.minFreq = node.freq

    def get(self, key: int) -> int:
        if key in self.keyMap:
            self.increase(self.keyMap[key])
            return self.keyMap[key].val
        return -1

    def put(self, key: int, value: int) -> None:
        if self.capacity != 0:
            if key in self.keyMap:
                node = self.keyMap[key]
                node.val = value
            else:
                node = Node(key, value)
                self.keyMap[key] = node
                self.size += 1
            if self.size > self.capacity:
                self.size -= 1
                deleted = self.delete(self.freqMap[self.minFreq][0].nex)
                self.keyMap.pop(deleted)
            self.increase(node)




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

---

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+time
    if ans>n:
        ans = n-(ans-n)
    return ans



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

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

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

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

---

9/29 605. 种花问题

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

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

---

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

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

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

10/1 121. 买卖股票的最佳时机

1.笨办法 比较每个值和之后的最大值的差值
2.记录最低点的值 遍历数组获得当前值与最低值的差值
实时更新最低点

def maxProfit(prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    res = 0
    for i in range(len(prices)-1):
        if max(prices[i+1:])-prices[i]>res:
            res = max(prices[i+1:])-prices[i]
    return res

def maxProfit2(prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    if len(prices)==0:
            return 0
    res = 0
    minvalue = prices[0]
    for i in range(1,len(prices)):
        minvalue = min(minvalue,prices[i])
        res = max(res,prices[i]-minvalue)
    return res


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

---