当前位置: 首页 > article >正文

【栈数据结构应用解析:常见算法题详细解答】—— Leetcode

文章目录

  • 栈的模拟实现
  • 删除字符串中的所有相邻重复项
  • 比较含退格的字符串
  • 基本计算器||
  • 字符串解码
  • 验证栈序列

栈的模拟实现

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

// 创建栈
int stk[N], n;

// 进栈 - 本质就是顺序表里面的尾插
void push(int x)
{
    stk[++n] = x;
}

// 出栈 - 顺序表的尾删操作
void pop()
{
    n--;
}

// 查询栈顶元素
int top()
{
    return stk[n];
}

// 判断是否为空
bool empty()
{
    return n == 0;
}

// 查询有效元素的个数
int size()
{
    return n;
}

int main()
{
    for(int i = 1; i <= 10; i++)
    {
        push(i);
    }

    // 当栈不为空的时候
    while(size()) // while(!empty()) 
    {
        cout << top() << endl;
        pop();
    }


    return 0;
}

删除字符串中的所有相邻重复项

在这里插入图片描述

  • 思路:我们通过模拟栈遍历字符串 s,逐个字符处理。当遇到当前字符和 ret(结果字符串)末尾的字符相同时,说明这两个字符相同且相邻,因此可以将末尾的字符移除(使用 pop_back()),实现删除重复字符的效果。否则,将当前字符添加到 ret 的末尾。最终返回 ret 作为结果。这个方法有效地将相邻的重复字符一一删除,直到整个字符串处理完成。
class Solution 
{
public:
    string removeDuplicates(string s) 
    {
        // 创建一个空的字符串 ret 用于存储结果
        string ret;

        // 遍历输入字符串 s 中的每一个字符
        for(char ch : s)
        {
            // 如果 ret 非空,并且 ret 的最后一个字符等于当前字符
            if(ret.size() && ret.back() == ch) 
                // 移除 ret 末尾的字符(即删除相邻的重复字符)
                ret.pop_back();
            else 
                // 否则,将当前字符添加到 ret 末尾
                ret += ch;
        }

        // 返回最终去重后的字符串
        return ret;
    }
};

比较含退格的字符串

在这里插入图片描述

  • 思路:本题要求我们比较两个字符串 s 和 t 在应用退格符 # 后是否相同。退格符 # 表示删除字符串中前一个有效字符。如果遇到 #,我们就模拟删除操作,即当字符串非空时,删除最后一个有效字符。最终通过比较处理后的两个字符串来判断它们是否相等。此方法是通过两个字符串 s1 和 s2 来分别存储 s 和 t 经过退格操作后的结果,最后直接比较这两个字符串。
class Solution 
{
public:
    bool backspaceCompare(string s, string t) 
    {
        // 创建两个空字符串 s1 和 s2 用于存储去除退格符后的结果
        string s1, s2;

        // 遍历字符串 s 处理退格符
        for(char ch : s)
        {
            if(ch == '#') // 如果遇到退格符
            {
                if(s1.size()) // 如果 s1 非空
                {
                    s1.pop_back(); // 删除 s1 最后一个字符
                }
            } 
            else s1 += ch; // 否则,将当前字符添加到 s1
        } 

        // 遍历字符串 t 处理退格符
        for(char ch : t)
        {
            if(ch == '#') // 如果遇到退格符
            {
                if(s2.size()) // 如果 s2 非空
                {
                    s2.pop_back(); // 删除 s2 最后一个字符
                }
            } 
            else s2 += ch; // 否则,将当前字符添加到 s2
        } 

        // 比较两个处理后的字符串是否相同
        if(s2 == s1) return true;
        else return false;
    }
};

基本计算器||

在这里插入图片描述

  • 思路:这道题目要求我们计算一个字符串表示的算式,支持加、减、乘、除四种基本运算,并且按照优先级顺序处理。为了正确计算,我们需要用栈来处理运算符的优先级。基本的思路如下:
  1. 遍历字符串:我们遍历字符串的每一个字符,遇到空格时跳过,遇到数字时读取完整的数字,遇到运算符时处理当前运算,并记录当前运算符。
  2. 使用栈存储中间结果:对于加法和减法,我们将结果加入栈中;对于乘法和除法,我们需要在栈顶进行计算(因为乘法和除法的优先级更高)。
  3. 最终计算:计算完所有数字和运算符后,栈中的值就是我们需要的结果,将栈中的值加和得到最终答案。
class Solution 
{
public:
    int calculate(string s) 
    {
        // 使用栈来存储计算中的结果
        vector<int> st;
        int i = 0, n = s.size();
        // 初始操作符为 '+', 表示第一个数字为正数
        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 == '+') 
                    st.push_back(tmp); // 加法:将数字压入栈
                else if(op == '-') 
                    st.push_back(-tmp); // 减法:将数字的相反数压入栈
                else if(op == '*') 
                    st.back() *= tmp; // 乘法:栈顶元素与当前数字相乘
                else 
                    st.back() /= tmp; // 除法:栈顶元素与当前数字相除
            }
            else 
            {
                // 如果是运算符,更新当前操作符
                op = s[i];
                i++;
            }
        }
        
        // 计算栈中所有数字的和
        int ret = 0;
        for(auto ch : st) 
            ret += ch;

        return ret;
    }
};

字符串解码

在这里插入图片描述

  • 思路:这道题目要求解码一个类似 “3[a2[c]]” 的字符串。通过递归或栈的方式,可以逐步处理字符串中的数字、字母和括号。基本思路如下:

