#|【Task12】LeetCode腾讯精选打卡腾讯精选练习|50|题|链表|数据

一、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

文章图片

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例2

文章图片

输入：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)

运行结果：

文章图片

三、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

复杂度分析：