146. LRU 缓存机制
难度中等1210
运用你所掌握的数据结构,设计和实现一个 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
提示:
1 <= capacity <= 3000
0 <= key <= 3000
0 <= value <= 10
最多调用
3 * 10
次get
和put
``` //构建双向链表单个节点结果 struct DListNode { DListNode prev; DListNode next; int key, value; DListNode(): key(0), value(0), prev(nullptr), next(nullptr){}; DListNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr){}; }; class LRUCache { private: //构建hash,声明大小,伪头部,伪尾部 unordered_mapcache; int capacity, size; DListNode head; DListNode tail; public: LRUCache(int _capacity):capacity(_capacity), size(0){ //初始化头部尾部
head = new DListNode();
tail = new DListNode();
head->next = tail;
tail->prev = head;
}
int get(int key) {
//未找到
if(!cache.count(key)){
return -1;
}
DListNode* node = cache[key];
moveTohead(node);
return node->value;
}
void put(int key, int value) {
//如果已经存在,那么更新值
if(cache.count(key)){
DListNode* node = cache[key];
node->value = value;
moveTohead(node);
}else{
//否则更新值
DListNode* node = new DListNode(key, value);
cache[key] = node;
addTohead(node);
size ++;
//如果超多容量了,那么执行删除最久未使用的元素
if(capacity < size){
DListNode *removeele = removeTail();
cache.erase(removeele->key);
delete removeele;
size --;
}
}
} //新建节点插入头部 void addTohead(DListNode* node){
DListNode* nex = head->next;
node->prev = head;
head->next = node;
node->next = nex;
nex->prev = node;
} //移除某个节点 void removeNode(DListNode* node){
node->prev->next = node->next;
node->next->prev = node->prev;
} //使用某个节点,遂更新头部顺序 void moveTohead(DListNode* node){
removeNode(node);
addTohead(node);
} DListNode* removeTail(){
//最后一个元素是tail->prev,第一个元素是head->next
DListNode* removeele = tail->prev;
removeNode(removeele);
return removeele;
} };
/**
- 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); */ ```
232. 用栈实现队列
难度简单335
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作(push
、pop
、peek
、empty
):
实现 MyQueue
类:
void push(int x)
将元素 x 推到队列的末尾int pop()
从队列的开头移除并返回元素int peek()
返回队列开头的元素boolean empty()
如果队列为空,返回true
;否则,返回false
说明:你只能使用标准的栈操作 —— 也就是只有
push to top
,peek/pop from top
,size
, 和is empty
操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
进阶:你能否实现每个操作均摊时间复杂度为
O(1)
的队列?换句话说,执行n
个操作的总时间复杂度为O(n)
,即使其中一个操作可能花费较长时间。
示例:
输入:
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出:
[null, null, null, 1, 1, false] ``` class MyQueue { private: stackinone; stack outone; public: /* Initialize your data structure here. / MyQueue() { }
/* Push element x to the back of queue. / void push(int x) {
inone.push(x);
}
/* Removes the element from in front of queue and returns that element. / int pop() {
//保证out非空
peek();
int ret = outone.top();
outone.pop();
return ret;
}
/* Get the front element. / int peek() {
//只有在outone为空时才执行,
if(outone.empty()){
while(!inone.empty()){
int x = inone.top();
inone.pop();
outone.push(x);
}
}
return outone.top();
}
/* Returns whether the queue is empty. / bool empty() {
return inone.empty() && outone.empty();
} };
/**
- Your MyQueue object will be instantiated and called as such:
- MyQueue* obj = new MyQueue();
- obj->push(x);
- int param_2 = obj->pop();
- int param_3 = obj->peek();
- bool param_4 = obj->empty(); */ ```
42. 接雨水
难度困难2099
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
示例 1:
输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。
示例 2:
输入:height = [4,2,0,3,2,5]
输出:9
暴力法
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
int ans = 0;
for(int i = 0; i < n; ++ i){
int l_max = 0, r_max = 0;
for(int j = 0; j <= i; ++ j){
l_max = max(l_max, height[j]);
}
for(int j = i; j < n; ++ j){
r_max = max(r_max, height[j]);
}
ans += min(l_max, r_max) - height[i];
}
return ans;
}
};
备忘录算法
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
if(!n) return 0;
int ans = 0;
vector<int> l_max(n), r_max(n);
l_max[0] = height[0], r_max[n - 1] = height[n - 1];
for(int i = 1; i < n; ++ i){
l_max[i] = max(l_max[i - 1], height[i]);
}
for(int i = n - 2; i >= 0; -- i){
r_max[i] = max(r_max[i + 1], height[i]);
}
for(int i = 0; i < n; ++ i){
ans += min(l_max[i], r_max[i]) - height[i];
}
return ans;
}
};
双指针
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
if(!n) return 0;
int ans = 0;
int l_max = height[0], r_max = height[n - 1];
int left = 0, right = n - 1;
while(left <= right){
//当前的l_max r_max是左右指针内的最大值
//与前两种算法还是有点不一样的
l_max = max(l_max, height[left]);
r_max = max(r_max, height[right]);
if(l_max < r_max){
ans += l_max - height[left];
left ++;
}else{
ans += r_max - height[right];
right --;
}
}
return ans;
}
};
224. 基本计算器
难度困难425
实现一个基本的计算器来计算一个简单的字符串表达式 s
的值。
示例 1:
输入:s = “1 + 1”
输出:2
示例 2:
输入:s = “ 2-1 + 2 “
输出:3
示例 3:
输入:s = “(1+(4+5+2)-3)+(6+8)”
输出:23
提示:
1 <= s.length <= 3 * 10
s
由数字、'+'
、'-'
、'('
、')'
、和' '
组成s
表示一个有效的表达式class Solution {
public:
void cal(stack<char>& ops, stack<int>& nums){
int o1 = nums.top();
nums.pop();
int o2 = nums.top();
nums.pop();
char op = ops.top();
ops.pop();
if(op == '+'){
int x = o1 + o2;
nums.push(x);
}else{
int x = o2 - o1;
nums.push(x);
}
}
int calculate(string s) {
stack<char> ops;
//防止第一个值是负号
stack<int> nums;
nums.push(0);
int n = s.size();
for(int i = 0; i < n; ++ i){
if(s[i] == ' '){
continue;
}else if(s[i] == '('){
ops.push(s[i]);
}else if(s[i] == ')'){
while(!ops.empty()){
//一直计算到匹配的括号为止
if(ops.top() == '('){
ops.pop();
break;
}else{
cal(ops, nums);
}
}
}else{//是数字或者加减号的情况
if(s[i] >= '0' && s[i] <= '9'){
int j = i;
int cnt = 0;
while(j < n && (s[j] >= '0' && s[j] <= '9')){
cnt = cnt * 10 + (s[j] - '0');
j ++;
}
i = j - 1;
nums.push(cnt);
}else{
//新操作入栈前计算掉可以算的
while(!ops.empty() && ops.top() != '(')
cal(ops, nums);
ops.push(s[i]);
}
}
}
while(!ops.empty()){
cal(ops, nums);
}
return nums.top();
}
};
440. 字典序的第K小数字
难度困难194
给定整数 n
和 k
,找到 1
到 n
中字典序第 k
小的数字。
注意:1 ≤ k ≤ n ≤ 10。
示例 :
输入:
n: 13 k: 2
输出:
10
解释:
字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9],所以第二小的数字是 10。
using LL = long long;
class Solution {
public:
//用来确定某一个前缀下可以有多少种情况(多少个子节点)
LL getCount(LL prefix, LL n){
//整体思路是用下一个前缀的起点减去当前前缀的起点
LL cur = prefix;
LL nex = prefix + 1;//下一个前缀
LL count = 0;
//在本题的情况下,+1就相当于获得了下一个前缀,比如这个+1如果引起了数的进位,那么两个数之间夹的节点个数就很多了
//*10则只是在同一个前缀下加层数,这是一个十叉树问题
while(cur <= n){
//这里要取n + 1和nex的最小值,因为我们无法保证nex是小于上界的,当大于上界时,要用n + 1来限制
//必须要用n + 1不然会少计算一个上界本身
count += min(n + 1, nex) - cur;
//加了一层
cur *= 10;
nex *= 10;
}
return count;
}
int findKthNumber(int n, int k) {
LL p = 1;//相当于是一个指针,用来协助找k的位置
LL prefix = 1;//前缀
while(p < k){
LL count = getCount(prefix, n);
//如果初值加上算出的当前前缀的节点个数大于k个了,那么我们就缩小了范围,找到了上界,我们继续缩小这个上界就行了
if(p + count > k){
//细化,加一层,继续找
prefix *= 10;
p ++;
}else if(p + count <= k){
prefix ++;
p += count;
}
}
return prefix;
}
};