蓝桥11

àì夳堔傛蜴生んèń 2023-01-10 11:45 160阅读 0赞

# 一LRU缓存机制 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70]

*  创建两个量，记录最大容量，记录缓存信息
 *  获取值：如果存在，先将当前值pop出，然后再插入尾部，如果没有直接返回-1
 *  存值：如果已经存在，则直接取出，然后插入到尾部，如果不存在直接插入尾部
 *  存值时需要判定当前缓存是否超出最大限制，如果超出限制，则需要移除最前面的

class LRUCache:
        def __init__(self, capacity: int):
            self.capacity = capacity
            self.caches = dict()
    
        def get(self, key: int) -> int:
            # 获取一个元素，那么这个元素就要从字典中取出，然后将其移动到最后去
            if key in self.caches:
                val = self.caches[key]
                self.caches.pop(key)
                self.caches[key] = val
            return self.caches.get(key,-1)
    
        def put(self, key: int, value: int) -> None:
            # 如果值已经存在则移除
            if key in self.caches:
                self.caches.pop(key)
            self.caches[key] = value
            if len(self.caches) > self.capacity:
                first = [*self.caches.keys()][0]
                self.caches.pop(first)
    
    
    
    # Your LRUCache object will be instantiated and called as such:
    # obj = LRUCache(capacity)
    # param_1 = obj.get(key)
    # obj.put(key,value)

# 二排序链表 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 1]

*  先记录链表的长度，
 *  创建一个数组，
 *  将链表中的数全部储存到数组中，
 *  然后通过数组Sort排序，
 *  最后用链表输出

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     public int val;
     *     public ListNode next;
     *     public ListNode(int val=0, ListNode next=null) {
     *         this.val = val;
     *         this.next = next;
     *     }
     * }
     */
    public class Solution {
        
        public ListNode SortList(ListNode head) {
        
            int len=0;
            ListNode p=head;
            while(p!=null)
            {
        
                len++;
                p=p.next;
            }
            int[] array=new int[len];
            p=head;
            for(int i=0;i<len;i++)
            {
        
                array[i]=p.val;
                p=p.next;
            }
            Array.Sort(array);
            p=head;
            for(int i=0;i<len;i++)
            {
        
                p.val=array[i];
                p=p.next;
            }
            return head;
        }
    }

# 三最小栈 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 2]

*  定义两个空列表来充当栈结构，一个存放真正栈中的数据，一个存放栈中最小值的数据，在第一次push的时候，不管这个值是多少，都要放到存放最小值这个列表里面，在之后push值得时候，比较，当前插入得值是不是比，minstack列表中最后一个值小，小得话就插入，当删除栈中得值时，也需要和minstack中最后一个值比较，因为这样会节省内存，将不必要得值删除

class MinStack:
    
        def __init__(self):
            """
            initialize your data structure here.
            """
            self.item = []
            self.minstack = []
    
        def push(self, x: int) -> None:
            self.item.append(x)
            if not self.minstack or self.minstack[-1] >= x:
                self.minstack.append(x)
    
        def pop(self) -> None:
            if self.item.pop() == self.minstack[-1]:
                self.minstack.pop()
        
        def top(self) -> int:
            return self.item[-1]
    
        def getMin(self) -> int:
            return self.minstack[-1]
            
    
    
    
    # Your MinStack object will be instantiated and called as such:
    # obj = MinStack()
    # obj.push(x)
    # obj.pop()
    # param_3 = obj.top()
    # param_4 = obj.getMin()

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70]: /images/20221119/3504399ba0be4d47a5572e27a254931a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210123220432795.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210123222230730.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA==,size_16,color_FFFFFF,t_70