🚑栈和队列🚑

转自：🔥【github】

• 7.整数反转
• 9.回文数
• 20.有效的括号
• 232.用栈实现队列
• 225.用队列实现栈
• 155.最小栈
• 150.逆波兰表达式求值
• 394.字符串解码
• 133.克隆图
• 200.岛屿数量
• 84.柱状图中最大的矩形
• 542.01矩阵
• 622.设计循环队列

整数反转

Leetcode给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转

解题思路

• 从低到高位依次加入队列，然后输出
• 注意反转后的溢出问题

  int reverse(int x) {
      int rev=0;
      while(x!=0){
          if(rev>INT_MAX/10 || rev<INT_MIN/10) return 0;
          rev=rev*10+x%10;
           x/=10;
       }
       return rev;
  }

回文数

Leetcode判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

解题思路

• 一位数一定是回文数
• 负数或者个位是0的一定不是回文数。
• 反转整数，只反转到一半，然后进行比较（对于奇数个数得回文数，去掉中间位再比较）

  bool isPalindrome(int x) {
      if(x>=0 && x<=9)return true;
      if(x%10==0 || x<0)return false;
      int rev=0;
      while(x>rev){
          rev=rev*10+x%10;
          x/=10;
      }
      return rev/10==x || rev==x;
  }

有效的括号

Leetcode给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ ===的字符串，判断字符串是否有效。
有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

解题思路

• 个数为奇数肯定不对
• 首字符为右符号肯定不对
• 遇到左符号入栈
• 遇到右符号与栈顶元素进行匹配，配对则出栈，否则返回false，最后栈空了则说明是有效的

   bool isValid(string s) {
      if(s.size()%2)return false;
      if(s[0]=='}' || s[0]==')' || s[0]==']') return false;
      stack<char> sck;
      for(int i=0;s[i]!='\0';++i){
          if(s[i]=='[' || s[i]=='{' || s[i]=='('){
              sck.push(s[i]);
          }else{
              if(s[i]=='}' && sck.top()!='{') return false;
              if(s[i]==']' && sck.top()!='[') return false;
              if(s[i]==')' && sck.top()!='(') return false;
              sck.pop();
          }
      } 
      return sck.empty();
  }

用栈实现队列

Leetcode

• 栈的顺序为后进先出，而队列的顺序为先进先出。
• 使用两个栈实现队列，一个元素需要经过两个栈才能出队列

  class MyQueue {
  public:   
      void push(int x) {
          stack1.push(x);
      }
      
      int pop() {
         if(stack2.empty()){                  //只有当stack2为空时，才重新加载
              while(!stack1.empty()){         //stack1装填到stack2
                  stack2.push(stack1.top());  //c++ pop()函数返回值额为void
                  stack1.pop();
              }
          }
          int res=stack2.top();
          stack2.pop();
          return res;
      }
      
      int peek() {
          if(stack2.empty()){
              while(!stack1.empty()){
                  stack2.push(stack1.top());
                  stack1.pop();
              }
          }
          return stack2.top();
      }
      
      bool empty() {
          return stack1.empty() && stack2.empty();
      }
  private:
      stack<int> stack1;
      stack<int> stack2;
  };

用队列实现栈

方法一

Leetcode

• 一个队列
• push之前判断当前是否为空
• 不为空则将元素插入到尾部，前面的全部弹出再去入队
• push时间复杂度O(n),而pop的时间复杂度O(1)

class MyStack {
public:
    MyStack() {}
    
    void push(int x) {
        if(queue1.empty()){
            queue1.push(x);
        }else{
            int cnt=queue1.size();
            queue1.push(x);
            while(cnt-->0){
                queue1.push(queue1.front());
                queue1.pop();
            }
        }
    }
    
    int pop() {
        int res=queue1.front();
        queue1.pop();
        return res;
    }
    
    int top() {
        return queue1.front();
    }
    
    bool empty() {
        return queue1.empty();
    }
private:
    queue<int> queue1;
};

方法二

• push时间复杂度O(1),而pop的时间复杂度O(n)

  private:
      queue<int> q1; 
      void push(int x) {
          q1.push(x);
      }
      int pop() {
          queue<int>q2;
          while(q1.size()>1){
              q2.push(q1.front());
              q1.pop();
          }
          int res=q1.front();
          q1=q2;
          return res;
      }   
      int top() {
          queue<int>q2(q1);
          while(q1.size()>1){
              q1.pop();
          }
          int res=q1.front();
          q1=q2;
          return res;
      }
      bool empty() {
          return q1.empty();
      }
  };

  最小栈

  Leetcode
