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 * 10getput ``` //构建双向链表单个节点结果 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_map cache; int capacity, size; DListNode head; DListNode tail; public: LRUCache(int _capacity):capacity(_capacity), size(0){

    1. //初始化头部尾部
    2. head = new DListNode();
    3. tail = new DListNode();
    4. head->next = tail;
    5. tail->prev = head;

    }

    int get(int key) {

    1. //未找到
    2. if(!cache.count(key)){
    3. return -1;
    4. }
    5. DListNode* node = cache[key];
    6. moveTohead(node);
    7. return node->value;

    }

    void put(int key, int value) {

    1. //如果已经存在,那么更新值
    2. if(cache.count(key)){
    3. DListNode* node = cache[key];
    4. node->value = value;
    5. moveTohead(node);
    6. }else{
    7. //否则更新值
    8. DListNode* node = new DListNode(key, value);
    9. cache[key] = node;
    10. addTohead(node);
    11. size ++;
    12. //如果超多容量了,那么执行删除最久未使用的元素
    13. if(capacity < size){
    14. DListNode *removeele = removeTail();
    15. cache.erase(removeele->key);
    16. delete removeele;
    17. size --;
    18. }
    19. }

    } //新建节点插入头部 void addTohead(DListNode* node){

    1. DListNode* nex = head->next;
    2. node->prev = head;
    3. head->next = node;
    4. node->next = nex;
    5. nex->prev = node;

    } //移除某个节点 void removeNode(DListNode* node){

    1. node->prev->next = node->next;
    2. node->next->prev = node->prev;

    } //使用某个节点,遂更新头部顺序 void moveTohead(DListNode* node){

    1. removeNode(node);
    2. addTohead(node);

    } DListNode* removeTail(){

    1. //最后一个元素是tail->prev,第一个元素是head->next
    2. DListNode* removeele = tail->prev;
    3. removeNode(removeele);
    4. 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
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作(pushpoppeekempty):
实现 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: stack inone; stack outone; public: /* Initialize your data structure here. / MyQueue() {

    }

    /* Push element x to the back of queue. / void push(int x) {

    1. inone.push(x);

    }

    /* Removes the element from in front of queue and returns that element. / int pop() {

    1. //保证out非空
    2. peek();
    3. int ret = outone.top();
    4. outone.pop();
    5. return ret;

    }

    /* Get the front element. / int peek() {

    1. //只有在outone为空时才执行,
    2. if(outone.empty()){
    3. while(!inone.empty()){
    4. int x = inone.top();
    5. inone.pop();
    6. outone.push(x);
    7. }
    8. }
    9. return outone.top();

    }

    /* Returns whether the queue is empty. / bool empty() {

    1. 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:
高频经典题 - 图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

暴力法

  1. class Solution {
  2. public:
  3. int trap(vector<int>& height) {
  4. int n = height.size();
  5. int ans = 0;
  6. for(int i = 0; i < n; ++ i){
  7. int l_max = 0, r_max = 0;
  8. for(int j = 0; j <= i; ++ j){
  9. l_max = max(l_max, height[j]);
  10. }
  11. for(int j = i; j < n; ++ j){
  12. r_max = max(r_max, height[j]);
  13. }
  14. ans += min(l_max, r_max) - height[i];
  15. }
  16. return ans;
  17. }
  18. };

备忘录算法

  1. class Solution {
  2. public:
  3. int trap(vector<int>& height) {
  4. int n = height.size();
  5. if(!n) return 0;
  6. int ans = 0;
  7. vector<int> l_max(n), r_max(n);
  8. l_max[0] = height[0], r_max[n - 1] = height[n - 1];
  9. for(int i = 1; i < n; ++ i){
  10. l_max[i] = max(l_max[i - 1], height[i]);
  11. }
  12. for(int i = n - 2; i >= 0; -- i){
  13. r_max[i] = max(r_max[i + 1], height[i]);
  14. }
  15. for(int i = 0; i < n; ++ i){
  16. ans += min(l_max[i], r_max[i]) - height[i];
  17. }
  18. return ans;
  19. }
  20. };

双指针

  1. class Solution {
  2. public:
  3. int trap(vector<int>& height) {
  4. int n = height.size();
  5. if(!n) return 0;
  6. int ans = 0;
  7. int l_max = height[0], r_max = height[n - 1];
  8. int left = 0, right = n - 1;
  9. while(left <= right){
  10. //当前的l_max r_max是左右指针内的最大值
  11. //与前两种算法还是有点不一样的
  12. l_max = max(l_max, height[left]);
  13. r_max = max(r_max, height[right]);
  14. if(l_max < r_max){
  15. ans += l_max - height[left];
  16. left ++;
  17. }else{
  18. ans += r_max - height[right];
  19. right --;
  20. }
  21. }
  22. return ans;
  23. }
  24. };

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 表示一个有效的表达式
    1. class Solution {
    2. public:
    3. void cal(stack<char>& ops, stack<int>& nums){
    4. int o1 = nums.top();
    5. nums.pop();
    6. int o2 = nums.top();
    7. nums.pop();
    8. char op = ops.top();
    9. ops.pop();
    10. if(op == '+'){
    11. int x = o1 + o2;
    12. nums.push(x);
    13. }else{
    14. int x = o2 - o1;
    15. nums.push(x);
    16. }
    17. }
    18. int calculate(string s) {
    19. stack<char> ops;
    20. //防止第一个值是负号
    21. stack<int> nums;
    22. nums.push(0);
    23. int n = s.size();
    24. for(int i = 0; i < n; ++ i){
    25. if(s[i] == ' '){
    26. continue;
    27. }else if(s[i] == '('){
    28. ops.push(s[i]);
    29. }else if(s[i] == ')'){
    30. while(!ops.empty()){
    31. //一直计算到匹配的括号为止
    32. if(ops.top() == '('){
    33. ops.pop();
    34. break;
    35. }else{
    36. cal(ops, nums);
    37. }
    38. }
    39. }else{//是数字或者加减号的情况
    40. if(s[i] >= '0' && s[i] <= '9'){
    41. int j = i;
    42. int cnt = 0;
    43. while(j < n && (s[j] >= '0' && s[j] <= '9')){
    44. cnt = cnt * 10 + (s[j] - '0');
    45. j ++;
    46. }
    47. i = j - 1;
    48. nums.push(cnt);
    49. }else{
    50. //新操作入栈前计算掉可以算的
    51. while(!ops.empty() && ops.top() != '(')
    52. cal(ops, nums);
    53. ops.push(s[i]);
    54. }
    55. }
    56. }
    57. while(!ops.empty()){
    58. cal(ops, nums);
    59. }
    60. return nums.top();
    61. }
    62. };

440. 字典序的第K小数字

难度困难194
给定整数 nk,找到 1n 中字典序第 k 小的数字。
注意:1 ≤ k ≤ n ≤ 10。
示例 :
输入:
n: 13 k: 2

输出:
10

解释:
字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9],所以第二小的数字是 10。

  1. using LL = long long;
  2. class Solution {
  3. public:
  4. //用来确定某一个前缀下可以有多少种情况(多少个子节点)
  5. LL getCount(LL prefix, LL n){
  6. //整体思路是用下一个前缀的起点减去当前前缀的起点
  7. LL cur = prefix;
  8. LL nex = prefix + 1;//下一个前缀
  9. LL count = 0;
  10. //在本题的情况下,+1就相当于获得了下一个前缀,比如这个+1如果引起了数的进位,那么两个数之间夹的节点个数就很多了
  11. //*10则只是在同一个前缀下加层数,这是一个十叉树问题
  12. while(cur <= n){
  13. //这里要取n + 1和nex的最小值,因为我们无法保证nex是小于上界的,当大于上界时,要用n + 1来限制
  14. //必须要用n + 1不然会少计算一个上界本身
  15. count += min(n + 1, nex) - cur;
  16. //加了一层
  17. cur *= 10;
  18. nex *= 10;
  19. }
  20. return count;
  21. }
  22. int findKthNumber(int n, int k) {
  23. LL p = 1;//相当于是一个指针,用来协助找k的位置
  24. LL prefix = 1;//前缀
  25. while(p < k){
  26. LL count = getCount(prefix, n);
  27. //如果初值加上算出的当前前缀的节点个数大于k个了,那么我们就缩小了范围,找到了上界,我们继续缩小这个上界就行了
  28. if(p + count > k){
  29. //细化,加一层,继续找
  30. prefix *= 10;
  31. p ++;
  32. }else if(p + count <= k){
  33. prefix ++;
  34. p += count;
  35. }
  36. }
  37. return prefix;
  38. }
  39. };