🚑栈和队列🚑

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

寻找两个正序数组的中位数

leetcode 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

解题思路

两个堆，左边大顶堆，右边小顶堆，大顶堆里数全部比右边小顶堆得数小
插入时根据两个堆高度分三种情况
返回时根据两个堆高度也分三种情况

	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        /// 合并
        vector<int> nums;
        for (auto num : nums1) nums.push_back(num);
        for (auto num : nums2) nums.push_back(num);

        /// 左边大顶堆，右边小顶堆
        priority_queue<int, vector<int>, less<int>> bigHeap;
        priority_queue<int, vector<int>, greater<int>> smallHeap;

        for (auto num : nums) {

            if (bigHeap.empty()) {
                bigHeap.push(num);
                continue;
            }

            if (smallHeap.empty()) {
                int tmp = bigHeap.top();
                bigHeap.pop();
                bigHeap.push(min(tmp, num));
                smallHeap.push(max(tmp, num));
                continue;
            }

            /// 两个堆一样高时
            if (bigHeap.size() == smallHeap.size()) {
                if (num >= bigHeap.top()) {
                    smallHeap.push(num);
                } else {
                    smallHeap.push(bigHeap.top());
                    bigHeap.pop();
                    bigHeap.push(num);
                }
            } /// 大顶堆高 
            else if (bigHeap.size() > smallHeap.size()) {
                    if (num >= bigHeap.top()) {
                    smallHeap.push(num);
                } else {
                    smallHeap.push(bigHeap.top());
                    bigHeap.pop();
                    bigHeap.push(num);
                }

            } /// 小顶堆高
            else if (bigHeap.size() < smallHeap.size()) {
                if (num <= smallHeap.top()) {
                    bigHeap.push(num);
                } else {
                    bigHeap.push(smallHeap.top());
                    smallHeap.pop();
                    smallHeap.push(num);
                }
            }
        }


        if (smallHeap.size() == bigHeap.size()) {
            return (smallHeap.top() + bigHeap.top()) / (double)2;
        } else if (smallHeap.size() > bigHeap.size()) {
            return smallHeap.top();
        } else {
            return bigHeap.top();
        }
    }

整数反转

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 。

示例

解题思路

理解题意比较难，题意要求我们找到每个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;
    }
};

刘文韬 / leetcode-note

🚑栈和队列🚑

寻找两个正序数组的中位数

解题思路

整数反转

解题思路

回文数

解题思路

有效的括号

解题思路

用栈实现队列

用队列实现栈

方法一

方法二

最小栈

逆波兰表达式求值

示例

解题思路

字符串解码

示例

解题思路

克隆图

示例

解题思路

岛屿数量

示例

DFS解题思路

BFS解题

柱状图中最大的矩形

示例

解题思路

01矩阵

示例

解题思路

设计循环队列

解题思路

简介

发行版

贡献者

近期动态

刘文韬 / leetcode-note .gitee-modal { width: 500px !important; }

🚑栈和队列🚑

寻找两个正序数组的中位数

解题思路

整数反转

解题思路

回文数

解题思路

有效的括号

解题思路

用栈实现队列

用队列实现栈

方法一

方法二

最小栈

逆波兰表达式求值

示例

解题思路

字符串解码

示例

解题思路

克隆图

示例

解题思路

岛屿数量

示例

DFS解题思路

BFS解题

柱状图中最大的矩形

示例

解题思路

01矩阵

示例

解题思路

设计循环队列

解题思路

简介

发行版

贡献者

近期动态

搜索帮助

刘文韬 / leetcode-note