队列&栈-05

内容概要，对队列&栈相关进行小结，用以下题目对 队列、BFS、栈、DFS 进行复习：

• 用栈实现队列
• 用队列实现栈
• 字符串解码
• 图像渲染
• 01 矩阵
• 钥匙和房间

题目：用栈实现队列

使用栈实现队列的下列操作：

• push(x): 将一个元素放入队列的尾部
• pop(): 从队列首部移除元素
• peek(): 返回队列首部的元素
• empty(): 返回队列是否为空

示例：

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

说明:

• 你只能使用标准的栈操作：也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可
• 假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）

个人理解：
栈是后入先出，用两个后入先出实现一个先入先出，那很简单了，负负得正。
我们定义两个栈，一个栈用来输入数据，一个栈用来输出数据，在输出栈为空的时候，把输入栈内容推到输出栈就行，这样数据就反向了。实现了队列效果。

代码如下(C++):

class MyQueue {
public:
  stack<int> inStack;   // 定义输入栈
  stack<int> outStack;  // 定义输出栈
  /** 检查方法 */
  void check(){   // 检查输出栈是否有数据，没有的话，就把输入栈缓存的弄进来
    if(outStack.empty()){
      while(!inStack.empty()){
        outStack.push(inStack.top());
        inStack.pop();
      }
    }
  }
  /** 在此初始化数据结构 */
  MyQueue() {

  }
  /** push方法，直接在inStack中推入 */
  void push(int x) {
    inStack.push(x);    // 将数据推入输入栈
  }
  /** 从队列前面删除该元素并返回该元素 */
  int pop() {
    check();    // 检查栈元素
    int a = outStack.top();   // 获取输出栈顶部元素
    outStack.pop();           // 推出元素
    return a;
  }
  /** 获取顶峰元素 */
  int peek() {
    check();    // 检查栈元素
    return outStack.top();    // 获取输出栈的顶部元素
  }
  /** 返回队列是否为空  */
  bool empty() {
    return inStack.empty() && outStack.empty();   // 输入输出均为空即可
  }
};

题目：用队列实现栈

使用队列实现栈的下列操作：

• push(x): 元素 x 入栈
• pop(): 移除栈顶元素
• top(): 获取栈顶元素
• empty(): 返回栈是否为空

注意:

• 你只能使用队列的基本操作：也就是 push to back,peek/pop from front,size,和 is empty 这些操作是合法的
• 你所使用的语言也许不支持队列。你可以使用 list 或者 deque（双端队列）来模拟一个队列,只要是标准的队列操作即可
• 你可以假设所有操作都是有效的（例如,对一个空的栈不会调用 pop 或者 top 操作）

个人理解：
这个和上面的栈实现队列有异曲同工之妙，但是稍有不同。两个队列实现栈，相当于两个正向，想要实现一个反向，正正肯定是不能得负的。
所以我们需要换一种想法，定义两个队列，输入一个数组，进入输入队列，然后将输入队列放到输出队列中，输入清空。
再来一个数字，将输出队列的数据放到输入中，实现反向，再重复步骤即可。

代码如下(C++):

class MyStack {
public:
  queue<int> inQueue;     // 输入队列
  queue<int> outQueue;    // 输出队列
  /** 初始化数据结构 */
  MyStack() {
  }
  /** 把值推入栈 */
  void push(int x) {
    inQueue.push(x);            // 将一个值推进输入队列
    while(!outQueue.empty()){   // 把输出队列中的给输入队列
      inQueue.push(outQueue.front());
      outQueue.pop();
    }
    queue<int> tmp = inQueue;   // 再把输入队列的还给输出队列
    inQueue = outQueue;
    outQueue = tmp;
    // while(!inQueue.empty()){   // 再把输入队列的还给输出队列
    //   outQueue.push(inQueue.front());
    //   inQueue.pop();
    // }
  }
  /** 移除栈顶元素 */
  int pop() {
    if(outQueue.empty()){   // 输出队列为空，return 0
      return 0;
    }
    int a = outQueue.front();   // 获取顶部
    outQueue.pop();             // 输出队列推出
    return a;
  }
  /** 获取栈顶元素 */
  int top() {
    if(outQueue.empty()){   //输出队列为空，return 0
      return 0;
    }
    return outQueue.front();    // 获取输出队列顶部
  }
  /** 查看队列是否为空 */
  bool empty() {
    return outQueue.empty();    // 判断输入队列是否为空
  }
};

