Task12: 完成以下三个题目并打卡(1天)
146 LRU缓存机制
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类:
- LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
- int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
- void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。
进阶:你是否可以在 O(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
代码,继承LinkedHashMap类
import java.util.LinkedHashMap;
//leetcode submit region begin(Prohibit modification and deletion)
class LRUCache extends LinkedHashMap<Integer,Integer> {
private int capacity;
public LRUCache(int capacity) {
super(capacity,0.75F,true);
this.capacity=capacity;
}
public int get(int key) {
return super.getOrDefault(key,-1);
}
public void put(int key, int value) {
super.put(key,value);
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
//leetcode submit region end(Prohibit modification and deletion)
提示:
- 1 <= capacity <= 3000
- 0 <= key <= 3000
- 0 <= value <= 104
- 最多调用 3 * 104 次 get 和 put
148 排序链表
给你链表的头结点 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
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
return brokeList(head);
}
//使用快慢指针遍历到链表重点,从该中点断开,左右子链
private ListNode brokeList(ListNode head){
if (head==null||head.next==null)
return head;
ListNode slow=head;
ListNode fast=head;
while(fast!=null && fast.next!=null && fast.next.next!=null){
slow=slow.next;
fast=fast.next.next;
}
ListNode temp=slow.next;
slow.next=null;
ListNode left=brokeList(head);
ListNode right=brokeList(temp);
ListNode newhead=merge(left,right);
return newhead;
}
private ListNode merge(ListNode p1,ListNode p2){
ListNode dummy=new ListNode();
ListNode head=dummy;
while(p1!=null&&p2!=null){
if(p1.val<p2.val){
dummy.next=p1;
p1=p1.next;
}else{
dummy.next=p2;
p2=p2.next;
}
dummy=dummy.next;
}
while (p1!=null){
dummy.next=p1;
p1=p1.next;
dummy=dummy.next;
}
while (p2 != null) {
dummy.next=p2;
p2=p2.next;
dummy=dummy.next;
}
dummy.next=null;
return head.next;
}
}
//leetcode submit region end(Prohibit modification and deletion)
155 最小栈
设计一个支持 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 操作总是在非空栈上调用。
辅助栈和数据栈同步
import java.util.Stack;
public class MinStack {
// 数据栈
private Stack<Integer> data;
// 辅助栈
private Stack<Integer> helper;
/**
* initialize your data structure here.
*/
public MinStack() {
data = new Stack<>();
helper = new Stack<>();
}
// 思路 1:数据栈和辅助栈在任何时候都同步
public void push(int x) {
// 数据栈和辅助栈一定会增加元素
data.add(x);
if (helper.isEmpty() || helper.peek() >= x) {
helper.add(x);
} else {
helper.add(helper.peek());
}
}
public void pop() {
// 两个栈都得 pop
if (!data.isEmpty()) {
helper.pop();
data.pop();
}
}
public int top() {
if(!data.isEmpty()){
return data.peek();
}
throw new RuntimeException("栈中元素为空,此操作非法");
}
public int getMin() {
if(!helper.isEmpty()){
return helper.peek();
}
throw new RuntimeException("栈中元素为空,此操作非法");
}
}