• 维护两个栈：数据栈 最小栈
• 同步简单，异步节省最小栈空间
• 异步：当新插入的元素比最小值还小（或相等）时，插入最小栈，出栈时只有当两个栈栈顶元素相同时，两个栈同时pop，否则只有数据栈pop
• 同步：两个栈的大小始终相同，只是最小栈每次都插入当前最小值，出栈时两栈同时pop

class MinStack {
public: 
    void push(int x) {
        dataStack.push(x);
        if(miniStack.empty()){
            miniStack.push(x);
        }else{
            int min=miniStack.top();
            if(min>=x){                         //相等时也要插入
                miniStack.push(x);
            }
        }
    }
    
    void pop() {
        if( dataStack.top()==miniStack.top()){  //只有相等时才同时弹出否则只弹出dataStack
            dataStack.pop();
            miniStack.pop();
        }else{
            dataStack.pop();
        }
    }
    
    int top() {
        return dataStack.top();
    }
    
    int getMin() {
        return miniStack.top();
    }
private:
    stack<int> dataStack;
    stack<int> miniStack;
};

逆波兰表达式求值

leetcode根据 逆波兰表示法，求表达式的值。
有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例

输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

解题思路

• 典型的后缀表达式，栈得应用场景
• 遍历字符串数组，遇到字符就弹出栈顶两个元素进行运算，再将结果填入栈。遇到数字就直接入栈
• 这里使用了c语言stoi()函数直接将字符串转换为数字，也可以使用ASCII值转，atoi(string.c_str())

  int evalRPN(vector<string>& tokens) {
      stack<int> sck;
      for (auto it : tokens) {
          if (it == "+") {
              int a = sck.top();
              sck.pop();
              int b = sck.top();
              sck.pop();
              sck.push(b + a);
          } else if (it == "-") {
              int a = sck.top();
              sck.pop();
              int b = sck.top();
              sck.pop();
              sck.push(b - a);
          } else if (it == "*"){
              int a = sck.top();
              sck.pop();
              int b = sck.top();
              sck.pop();
              sck.push(a * b);
          } else if (it == "/"){
              int a = sck.top();
              sck.pop();
              int b = sck.top();
              sck.pop();
              sck.push(b / a);
          } else {
              sck.push(stoi(it));
          }
      }
      return sck.top();
  }

字符串解码

leetcode给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例

输入：s = "3[a]2[bc]"
输出："aaabcbc"

输入：s = "3[a2[c]]"
输出："accaccacc"

解题思路

• 一看到[ ] 匹配得题，首先想到使用栈，既有数字又有字母，想到使用两个栈
• 这类题基本思路就是找到什么时候入栈，什么时候出栈。
• 同时涉及了遍历数组，提取数字和提取字符串算法
• 本题的当遍历到’[‘时同时入栈，遍历到’]’时出栈进行操作,strSck.top()可以理解为到当前为止前面已经展开的字符串，cur为刚刚[ ]中合成的字符串。
• 讲道理此题过于难以理解🐛

  string decodeString(string s) {
      string cur = "";
      stack<int> numSck;
      stack<string> strSck;
      int val = 0;
      for (int i = 0; s[i] != '\0'; ++i) {
          if (s[i] >= '0' && s[i] <= '9') {
              val = val * 10 + s[i] - '0';
          } else if (s[i] == '[') {
              numSck.push(val);
              strSck.push(cur);
              val = 0;
              cur = "";
          } else if ((s[i] >= 'a' && s[i] <='z') || (s[i] >= 'A' && s[i] <= 'Z')) {
              cur += s[i];
          } else if (s[i] == ']') {
              int cnt = numSck.top();
              numSck.pop();
              for (int i = 0; i < cnt; ++i) {
                  strSck.top() += cur;
              }
              cur = strSck.top();
              strSck.pop();
          }
      }
      return cur;
  }

克隆图

leetcode给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
图中的每个节点都包含它的值val int 和其邻居的列表vector[Node]。

示例

输入：adjList = [[2,4],[1,3],[2,4],[1,3]]
输出：[[2,4],[1,3],[2,4],[1,3]]
解释：
图中有 4 个节点。
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。

解题思路

