Python教程

[Leetcode]数据结构之自己设计数据结构——python版本

本文主要是介绍[Leetcode]数据结构之自己设计数据结构——python版本,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

本篇文章根据labuladong的算法小抄汇总自己设计数据结构的常见算法,采用python3实现

文章目录

  • LRU算法
    • LRU缓存机制,T146
  • 单调栈结构
    • 单调栈模板
    • 下一个更大元素Ⅰ,T496
    • 每日温度,T739
    • [循环数组],下一个更大元素Ⅱ,T503
  • 单调队列
    • 滑动窗口最大值,T239
  • 二叉堆实现优先级队列
    • 二叉堆
    • 优先级队列
    • 实现上浮swim和下沉sink
    • 实现delMax和insert
  • 队列实现栈,T225
  • 栈实现队列,T232

LRU算法

LRU(Least Recently Used)算法是一种缓存淘汰机制。计算机的缓存容量有限,如果缓存满了就要删除一些内容,那么删除哪些内容呢?LRU认为最近使用过的数据是有用的,很久没用的就是无用的,内存满了就优先删掉很久没用过的数据。

LRU缓存机制,T146

题目:设计并实现一个满足LRU缓存约束的数据结构。

要求:put和get时间复杂度为O(1)

解决:哈希链表

  1. 用python自带的哈希+双向链表OrderedDict
class LRUCache(collections.OrderedDict):
    def __init__(self,capacity):
        super().__init__()
        self.capacity = capacity
    def get(self,key):
        if key not in self:
            return -1
        self.move_to_end(key)
        return self[key]
    def put(self,key,value):
        if key in self:
            self.move_to_end(key)
        self[key] = value
        if len(self) > self.capacity:
            self.popitem(last=False)
  1. 自己实现
#双向链表
class DLinkedNode:
    def __init__(self,key=0,value=None):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None
    
