1. 基本的计算器

题目地址：https://leetcode-cn.com/problems/basic-calculator-ii/

字符串转为整数实现：

string s = "458";int n = 0;
for (int i = 0; i < s.size(); i++) {char c = s[i];n = 10 * n + (c - '0');
}
// n 现在就等于 458

如果是数字，连续读取到 num
如果不是数字，就是遇到了下一个符号，之前的数字和符号就要存进栈中，遇到乘除法，拿出前一个数字做对应运算即可。

class Solution {
public:int calculate(string s) {stack <int> t;int res = 0, n = 0;char sign = '+';for(int i = 0; i < s.size(); ++i){if(s[i] >= '0')  n = n * 10 + (s[i] - '0');     //如果是数字，就继续进位if(s[i] < '0' && s[i] != ' ' || i == s.size()-1)                {    //当遇见新的符号或者是最后一位数字时，进行上一个符号的计算并将结果入栈int pre;switch(sign){case '+':t.push(n);break;case '-':t.push(-n);break;case '*':pre = t.top();t.pop();t.push(pre * n);break;case '/':pre = t.top();t.pop();t.push(pre / n);break;}sign = s[i];n = 0;              //上个符号的计算结束，符号更新，数字清0}}while(!t.empty())           //统计计算结果{res += t.top();t.pop();}return res;}
};

2.递增的三元子序列

方法一：

首先，新建两个变量 small 和 mid ，分别用来保存题目要我们求的长度为 3 的递增子序列的最小值和中间值。

接着，我们遍历数组，每遇到一个数字，我们将它和 small 和 mid 相比，若小于等于 small ，则替换 small；否则，若small<nums[i]<= mid，则替换 mid；否则，若大于 mid，则说明我们找到了长度为 3 的递增数组！

class Solution {
public:bool increasingTriplet(vector<int>& nums) {int len=nums.size();if(len<3)  return false;int small=INT_MAX, mid=INT_MAX;for(auto num:nums){if(num<=small){small=num;}else if(num<=mid){mid=num;}else if(num>mid){return true;}}return false;}
};

方法二：定义两个数组forward[i]和backward[i]，forward[i]从前向后遍历，保存[0, i]之间最小元素值，backward[i]从后向前遍历，保存[i, size - 1]间最大元素值。然后从前向后遍历，如果找到一个数满足forward[i] < nums[i] < backward[i]，则表示三元子序列存在。  （空间复杂度O(n)）

比如：
nums[i]: 8 3 5 1 6
forwa[i]: 8 3 3 1 1
backw[i]:8 6 6 6 6

class Solution {
public:bool increasingTriplet(vector<int>& nums) {int len=nums.size();if(len<3)  return false;vector<int> f(len,nums[0]);vector<int> b(len,nums.back());for(int i=1; i<len; i++){f[i]=min(f[i-1],nums[i]);}for(int i=len-2; i>=0; i--){b[i]=max(b[i+1],nums[i]);}for(int i=0; i<len; i++){if(f[i]<nums[i] && nums[i]<b[i]){return true;}}return false;}
};

3.LRU缓存机制

方法：哈希表+双向链表

范例：可以想象手机后台程序。

/* 缓存容量为 2 */
LRUCache cache = new LRUCache(2);
// 你可以把 cache 理解成一个队列
// 假设左边是队头，右边是队尾
// 最近使用的排在队头，久未使用的排在队尾
// 圆括号表示键值对 (key, val)cache.put(1, 1);
// cache = [(1, 1)]
cache.put(2, 2);
// cache = [(2, 2), (1, 1)]
cache.get(1);       // 返回 1
// cache = [(1, 1), (2, 2)]
// 解释：因为最近访问了键 1，所以提前至队头
// 返回键 1 对应的值 1
cache.put(3, 3);
// cache = [(3, 3), (1, 1)]
// 解释：缓存容量已满，需要删除内容空出位置
// 优先删除久未使用的数据，也就是队尾的数据
// 然后把新的数据插入队头
cache.get(2);       // 返回 -1 (未找到)
// cache = [(3, 3), (1, 1)]
// 解释：cache 中不存在键为 2 的数据
cache.put(1, 4);    
// cache = [(1, 4), (3, 3)]
// 解释：键 1 已存在，把原始值 1 覆盖为 4
// 不要忘了也要将键值对提前到队头

struct Node{int key;int value;Node* pre, * next;Node():key(0),value(0),pre(nullptr), next(nullptr){}Node(int _key, int _value):key(_key),value(_value),pre(nullptr), next(nullptr){}
};
class LRUCache {
public:Node* head;Node* tail;unordered_map<int, Node*> mp;int size;int capacity;LRUCache(int _capacity):capacity(_capacity),size(0) {head=new Node();  //伪头部（头哨兵）tail=new Node();  //伪尾部（尾哨兵）head->next=tail;tail->pre=head;}int get(int key) {if(!mp.count(key)){return -1;}//如果key存在Node* node=mp[key]; //1.通过哈希表定位moveToHead(node);   //2.移到头部return node->value;   //返回get要的node的值}void put(int key, int value) {//key不存在,加入if(!mp.count(key)){Node* node=new Node(key,value);  //1.new一个Nodemp[key]=node;                    //2.将Node加入哈希表addToHead(node);                 //3.加入头部++size;                          //4.size+1if(size>capacity){Node* removed=removeTail();   //超出容量，删除双向链表尾节点mp.erase(removed->key);       //删除哈希表中对应的项delete removed;--size;}}//key值存在，value需要更新else{Node* node=mp[key];   //1.通过哈希表定位node->value=value;    //2.更新value值moveToHead(node);     //3.移到头部}}void addToHead(Node* node){node->pre=head;node->next=head->next;head->next->pre=node;head->next=node;}void removeNode(Node* node){node->pre->next=node->next;node->next->pre=node->pre;}void moveToHead(Node* node){removeNode(node);addToHead(node);}Node* removeTail(){Node* node=tail->pre;removeNode(node);return node;}
};
/*** 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);*/

4. 最小栈

两个栈：

数据栈:常规操作即可，

“最小”栈：如果新元素<=数据栈栈顶元素或者最小栈为空，则也要push进最小栈(维持一个降序）

                 等价于遍历stack所有元素，把升序的数字都删除掉，留下一个从栈底到栈顶降序的栈。

class MinStack {
private:stack<int> stk;stack<int> min_stk;
public:/** initialize your data structure here. */MinStack() {}void push(int x) {stk.push(x);if(min_stk.empty() || x<=min_stk.top()){min_stk.push(x);}}void pop() {if(stk.top()==min_stk.top()){min_stk.pop();}stk.pop();}int top() {return stk.top();}int getMin() {return min_stk.top();}
};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(x);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->getMin();*/