题目：字符串解码

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

示例：

输入：s = "3[a]2[bc]"
输出："aaabcbc"
输入：s = "3[a2[c]]"
输出："accaccacc"
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

个人理解：
这个之前我们见过类似的，括号匹配，肯定是用栈来实现问题，其实就是遇到数字，压到数字栈里面，然后遇到字母压到字母栈里面，遇到符号]就把之前压进去的都取出来，然后数字对字母加倍。

代码如下(C++):

class Solution {
public:
  string decodeString(string s) {
    string res = "";
    stack <int> nums;
    stack <string> strs;
    int num = 0;
    int len = s.size();
    for(int i = 0; i < len; i++){
      if(s[i] >= '0' && s[i] <= '9'){
        num = num * 10 + s[i] - '0';
      }else if((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z')){
        res = res + s[i];
      }else if(s[i] == '['){      // 将'['之前的数字压入nums栈，字母压入strs栈
        nums.push(num);
        num = 0;
        strs.push(res);
        res = "";
      }else{
        int times = nums.top();
        nums.pop();
        for(int j = 0;j < times; j++)
          strs.top() += res;
          res = strs.top();   // 之后若还是字母，就直接加到res后，因为它们是同一级的运算，若是左括号，res会被压入strs栈，作为上一层的运算。
          strs.pop();
      }
    }
    return res;
  }
};

题目：图像渲染

有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。
给你一个坐标(sr,sc)表示图像渲染开始的像素值（行，列）和一个新的颜色值 newColor，让你重新上色这幅图像。
为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。
最后返回经过上色渲染后的图像。

示例：

输入:
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
输出: [[2,2,2],[2,2,0],[2,0,1]]
解析:
在图像的正中间，(坐标(sr,sc)=(1,1)),
在路径上所有符合条件的像素点的颜色都被更改成2。
注意: 右下角的像素没有更改为2，
因为它不是在上下左右四个方向上与初始点相连的像素点。

注意:

• image 和 image[0]的长度在范围[1,50]内。
• 给出的初始点将满足 0 <= sr < image.length 和 0 <= sc < image[0].length。
• image[i][j] 和 newColor 表示的颜色值在范围 [0, 65535]内。

个人理解：
从像素位置开始上色，渲染周边和目标像素初始颜色相同的像素。
算法：将 color 置为目标像素初始颜色。从目标像素位置开始上色：如果像素颜色和 color 相同则改变像素颜色为 newColor，然后再从四个方向进行上色，重复上述过程。使用 dfs 函数对目标像素进行渲染。

代码如下(C++):

class Solution {
public:
  vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
    vector<vector<int>> new_image(image);
    int oldColor = image[sr][sc];       // 例子：oldColor = 1
    if(oldColor != newColor){           // 新的颜色不同于旧颜色才更新
      DFS(new_image,sr,sc,oldColor,newColor);   // 深度优先搜索
    }
    return new_image;
  }
private:
  void DFS(vector<vector<int>> &new_image, int r,int c,int old_color,int new_color){
    int row_num = new_image.size(), col_num = new_image[0].size();
    //越界，或者颜色不相等返回，例子：old_color = 1，只更新位置color = 1的地方
    if(r < 0 || r >= row_num || c < 0 || c >= col_num || new_image[r][c] != old_color){
      return;
    }
    new_image[r][c] = new_color;
    DFS(new_image,r-1,c,old_color,new_color);
    DFS(new_image,r+1,c,old_color,new_color);
    DFS(new_image,r,c-1,old_color,new_color);
    DFS(new_image,r,c+1,old_color,new_color);
  }
};

看到一个解法，作者：OrangeMan，简洁易懂，优秀。

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        int oldColor = image[sr][sc];   //记录旧坐标的像素
        if (image[sr][sc] == newColor) return image; //颜色相同则无需修改
        image[sr][sc] = newColor;   //染色
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; //上右下左
        for (int i = 0; i < 4; i ++) {
            int x = sr + dx[i], y = sc + dy[i];
            if (x >=0 && y >= 0 && x < image.size() && y < image[0].size() && image[x][y] == oldColor)
                floodFill (image, x, y, newColor);
        }
        return image;
    }
};

题目：01 矩阵

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

示例：

输入:
0 0 0
0 1 0
0 0 0
输出:
0 0 0
0 1 0
0 0 0
输入:
0 0 0
0 1 0
1 1 1
输出:
0 0 0
0 1 0
1 2 1