• 图得遍历有两种深度DFS和广度BFS
• 深度优先遍历：使用递归同时还需要记录哪些是已经复制过得，函数得意义是复制并返回复制得结点，如果发现该结点已经复制过，直接返回复制得结点
• 由于是深拷贝，一定需要new，所以该结点没有复制，就new一个新结点，并标记已经拷贝过。
• 新得结点还需要链接它得邻接点，遍历它得所以邻接点，并继续复制。

  Node* isClone[101];
  Node* cloneGraph(Node* node) {
      if (node == NULL) return NULL;
      if (isClone[node->val] != NULL) return isClone[node->val];
      Node* newNode = new Node(node->val);
      isClone[node->val] = newNode;
      for (auto it : node->neighbors) {
          newNode->neighbors.push_back(cloneGraph(it));
      }
      return newNode;
  }

• 使用广度优先遍历就必须使用队列
• 首先先复制第一个结点并加入到队列中，然后进入循环，注意：队列加入得都是原结点不是新创建得结点，因为新结点还没有链接邻接点
• 对每个出队列得结点广度遍历，即遍历完它得所有邻接点，没有复制过得就新建并加入队列，最后链接新建的结点和邻接点

   Node* isClone[101];
   Node* cloneGraph(Node* node) {
       if (!node) return nullptr;
       queue<Node*> que;
       Node* newNode = new Node(node->val);
       isClone[node->val] = newNode;
       que.push(node);
       while (!que.empty()) {
Node* cur = que.front();
que.pop();
for (Node* e : cur->neighbors) {
       if (isClone[e->val] == NULL) {
	que.push(e);
	isClone[e->val] = new Node(e->val);
       }
       isClone[cur->val]->neighbors.push_back(isClone[e->val]);
}
        }
        return newNode;
    }

岛屿数量

leetcode给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

示例

