算法专题十: 栈+BFS

用户11317877

发布于 2024-10-31 08:24:34

720

发布于 2024-10-31 08:24:34

文章被收录于专栏：学习

一. 前言

很高兴迎来了一年一度的“程序员节”。这个节日的由来与数字“1024”息息相关，因为1024是2的10次方，正好与计算机科学中的二进制系统紧密相连。本篇文章我会把自己刷到的经典题目和解决题目的思路分享给大家.

感谢大家的支持!!! 博客主页: 酷酷学!!!

二. 栈

1. 基本计算器Ⅱ

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。

注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。



示例 1：

输入：s = "3+2*2"
输出：7
示例 2：

输入：s = " 3/2 "
输出：1
示例 3：

输入：s = " 3+5 / 2 "
输出：5


提示：

1 <= s.length <= 3 * 105
s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
s 表示一个 有效表达式
表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
题目数据保证答案是一个 32-bit 整数

算法思路:

首先仔细读题目, 可以知道题目所给的表达式中全部都是非负整数, 并且表达式是有效的, 核心思想就是利用栈依次提取数字和字符进行运算

第一步: 创建栈,另外创建一个字符, 这里可以直接使用数组模拟, 因为不存在头插和头删, 默认第一个数字的字符为+/

第二步: 把遍历字符串, 如果有空格直接跳过, 如果数字, 先将数字提取出来, 然后根据字符进行不同的操作, 如果是+, - 则直接入栈, 如果是*, / 则运算到栈顶元素上, 如果为字符则更新字符

第三步: 将数字一一提取出来, 然后直接运算即可.

编写代码:

class Solution {
public:
    int calculate(string s) {
        vector<int> v;
        int n = s.size(), i = 0;
        char op = '+';
        while(i < n)
        {
            if(s[i] == ' ') i++;
            else if(s[i] >= '0' && s[i] <= '9')
            {
                int tmp = 0;
                while(i < n && s[i] >= '0' && s[i] <= '9')
                    tmp = tmp * 10 + (s[i++] - '0');
                if(op == '+')  v.push_back(tmp);
                if(op == '-')  v.push_back(-tmp);
                if(op == '*')  v.back() *= tmp;
                if(op == '/')  v.back() /= tmp;
            }
            else op = s[i++];
        }
        int ret = 0;
        for(auto x : v)
            ret += x;
        return ret;
    }
};

2. 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

 

示例 1：

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

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

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
示例 4：

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"
 

提示：

1 <= s.length <= 30
s 由小写英文字母、数字和方括号 '[]' 组成
s 保证是一个 有效 的输入。
s 中所有整数的取值范围为 [1, 300]

算法思路:

本道题有很多细节需要注意

第一步: 当拿到一个数字时, 后面[]中内容对于我们来说是一个黑盒, 所以说我们就需要对后面的内容进行分类的讨论, 核心思想就是利用栈提取出字符串和数字, 然后根据要求进行处理

第二步: 分类讨论, 如果遇到数字, 则提取出数字, 放入到数字栈中, 如果遇到[, 则提取出后面的字符串, 然后放入到字符串栈中, 如果遇到], 则说明开始运算了, 这里注意我们运算时相对于前一个[还是黑盒, 所以我们要运算到前一个字符串的后面, 如果直接遇到字符串, 则提取之后运算到栈顶元素即可

第三步: 返回我们的栈顶元素

编写代码:

class Solution {
public:
    string decodeString(string s) {
        stack<int> digit;
        stack<string> st;
        st.push("");
        int i = 0, n = s.size();
        while(i < n)
        {
            //如果遇到数字, 处理数字
            if(s[i] >= '0' && s[i] <= '9')
            {
                int tmp = 0;
                while(i < n && s[i] >= '0' && s[i] <= '9')
                    tmp = tmp * 10 + (s[i++] - '0');
                digit.push(tmp);
            }
            //如果遇到左括号,处理后面的字符串
            else if(s[i] == '[')
            {
                i++;//先++之后处理
                string tmp;
                while(i < n && s[i] >= 'a' && s[i] <= 'z')
                    tmp += s[i++];
                st.push(tmp);
            }
            //如果遇到右括号取两个栈顶元素结果加到前一个字符串上
            else if(s[i] == ']')
            {
                i++;
                int num = digit.top();
                digit.pop();
                string tmp = st.top();
                st.pop();
                while(num--)
                    st.top() += tmp;
            }
            //直接遇到字符串
            else
            {
                string tmp;
                while(i < n && s[i] >= 'a' && s[i] <= 'z')
                    tmp += s[i++];
                st.top() += tmp;
            }
        }
        return st.top();
    }
};

三. BFS

1. N叉树的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

 

示例 1：



输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]
示例 2：



输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
 

提示：

树的高度不会超过 1000
树的节点总数在 [0, 104] 之间

算法思路: 这个其实就是非常经典的BFS, 可以根据队列来进行层序遍历, 先让根节点进入队列, 然后执行出队列操作, 出队列的次数就是当前队列中元素的个数, 出队列操作首先将当前节点的保存下来, 然后pop, 并且记录val, 将他的孩子节点入队列.

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
//1.头节点进队列, 队列不为空循环
//2.提取第一个队列元素, pop掉, 孩子入队列
//3.每次计算一下队列的节点个数, 进行几次的pop操作

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        queue<Node*> q;
        vector<vector<int>> ret;
        if(root == nullptr) return ret; 
        q.push(root);
        while(q.size())
        {
            vector<int> tmp;
            int sz = q.size();
            for(int i = 0; i < sz; i++)
            {
                Node* front = q.front();
                q.pop();
                tmp.push_back(front->val);
                for(auto& ch : front->children)
                    q.push(ch);
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};

2. 在每行中找出最大值

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

 

示例1：



输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
示例2：

输入: root = [1,2,3]
输出: [1,3]
 

提示：

二叉树的节点个数的范围是 [0,104]
-231 <= Node.val <= 231 - 1

算法思路

依旧是利用层序遍历，但是这⼀次队列里面不单单存结点信息，并且还存储当前结如果在数组中存储所对应的下标（在我们学习数据结构 - 堆的时候，计算左右孩⼦的⽅式）。这样我们计算每⼀层宽度的时候，无需考虑空节点，只需将当层结点的左右结点的标相减再加 1 即可。但是，这里有个细节问题：如果⼆叉树的层数非常恐怖的话，我们任何⼀种数据类型都不能存下下标的值。但是没有问题，因为

• 我们数据的存储是⼀个环形的结构； • 并且题目说明，数据的范围在 int 这个类型的最大值的范围之内，因此不会超出⼀圈； • 因此，如果是求差值的话，我们无需考虑溢出的情况。

编写代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> ret;
        if(root == nullptr) return ret;
        list<TreeNode*> lt;
        lt.push_back(root);
        while(lt.size())
        {
            int k = INT_MIN;
            int sz = lt.size();
            for(int i = 0; i < sz; i++)
            {
                TreeNode* front = lt.front();
                lt.pop_front();
                k = max(k,front->val);
                if(front->left) lt.push_back(front->left);
                if(front->right) lt.push_back(front->right);
            }
            ret.push_back(k);
        }
        return ret;
    }
};

完