注意:

• 给定矩阵的元素个数不超过 10000
• 给定矩阵中至少有一个元素是 0
• 矩阵中的元素只在四个方向上相邻:上、下、左、右。

个人理解：
应该挺好理解的，要得到的是最近距离，所有元素，那就广度优先搜索呗。
弄一个队列出来，然后只有一个 0 的时候，把 0 的位置加入队列，然后搜索所有。如果有多个 0，那就把所有的 0 都加入队列，然后在搜索。

注意：因为有多个 0，所以需要将距离实时更新为最短。

代码如下(C++):

class Solution {
public:
  vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
    int numr = matrix.size();    // 获取矩阵大小
    if(numr == 0) return matrix;
    int numc = matrix[0].size();
    if(numc == 0) return matrix;
    // 初始化一个结果数组内容为INT_MAX
    vector<vector<int>> res(numr, vector<int>(numc, INT_MAX));
    queue<pair<int,int>> q;    // 定义队列

    vector<int> dx = {-1,1,0,0};
    vector<int> dy = {0,0,-1,1};

    for(int i = 0; i < numr; ++i){
      for(int j = 0; j < numc; ++j){
        if(matrix[i][j] == 0){        // 如果是 0 结果里面直接就为 0
          res[i][j] = 0;
          q.push(make_pair(i, j));  // 并且将 0 推入队列中
        }
      }
    }
    while(!q.empty()){    // BFS
      int x = q.front().first;    // 获取 x,y 坐标
      int y = q.front().second;
      q.pop();            // 推出
      for(int j = 0;j<4;++j){     // 遍历
        int nx = x + dx[j];
        int ny = y + dy[j];
        if(nx >= 0 && nx<numr && ny >= 0 && ny < numc && res[nx][ny]>res[x][y]+1){
          res[nx][ny] = res[x][y] + 1;      // 默认值为INT_MAX，对比，选择最短路径
          q.push(make_pair(nx, ny));        // 然后推入附近的坐标
        }
      }
    }
    return res;   // 返回结果
  }
};

题目：钥匙和房间

有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，…，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。
在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j]由[0,1，…，N-1]中的一个整数表示，其中 N=rooms.length。钥匙 rooms[i][j]=v 可以打开编号为 v 的房间。

最初，除 0 号房间外的其余所有房间都被锁住。
你可以自由地在房间之间来回走动。
如果能进入每个房间返回 true，否则返回 false

示例：

输入: [[1],[2],[3],[]]
输出: true
解释:
我们从 0 号房间开始，拿到钥匙 1
之后我们去 1 号房间，拿到钥匙 2
然后我们去 2 号房间，拿到钥匙 3
最后我们去了 3 号房间。
由于我们能够进入每个房间，我们返回 true。

输入：[[1,3],[3,0,1],[2],[0]]
输出：false
解释：我们不能进入2号房间。

提示：

• 1<=rooms.length<=1000
• 0<=rooms[i].length<=1000
• 所有房间中的钥匙数量总计不超过 3000

个人理解：
当进入一个房间时，根据钥匙，进入更深的房间，并且标记房间，如果没路了，回来继续进入其他钥匙指向的房间，直到结束。

代码如下(C++):

class Solution {
public:
  bool canVisitAllRooms(vector<vector<int>>& rooms) {
    int roomCount = rooms.size();   // 获取房间数量
    vector<bool> visited(roomCount, false);   // 定义可访问房间
    visited[0] = 1;     // 从第0房间开始
    stack <int> keys;   // 钥匙栈
    keys.push(0);
    while(!keys.empty())    // DFS
    {
      int key = keys.top();
      keys.pop();
      int rs = rooms[key].size();
      for(int i = 0; i < rs; ++i)     // 把房间里的钥匙遍历
      {
        if(!visited[rooms[key][i]])   // 如果这个钥匙去的地方我们可以进入，就不添加钥匙
        {
          visited[rooms[key][i]] = true;    // 否则添加
          keys.push(rooms[key][i]);         // 然后把钥匙推入栈，继续走
        }
      }
    }
    for(int i = 1; i < roomCount; i++){     // 遍历所有添加进去的可访问房间
      if(!visited[i]) return false;         // 任何一个错误，就返回false
    }
    return true;
  }
};

声明：本文为学习记录，参考之处较多，如果有侵权内容，请联系我立即删除。