leetcode题解(栈和队列问题)

栈和队列虽然是简单的数据结构，但是使用这些简单的数据结构所解决的算法问题不一定简单,主要介绍和栈与队列相关的leetcode算法问题。

栈的基础应用

leetcode 20. 有效的括号

解题思路

• 采用栈这个数据结构存储“左符号”
• 栈顶元素反映了在嵌套的层次关系中，最近的需要匹配的元素

代码实现

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        
        for (int i = 0; i < s.size(); i++){
            //只有左符号才入栈
            if (s[i] == '(' || s[i] == '{'|| s[i] == '['){
                st.push(s[i]);
            }else{
                if (st.size() == 0){
                    return false;
                }
                
                char top = st.top();
                st.pop();
                
                char match;
                if (s[i] == ')'){
                    match = '(';
                }else if(s[i] == '}'){
                    match = '{';
                }else{
                    assert(s[i] == ']');
                    match = '[';
                }
                
                if (top != match){
                    return false;
                }
                
            }  
        }
        
        if (st.size() != 0){
            return false;
        }
        return true;
    }
};

复制代码

相似问题

leetcode 150. 逆波兰表达式求值

leetcode 71. 简化路径

栈和递归的紧密关系

我们先看一下二叉树的先序遍历

function preorder(node){
  if(node){
    cout << node -> val;
    preorder(node.left);
    preorder(node.right);
  }
}
       
复制代码

分析

我们来看一下具体的遍历，假设我们只有三个节点，父节点是1，左节点是2，右节点是3。我们首先使用根节点调用函数preorder，然后使用节点2调用了函数preorder，再使用节点3调用了函数preorder。这三次preorder的传入参数是不同的，那么这三个函数的调用顺序是怎么样的？我们可以抽象为根节点调用时，执行到节点2调用的时候停住了，接着执行一个子函数也就是节点2的调用，直到节点2调用结束之后，再进行节点3子函数的调用。那么操作系统就是通过栈来实现这样一个操作。根节点调用的函数先被压入栈中开始执行，这时遇到了函数栈节点2。在节点2的函数被压入栈之后立即执行，等到执行完之后返回值(或不返回)，然后节点2的函数被弹出。节点2的函数被弹出之后，节点1的函数继续执行，节点3的函数被压入并立即执行。

leetcode144. 二叉树的前序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> vec;
        preHelp(root, vec);
        return vec;
    }
    
private:
    void preHelp(TreeNode* root, vector<int> &vec){
        
        if(root){
            vec.push_back(root->val);
            preHelp(root->left, vec);
            preHelp(root->right, vec);
        }
    }
};
复制代码

相似问题

leetcode 94. 二叉树的中序遍历

leetcode 145. 二叉树的后序遍历

运用栈模拟递归

现在使用栈模拟系统栈，写出非递归程序：我们先推入右孩子，在再推入左孩子，最后推入打印，这样由于栈的后进先出就完成了先序遍历。

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


class Solution {

private:
    struct Command{
        string s;   // go, print
        TreeNode* node;
        Command(string s, TreeNode* node): s(s), node(node){}
    };

public:
    vector<int> preorderTraversal(TreeNode* root) {

        vector<int> res;
        if(root == NULL)
            return res;

        stack<Command> stack;
        stack.push(Command("go", root));
        while(!stack.empty()){
            Command command = stack.top();
            stack.pop();

            if(command.s == "print")
                res.push_back(command.node->val);
            else{
                assert(command.s == "go"); 
                //stack.push(Command("print", command.node));//后序遍历
                if(command.node->right)
                    stack.push(Command("go",command.node->right));
                //stack.push(Command("print", command.node));//中序遍历
                if(command.node->left)
                    stack.push(Command("go",command.node->left));
                stack.push(Command("print", command.node));//先序遍历
            }
        }
        return res;
    }
};

int main() {

    return 0;
}

复制代码

相似问题

leetcode 341

队列的典型应用

leetcode 102. 二叉树的层次遍历

其实对于队列Queue来说，它主要处理的算法问题就是广度优先遍历(树：层序遍历，图：无权图的最短路径) 这其实就是二叉树的层序遍历，但却是很多公司的面试题，在平时还是要多注重典型基础数据结构的应用。

代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (root == NULL){
            return res;
        }
        
        queue<pair<TreeNode*, int>> q;//存储节点和层级
        
        q.push(make_pair(root, 0));
        
        while(!q.empty()){
            TreeNode* node = q.front().first;
            int level = q.front().second;
            
            q.pop();
            
            
            if (res.size() == level){
                res.push_back(vector<int>());
            }
            
            res[level].push_back(node->val);
            
            if (node->left){
                q.push(make_pair(node->left, level+1));
            }
            
            if (node -> right){
                q.push(make_pair(node->right, level+1));
            }
        }
        
        return res;
    }
};
    

复制代码

相似问题

leetcode 107

leetcode 103

leetcode 199

图的广度优先遍历(BFS)和图的最短路径

当我们对图进行广度优先遍历的时候可以解决最短路径的问题。但其实很多算法问题，我们使用图的最短路径这一思路来解决，但是这个问题第一眼看上去却不像一个图论问题，在问题的描述中没有非常明确的告诉我们需要使用图来解决问题，在这种情况下我们需要对问题深入分析并建模。

leetcode279. 完全平方数

解决思路

直觉解法？贪心？

12 = 9 + 1 + 1 + 1  
    12 = 4 + 4 + 4 
    
复制代码

关于贪心算法我们后续还会有介绍，贪心算法实现起来比较简单，但我们很容易陷入一个误区，一个问题不能用贪心算法来解决我们却以为可以使用贪心算法来解决。