class LRUCache:
    #以正整数作为容量初始化LRU缓存
    def __init__(self,capacity):
        self.cache = dict()
        #伪头部节点;伪尾部节点
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = self.capacity
        self.size = 0
        
    #如果关键字key存在于缓存中,则返回关键字的值,否则返回-1
    def get(self,key):
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self.moveToHead(node)
        return node.value
        
    #如果key已经存在,则变更其value;如key不存在,则向缓存中插入key-value;如插入导致容量超限,则逐出最久未使用的关键字
    def put(self,key,value):
        if key not in self.cache:
            node = DLinkedNode(key,value)
            self.cache[key] = value
            self.addToHead(node)
            self.size += 1
            if self.size > self.capacity:
                removed = self.removeTail()
                self.cache.pop(removed.key)
                self.size -= 1
        else:
            node = self.cache[key]
            node.value = value
            self.moveToHead(node)
        
    def addToHead(self,node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
        
    def removeNode(self,node):
    	node.prev.next = node.next
        node.next.prev = node.prev
        
    def moveToHead(self,node):
        self.removeNode(node)
        self.addToHead(node)    	
    
    def removeTail(self):
        node = self.tail.prev
        self.removeNode(node)
        return node

单调栈结构

栈:先进后出。

单调栈:每次新元素入栈后,栈内元素都保持有序(单调递增或单调递减)

单调栈只处理一种典型问题Next Greater Element。

单调栈模板

给你一个数组nums,返回一个等长的结果数组,结果数组中对应索引存储着下一个更大元素,如果没有更大的元素,就存-1。

def nextGreaterElement(nums):
    n = len(nums)
    res = [0 for i in range(n)]
    s = []
    for i in range(n-1,-1,-1):
        while s and s[-1] <= nums[i]:
            s.pop()
        res[i] = -1 if not s else s[-1]
        s.append(nums[i])
    return res

下一个更大元素Ⅰ,T496

def nextGreaterElement(nums1,nums2):
    res = {}
    stack = []
    for num in reversed(nums2):
        while stack and num >= stack[-1]:
            stack.pop()
        res[num] = stack[-1] if stack else -1
        stack.append(num)
    return [res[num] for num in nums1]

每日温度,T739

数组T存放近几天的气温,返回等长数组,计算对于每一天,至少等多少天才能等到一个更暖和的气温,如果等不到填0

def dailyTemperatures(T):
    n = len(T)
    res = [0 for i in range(T)]
    s = []
    for i in range(n-1,-1,-1):
        while s and T[s[-1]] <= T[i]:
            s.pop()
        res[i] = 0 if not s else s[-1]-i
        s.append(i)
    return res

[循环数组],下一个更大元素Ⅱ,T503

常用套路:将数组长度翻倍

def nextGreaterElements(nums):
    n = len(nums)
    res = [0 for i in range(n)]
    stack = []
    for i in range(2*n-1,-1,-1):
        while s and s[-1] <= nums[i % n]:
            s.pop()
        res[i % n] = s[-1] if s else -1
        s.append(nums[i%n])
    return res

单调队列

单调队列主要解决滑动窗口相关问题

滑动窗口最大值,T239

题目:给定数组nums和正整数k,有一个大小为k的窗口在nums上从左到右滑动,请你输出每次窗口中k个元素的最大值。

#实现单调队列数据结构
class MonotonicQueue:
    def __init__(self):
        self.q = LinkedList()
    def push(self,n):
        while q and q.getLast() < n:
            q.pollLast()
        q.addLast(n)
    def max_(self):
        rerurn q.getFirst()
    def pop(self,n):
        if n == q.getFirst:
            q.pollFirst()
    
def maxSlidingWindow(nums,k):
    window = MonotonicQueue()
    res = []
    for i in range(len(nums)):
        #先把前k-1个填满
        if i < k - 1:
            window.push(nums[i])
        else:
            window.push(nums[i])
            res.append(window.max_())
            window.pop(nums[i-k+1])
    return res

官方解答:

def maxSlidingWindow(nums,k):
    n = len(nums)
    q = collections.deque()
    for i in range(k):
        while q and nums[i] >= nums[q[-1]]:
            q.pop()
        q.append(i)
    res = [nums[q[0]]]
    for i in range(k,n):
        while q and nums[i] >= nums[q[-1]]:
            q.pop()
        q.append(i)
        while q[0] <= i - k:
            q.popleft()
        res.append(nums[q[0]])
    return res

二叉堆实现优先级队列

二叉堆

【储存在列表里的完全二叉树】二叉堆在逻辑上是完全二叉树,只不过存储在数组里。一般的链表二叉树,我们操作节点的指针,而在数组里,我们把数组索引作为指针。

二叉堆主要操作:sink(下沉);swim(上浮)

二叉堆主要应用:堆排序;优先级队列

注意:第一个索引0空着不用

#数组第0位空着不用
#父节点索引
def parent(root):
    return root // 2
#左孩子索引
def left(root):
    return root * 2
#右孩子索引
def right(root):
    return root * 2 + 1

最大堆:每个节点都大于等于它的两个子节点

最小堆:每个节点都小于等于它的两个子节点

优先级队列

性质:插入或删除元素时,元素会自动排序。

底层原理:二叉堆的操作

主要API:insert插入一个元素,delMax删除最大元素(最小堆则为delMin删除最小元素)

实现上浮swim和下沉sink

对于最大堆来说,可能出现以下破坏其性质的情况:

(1)如果某个节点A比它的子节点小,那么A就不配做父节点,应该下沉

(2)如果某个节点A比它的父节点大,那么A就不应该做子节点,应该上浮

实现delMax和insert

insert:把要插入的元素添加到堆底的最后,然后让其上浮到正确位置

delMax:把堆顶元素A和堆底最后的元素B对调,然后删除A,最后让B下沉到正确位置

class MaxPQ:
    def __init__(self,N=0,pq=[]):
        self.N = N
        self.pq = pq
    def parent(self,i):
        return i // 2
    def left(self,i):
        return i * 2
    def right(self,i):
        return i * 2 + 1    
    #交换两个元素
    def exch(self,i,j):
        pq[i],pq[j] = pq[j],pq[i]
    #比较两个元素
    def less(self,i,j):
        return pq[i] < pq[j]
    #上浮    
	def swim(self,k):
    	while (k > 1) and MaxPQ.less(MaxPQ.parent(k),k):
            MaxPQ.exch(MaxPQ.parent(k),k)
            k = MaxPQ.parent(k)
    #下沉
    def sink(self,k):
        while MaxPQ.left(k) <= N:
            older = MaxPQ.left(k)
            if (MaxPQ.right(k) <= N) and (MaxPQ.less(older,MaxPQ.right(k))):
                older = maxPQ.right(k)
            if maxPQ.less(older,k):
                break
            maxPQ.exch(k,older)
            k = older
    #插入一个新元素
    def insert(self,e):
        N += 1
        pq[N] = e
        MaxPQ.swim(N)
    #删除堆顶元素
    def delMax(self):
        maxValue = pq[1]
        MaxPQ.exch(1,N)
        pq[N] = None
        N -= 1
        maxPQ.sink(1)
        return maxValue

队列实现栈,T225

队列:先进先出

栈:先进后出

class MyStack:
    def __init__(self):
        self.q = []
        self.topelem = 0
        
    def push(self,x):
        self.q.append(x)
        self.topelem = x
        
    def top(self):
        return self.topelem
        
    def pop(self):
        size = len(self.q)
        while size > 2
            self.q.append(self.q.pop(0))
            size -= 1
        self.topelem = self.q[0]
        self.q.append(self.q.pop(0))
        return self.q.pop(0)
        
    def empty(self):
        return not self.q

pop时间复杂度为O(N),其它都为O(1)

栈实现队列,T232

img
class MyQueue:
    def __init__(self):
        self.s1 = []
        self.s2 = []
        
    #将元素x推到队列末尾
    #顺序添加进s1
    def push(self,x):
    	self.s1.append(x)
    
    #返回队列开头的元素
    #当s2为空时,可以把s1所有元素取出添加进s2
    def peek(self):
    	if not self.s2:
            while self.s1:
                self.s2.push(self.s1.pop())
        return self.s2[-1]
        
    #从队列开头移除并返回元素
    def pop(self):
    	self.peek()
        return self.s2.pop()
        
    #队列是否为空
    def empty(self):
        return (not self.s1) and (not self.s2)

最坏时间复杂度为O(N),但均摊时间复杂度为O(1),因为对于一个元素,最多只可能被搬运一次。

这篇关于[Leetcode]数据结构之自己设计数据结构——python版本的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!