算法题

LRU

class LRUCache:
    def __init__(self, capacity: int):
        self.cap=capacity
        self.list=OrderedDict()
    def get(self, key: int) -> int:
        if key in self.list:
            self.list.move_to_end(key)
            return self.list[key]
        else:
            return -1
    def put(self, key: int, value: int) -> None:
        if key in self.list:
            self.list[key]=value
            self.list.move_to_end(key)
        else:
            self.list[key]=value
        if len(self.list)>self.cap:
            self.list.popitem(last=False)

回溯算法，回文

class Solution:
    def huiwen(self,s):
        if s==s[::-1]:
            return True
        return False
    def backtrace(self,l,s,ret):
        if not s:
            list=l.copy()
            ret.append(list)
            return
        for i in range(1,len(s)+1):
            if self.huiwen(s[:i]):
                l.append(s[:i])
                self.backtrace(l,s[i:],ret)
                l.pop()
    def partition(self, s: str) -> List[List[str]]:
        l=[]
        ret=[]
        self.backtrace(l,s,ret)
        return ret

堆，第k大

import heapq
from typing import List

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # 维护一个大小为 k 的最小堆
        heap = []
        for num in nums:
            heapq.heappush(heap, num)
            if len(heap) > k:
                heapq.heappop(heap)
        # 堆顶即为第 k 大的元素
        return heap[0]

list(heapq.merge([1, 3, 5], [2, 4, 6]))   # [1, 2, 3, 4, 5, 6]
heap = []
heapq.heappush(heap, 5)
data = [3, 1, 4, 1, 5]
heapq.heapify(data)