广度遍历建模

对于这个问题建模： 整个问题转化为一个图论问题,从n到0，每个数字表示一个节点,如果有两个数字x到y相差一个完全平方数，则连接一条边，我们得到了一个无权图，原问题转化成，求这个无权图中从n到0的最短路径

class Solution {
public:
    int numSquares(int n) {
        queue<pair<int, int>> q;
        q.push(make_pair(n, 0));//从n出发，到达n需要0步
        
        while(!q.empty()){
            int num = q.front().first;
            int step = q.front().second;
            
            q.pop();
            
            if (num == 0){
                return step;
            }else{
                for(int i = 1; num - i *i >= 0; i++){
                    q.push(make_pair(num - i *i, step + 1));
                }
            }
        }
        throw invalid_argument("no answer!");
    }
};

复制代码

分析

这样实现的程序并不是一个标准的广度优先实现，它是有性能问题的，问题来自我们每一次都将num-i*i推入了队列中，其中包含有大量的重复，因为每一个数字我们可以从多种路径到达。

• 为了处理冗余，我们设立一个新数组visited表示从0到n这n+1个数字有没有被访问过。

class Solution {
public:
    int numSquares(int n) {
        queue<pair<int, int>> q;
        q.push(make_pair(n, 0));//从n出发，到达n需要0步
        
        vector<bool> visited(n + 1, false);
        visited[n] = true;
        
        while(!q.empty()){
            int num = q.front().first;
            int step = q.front().second;
            
            q.pop();
            
            if (num == 0){
                return step;
            }else{
                for(int i = 1; ; i++){
                    int tmp = num - i *i;
                    
                    if (tmp < 0){
                        break;
                    }
                    
                    if (!visited[tmp]){
                        q.push(make_pair(tmp, step + 1));
                        visited[tmp] = true;
                    }
                    
                }
            }
        }
        throw invalid_argument("no answer!");
    }
};
复制代码

相似问题

leetcode 127

leetcode 126

优先队列(c++)

优先队列是一种特殊的队列，通常优先队列的底层实现是堆。对于堆得底层实现需要我们可以使用白板编程。

c++库 priority_queue

#include <iostream>
#include <queue>
#include <ctime>

using namespace std;

bool myCmp(int a , int b){

    if(a%10 != b%10)
        return a%10 > b%10;
    return a > b;
}

int main() {

    srand(time(NULL));

    // 默认的priority queue, 底层是最大堆
    priority_queue<int> pq;

    for(int i = 0 ; i < 10 ; i ++){
        int num = rand() % 100;
        pq.push(num);
        cout << "insert " << num << " in priority queue." << endl;
    }

    while(!pq.empty()){
        cout << pq.top() << " ";
        pq.pop();
    }

    cout << endl << endl;

    // 使用greater的priority queue, 底层是最小堆
    priority_queue<int, vector<int>, greater<int>> pq2;

    for(int i = 0; i < 10; i ++){
        int num = rand() % 100;
        pq2.push(num);
        cout << "insert " << num << " in priority queue." << endl;
    }

    while(!pq2.empty()){
        cout << pq2.top() << " ";
        pq2.pop();
    }

    cout << endl << endl;

    // 使用自定义Comparator的priority queue
    priority_queue<int, vector<int>, function<bool(int,int)>> pq3(myCmp);

    for(int i = 0; i < 10; i ++){
        int num = rand() % 100;
        pq3.push(num);
        cout << "insert " << num << " in priority queue." << endl;
    }

    while(!pq3.empty()){
        cout << pq3.top() << " ";
        pq3.pop();
    }

    return 0;
}

复制代码

优先队列相关的算法问题

leetcode 347. 前K个高频元素

最简单的思路：扫描一遍统计频率：排序找到前k个出现频率最高的元素，O(nlogn)。

经过思考，其实我们可以维护一个含有k个元素的优先队列。如果遍历到的元素比队列中的最小频率元素的频率高，则取出队列中最小频率的元素，将新元素入队。最终，队列中剩下的，就是前k个出现频率最高的元素。

代码实现

#include <iostream>
    #include <vector>
    #include <queue>
    #include <unordered_map>
    #include <cassert>
    
    using namespace std;
    
    class Solution {
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
    
            assert( k > 0 );
    
            // 统计每个元素出现的频率
            unordered_map<int,int> freq;
            for(int i = 0 ; i < nums.size() ; i ++ )
                freq[nums[i]] ++;
    
            assert( k <= freq.size() );
    
            // 扫描freq,维护当前出现频率最高的k个元素
            // 在优先队列中,按照频率排序,所以数据对是 (频率,元素) 的形式
            priority_queue< pair<int,int> , vector<pair<int,int>> , greater<pair<int,int>> > pq;
            for( unordered_map<int,int>::iterator iter = freq.begin() ;
                 iter != freq.end() ; iter ++ ){
                if( pq.size() == k ){
                    if( iter->second > pq.top().first ){
                        pq.pop();
                        pq.push( make_pair( iter->second , iter->first) );
                    }
                }
                else
                    pq.push( make_pair( iter->second , iter->first ) );
            }
    
            vector<int> res;
            while( !pq.empty() ){
                res.push_back( pq.top().second );
                pq.pop();
            }
    
            return res;
        }
    };


复制代码

分析

• 上面代码的时间复杂度为O(N*longK)
• 但是如果k接近N，则时间复杂度蜕化为O(N*N)
• 可以修改上述代码，当k接近N，时间复杂度为O(nlog(n-k))