#|【Task12】LeetCode腾讯精选打卡

一、No0146. LRU 缓存机制 题目 运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类:

  • LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
  • void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。
进阶:你是否可以在 O(1) 时间复杂度内完成这两种操作?
说明: 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例
  • 输入: [2,2,1]
  • 输出: 1
输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
解题代码(Python3)
class LRUCache:def __init__(self, capacity: int): self.index = 0 self.maxLength = capacity self.Length = 0 self.dataDict = { } self.dataQueue = []def get(self, key: int) -> int: if key in self.dataDict[key]: #移动到队列尾 return self.dataDict[key] else: return -1 def put(self, key: int, value: int) -> None: if self.Length < self.maxLength: #填入dict,并且新增至队列尾 pass else: #删除dict,新增dict,然后将队列头删除,队列尾加入 pass

复杂度分析:
  • 时间复杂度O(n),由于存在删除List元素
  • 空间复杂度O(n),实际上是O(2n)
二、No0148. 排序链表 题目 给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。
进阶:
你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?
示例1 #|【Task12】LeetCode腾讯精选打卡
文章图片

  • 输入:head = [4,2,1,3]
  • 输出:[1,2,3,4]
示例2 #|【Task12】LeetCode腾讯精选打卡
文章图片

  • 输入:head = [-1,5,3,4,0]
  • 输出:[-1,0,3,4,5]
示例3
  • 输入:head = []
  • 输出:[]
提示
  • 链表中节点的数目在范围 [0, 5 * 104] 内
  • -105 <= Node.val <= 105
思路: 遍历存入进List,然后经过排序后重新按序赋值。
解题代码(Python3)
class Solution: def sortList(self, head: ListNode) -> ListNode: #假设是对值排序 放到List里面排序之后再放入 p = head result = [] while p: result.append(p.val) p = p.next p = head result.sort() i = 0 while p: p.val = result[i] i += 1 p = p.next return head

复杂度分析:
  • 时间复杂度O(nlogn)
  • 空间复杂度O(n)
运行结果: #|【Task12】LeetCode腾讯精选打卡
文章图片

三、No0155. 最小栈 题目 设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
示例
  • 输入:
    [“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]
    [[],[-2],[0],[-3],[],[],[],[]]
  • 输出:
    [null,null,null,null,-3,null,0,-2]
  • 解释:
    MinStack minStack = new MinStack();
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    minStack.getMin(); --> 返回 -3.
    minStack.pop();
    minStack.top(); --> 返回 0.
    minStack.getMin(); --> 返回 -2.
提示
  • pop、top 和 getMin 操作总是在 非空栈 上调用。
解题代码(Python3)
class MinStack:def __init__(self): """ initialize your data structure here. """ self.dataList = []self.minNum = 0#还有一种 就是每次push时拿到最小def push(self, x: int) -> None: if self.dataList == []: self.minNum = x else: if x < self.minNum: self.minNum = x self.dataList.append(x)def pop(self) -> None: temp = self.dataList[-1] del self.dataList[-1] if temp == self.minNum and self.dataList != []: self.minNum = min(self.dataList) return tempdef top(self) -> int: return self.dataList[-1]def getMin(self) -> int: return self.minNum

复杂度分析:
  • 时间复杂度 O(n)
  • 空间复杂度 O(n)
运行结果: 【#|【Task12】LeetCode腾讯精选打卡】#|【Task12】LeetCode腾讯精选打卡
文章图片

    推荐阅读