专项 - 高频经典题 - 《Leetcode 刷题记录》

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_map cache; 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: stack inone; 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：
高频经典题 - 图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;
    }
};