输入:
[
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
输出: 1

DFS解题思路

• 把二维表格当作一个图来处理，每个结点的上下左右都是它的邻接点
• 两个for循环遍历二维数组，当遇到1时开始深度遍历它的邻接点，凡是dfs遍历途中遇到1的都改为0，直到所有相连的1全部改为0，这就算找到了一个岛，后面继续遍历改后的二维数组。

  int numIslands(vector<vector<char>>& grid) {
      int cnt = 0;
      for (int i = 0; i < grid.size(); ++i) {
          for (int j = 0; j < grid[0].size(); ++j) {
              if (grid[i][j] == '1') {
                  dfs(grid, i, j);
                  cnt++;
              }
          }
      }
      return cnt;
  }
  
  void dfs(vector<vector<char> >& grid, int x, int y) {
      int row = grid.szie() - 1;
      int col = grid[0].szie() - 1;
      grid[row][col] = '0';
      if (x < row && grid[x + 1][y] == '1') dfs(grid, x + 1, y);
      if (x > 0   && grid[x - 1][y] == '1') dfs(grid, x - 1, y);
      if (y < col && grid[x][y + 1] == '1') dfs(grid, x, y + 1);
      if (y > 0   && grid[x][y - 1] == '1') dfs(grid, x, y - 1);
  }

  BFS解题

• md，超出时间限制找了一个多小时的原因，一个字一个字对比最后才发现，一个=写成==，日啊。第二次犯这种错误了

  int numIslands(vector<vector<char>>& grid) {
      if (grid.empty()) return 0;
      int row = grid.size();
      int col = grid[0].size();
      int cnt = 0;
      queue<pair<int, int> > que;
      for (int i = 0; i < row; ++i) {
          for (int j = 0; j < col; ++j) {
              if (grid[i][j] == '1') {
                  cnt++;
                  grid[i][j] = '0';
                  que.push(pair(i, j));
                  while (!que.empty()) {
                      pair<int, int> cur = que.front();
                      que.pop();
                      int x = cur.first;
                      int y = cur.second;
                      if (x - 1 >= 0  && grid[x - 1][y] == '1') {
                          grid[x - 1][y] = '0';
                          que.push(pair<int, int>(x - 1, y));
                      }  
                      if (y - 1 >= 0  && grid[x][y - 1] == '1') {
                          que.push(pair<int, int>(x, y - 1));
                          grid[x][y - 1] = '0';
                      }  
                      if (x + 1 < row && grid[x + 1][y] == '1') {
                          que.push(pair<int, int>(x + 1, y));
                          grid[x + 1][y] = '0';
                      }
                      if (x + 1 < row && grid[x + 1][y] == '1') {
                          que.push(pair<int, int>(x + 1, y));
                          grid[x + 1][y] = '0';
                      }
                      if (y + 1 < col && grid[x][y + 1] == '1') {
                          que.push(pair<int, int>(x, y + 1));
                          grid[x][y + 1] = '0';
                      }
                  }
              }
          }
      } 
      return cnt;
  }

柱状图中最大的矩形

leetcode给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例

dd
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

解题思路

• 暴力解法可以枚举以每个柱形为高度的最大矩形的面积。具体来说就是：依次遍历柱形的高度，对于每一个高度分别向两边扩散，求出以当前高度为矩形的最大宽度多少。
• 左边看一下，看最多能向左延伸多长，找到大于等于当前柱形高度的最左边元素的下标；
• 右边看一下，看最多能向右延伸多长；找到大于等于当前柱形高度的最右边元素的下标。
• 以下题解会超时。

  int largestRectangleArea(vector<int>& heights) {
      if (heights.empty()) return 0;
      int res = INT_MIN;
      for (int i = 0; i < heights.size(); ++i) {
          int left = i, right = i; 
          while (left > 0 && heights[left - 1] >= heights[i]) left--;
          while (right < heights.size() - 1 && heights[right + 1] >= heights[i]) right++;
          int len = right - left + 1;
          res = max(res, heights[i] * len);
      }
      return res;
  }

01矩阵

leetcode
给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。

示例

0 0 0
0 1 0
1 1 1
输出:

0 0 0
0 1 0
1 2 1

解题思路

• 理解题意比较难，题意要求我们找到每个1离0最近的距离，正常会想到遍历每个1，最每个1进行DFS或者BFS，但是这样就涉及到对上下左右每个分支的距离最短筛选的操作。时间复杂度也会大大增加。
• 因此我们可以反过来遍历，先遍历找到所有0的结点，他的4个上下左右分支点一定是1，而1的上下左右4个未访问过的分支点一定是2，依次展开。
• BFS解法一般都涉及队列的使用：

  int off[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
  vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
      int row = matrix.size();
      int col = matrix[0].size();
      // 初始化
      bool isVis[row][col];
      for (int i = 0; i < row; ++i) {
          memset(isVis[i], 0, col);
      }
      // 入队列的顺序：所有0的位置，所有离0点距离为1的点，所有离0点距离为2的点....
      queue<pair<int, int>> que;
      for (int i = 0; i < row; ++i) {
          for (int j = 0; j < col; ++j) {
              if (matrix[i][j] == 0) {
                  que.push({i, j});
                  isVis[i][j] = true;
              }
          }
      }
      
      while (!que.empty()) {
          int x = que.front().first;
          int y = que.front().second;
          que.pop();
          for (int i = 0; i < 4; ++i) {
              int xi = x + off[i][0];
              int yi = y + off[i][1];
              if (xi >= 0 && xi < row && yi >= 0 && yi < col && !isVis[xi][yi]) {
                  isVis[xi][yi] = true;
                  matrix[xi][yi] = matrix[x][y] + 1; 
                  que.push({xi, yi});
              }
          }
      }
      return matrix;
  }

设计循环队列

leetcode设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：

MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

解题思路

• 两个指针，head和tail，注意满队和空队的条件，满队时：tail就在head的前一格，空队时：tail和head都指向-1。
• 凡涉及到循环，指针移动后都要对size取模才能保证不超过size大小。

  class MyCircularQueue {
  private:
      vector<int> data;
      int size;
      int head;
      int tail;
  
  public:
      MyCircularQueue(int k) {
          data.resize(k);
          size = k;
          head = -1;
          tail = -1;
      }
      
      bool enQueue(int value) {
          if (isFull()) return false;
          if (isEmpty()) head = 0;
          tail = (tail + 1) % size;
          data[tail] = value;
          return true;
      }
      
      bool deQueue() {
          if (isEmpty()) return false;
          if (head == tail) {     // 只剩一个元素时
              head = -1;
              tail = -1;
              return true;
          }
          head = (head + 1) % size;
          return true;
      }
      
      int Front() {
          if (isEmpty()) return -1;
          return data[head];
      }
      
      int Rear() {
          if (isEmpty()) return -1;
          return data[tail];
      }
      
      bool isEmpty() {
          return head == -1;
      }
      
      bool isFull() {
          return (tail + 1) % size == head;
      }
  };