栈的使用:我们使用两个栈来辅助解码:

  • st 栈用于存储解码过程中的中间字符串。
    nums 栈用于存储数字(即每次遇到数字时,记录数字,表示该数字代表后续括号中的字符串重复次数)。
    数字处理:当我们遇到数字时,我们会计算出当前数字(可能是多位数),并将其压入 nums 栈。
    左括号 [ 处理:当我们遇到左括号时,表示一个新的子字符串的开始,此时将当前已处理的字符串压入 st 栈,开始处理新的一段字符串。
    右括号 ] 处理:当我们遇到右括号时,表示当前子字符串的结束。此时,弹出 st 栈顶的字符串和 nums 栈顶的数字。数字 k 代表当前子字符串应该重复的次数。我们将字符串重复 k 次后,合并到栈顶的字符串。
    字母处理:当我们遇到字母时,将其直接添加到栈顶的字符串中。

最后,栈中存储的是解码后的字符串,返回栈顶的字符串即为最终结果。

class Solution 
{
public:
    string decodeString(string s) 
    {
        // 栈 st 用于存储解码过程中的中间字符串,栈 nums 用于存储数字
        stack<string> st;
        stack<int> nums;
        
        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');
                }
                nums.push(tmp); // 将数字压入 nums 栈
            }
            // 处理左括号 '[',表示进入一个新的子字符串
            else if(s[i] == '[')
            {
                i++;
                string tmp = "";
                // 读取子字符串中的字母
                while(s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i];
                    i++;
                }
                st.push(tmp); // 将字母子串压入栈中
            }
            // 处理右括号 ']',表示子字符串结束,进行重复操作
            else if(s[i] == ']')
            {
                string tmp = st.top();
                st.pop();  // 弹出栈顶字符串(当前子字符串)
                int k = nums.top();
                nums.pop();  // 弹出栈顶数字(重复次数)

                // 重复当前子字符串 k 次,并合并到栈顶字符串中
                while(k--)
                {
                    st.top() += tmp;
                }
                i++; // 处理下一个字符
            }
            // 处理字母,直接添加到栈顶字符串
            else
            {
                string tmp;
                while(i < n && s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i];
                    i++;
                }
                st.top() += tmp; // 将字母添加到栈顶字符串中
            }
        }
        
        return st.top();  // 最终返回栈顶的解码结果
    }
};

验证栈序列

在这里插入图片描述

  • 思路:
  • 模拟栈的操作:
    我们遍历 pushed 序列,将每个元素压入栈中。
    每次压栈后,检查栈顶元素是否与 popped[j] 相等。如果相等,说明栈顶元素可以被弹出,接着弹出栈顶元素,并将 j 增加。
    一直进行上述操作,直到遍历完整个 pushed 序列。
  • 最终判断:
    如果遍历完 pushed 序列后,栈为空,且 j 达到了 popped 序列的末尾,说明 popped 是可能的弹出序列。
    如果栈不为空,或者 j 没有达到 popped 的末尾,则说明不可能通过栈操作生成 popped。
class Solution 
{
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) 
    {
        int i = 0, j = 0, n = popped.size();  // i 是 pushed 的索引,j 是 popped 的索引
        stack<int> st;  // 栈,用于模拟压栈和弹栈操作
        
        // 遍历 pushed 序列
        while(i < n)
        {
            st.push(pushed[i++]);  // 将当前元素压入栈中
            
            // 检查栈顶元素是否等于 popped[j]
            while(st.size() && st.top() == popped[j])
            {
                st.pop();  // 如果栈顶元素等于 popped[j],则弹出栈顶
                j++;  // 更新 popped 序列的索引
            }
        }
        
        // 如果栈为空,且所有元素都能匹配成功,则返回 true
        return st.empty();
    }
};

栈算法的核心思路:

  • 栈的模拟:栈是后进先出的数据结构,适用于回溯、优先级运算、括号匹配等问题。
  • 运算符优先级处理:在处理加减乘除等运算时,栈帮助我们按照优先级进行操作,确保高优先级操作先被计算。
  • 递归与回溯:栈模拟递归过程,通过将中间状态压栈来解决字符串解码等问题。
  • 动态修改栈顶元素:栈可以通过操作栈顶元素来完成许多复杂的任务,如删除、合并、重复等。

http://www.kler.cn/a/585824.html

相关文章:

  • 计算机网络——路由器
  • 用 Vue 3.5 TypeScript 重新开发3年前甘特图的核心组件
  • HTML5 Web SQL
  • 我的创作纪念日 打造高效 Python 日记本应用:从基础搭建到功能优化全解析
  • Java EE Web环境安装
  • MCU详解:嵌入式系统的“智慧之心”
  • 【Prometheus】prometheus监控pod资源,ingress,service资源以及如何通过annotations实现自动化监控
  • 宝塔-服务器部署(1)-环境准备
  • 如何处理PHP中的日期和时间问题
  • HTML块级元素和内联元素(简单易懂)
  • vue/react/vite前端项目打包的时候加上时间最简单版本,防止后端扯皮
  • Centos7系统基于docker下载ollama部署Deepseek-r1(GPU版不踩坑)
  • plantuml画甘特图gantt
  • SpringBoot中使用AJ-Captcha实现行为验证码(滑动拼图、点选文字)
  • stm32u5
  • std::stack和std::queue
  • iOS OC匹配多个文字修改颜色和字号
  • Language Models are Few-Shot Learners,GPT-3详细讲解
  • 【最后203篇系列】014 AI机器人-2
  • E2PRAM