首页 > 编程语言 >11.优化算法之栈

11.优化算法之栈

时间:2024-07-02 09:27:55浏览次数:26  
标签:11 String ss 之栈 public int 算法 new Stack

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

可以用数组模拟栈结构 

class Solution {
    public String removeDuplicates(String s) {
        if(s.length()<=1){
            return s;
        }
        StringBuffer ret=new StringBuffer();
        
        for(int i=0;i<s.length();i++){
            if(ret.length()<1){
                ret.append(s.charAt(i));
            }else if(s.charAt(i)==ret.charAt(ret.length()-1)){
                ret.deleteCharAt(ret.length()-1);
            }else{
                ret.append(s.charAt(i));
            }
        }
        return ret.toString();
    }
}

 

2.比较含退格的字符串 

844. 比较含退格的字符串 - 力扣(LeetCode)

class Solution {
    public boolean backspaceCompare(String s, String t) {
        return changeStr(s).equals(changeStr(t));
    }

    public String changeStr(String str1){
        StringBuffer ss=new StringBuffer();
        char[] str=str1.toCharArray();
        for(char ch:str){
            if(ch!='#'){
                ss.append(ch);//入栈
            }else{
                if(ss.length()>0){
                    ss.deleteCharAt(ss.length()-1);//出栈
                }
            }
        }
        return ss.toString();
    }
}

3.基本计算器2

. - 力扣(LeetCode)

算法原理

双端队列也可以实现栈

class Solution {
    public int calculate(String s) {
        //双端队列,实现栈操作
        Deque<Integer> deque=new ArrayDeque<>();
        char op='+';
        int i=0,n=s.length();
        char[] ss=s.toCharArray();
        while(i<n){
            //1.先考虑为空的情况
            if(ss[i]==' '){
                i++;
            }else if(ss[i]>='0'&ss[i]<='9'){
                int tmp=0;
                while(i<n&&ss[i]>='0'&ss[i]<='9'){
                    tmp=tmp*10+(ss[i]-'0');
                    i++;
                }
                if(op=='+'){
                    deque.push(tmp);
                }else if(op=='-'){
                    deque.push(-tmp);
                }else if(op=='*'){
                    deque.push(deque.poll()*tmp);
                }else if(op=='/'){
                    deque.push(deque.poll()/tmp);
                }
            }else{
                op=ss[i];
                i++;
            }
        }
        //遍历队列
        int ret=0;
        while(!deque.isEmpty()){
            ret=ret+deque.poll();
        }
        return ret;
    }
}

 4.字符串解码

394. 字符串解码 - 力扣(LeetCode)

 算法原理

class Solution {
    public String decodeString(String s) {
        int i=0,n=s.length();
        char[] ss=s.toCharArray();
        //构造栈
        Stack<StringBuffer> strstack=new Stack<>();
        //字符串要先加入一个空字符串
        //不然会出现越界的情况
        strstack.push(new StringBuffer());
        Stack<Integer> numstack=new Stack<>();
        while(i<n){
            //1.遇到数字的情况
            if(ss[i]>='0'&&ss[i]<='9'){
                int tmp=0;
                while(i<n&&ss[i]>='0'&&ss[i]<='9'){
                    tmp=tmp*10+(ss[i]-'0');
                    i++;
                }
                numstack.push(tmp);
            }else if(ss[i]==' '){
                i++;
            }else if(ss[i]=='['){
                i++;
                //后面遇到的字符串都要加入栈中
                StringBuffer str=new StringBuffer();
                while(i<n&&ss[i]>='a'&&ss[i]<='z'){
                    str.append(ss[i]);
                    i++;
                }
                strstack.push(str);
            }else if(ss[i]==']'){
                int num1=numstack.pop();
                StringBuffer str1=strstack.pop();
                while(num1--!=0){
                    strstack.peek().append(str1);
                }
                i++;
            }else{
                //后面遇到的字符串都要加入栈中
                StringBuffer str=new StringBuffer();
                while(i<n&&ss[i]>='a'&&ss[i]<='z'){
                    str.append(ss[i]);
                    i++;
                }
                strstack.peek().append(str);
            }
        }
        return strstack.peek().toString();
    }
}

 5.验证栈序列

. - 力扣(LeetCode)

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> st = new Stack<>();
        int i = 0, n = popped.length;
        for (int x : pushed) {
            st.push(x);
            while (!st.isEmpty() && st.peek() == popped[i]) {
                st.pop();
                i++;
            }
        }
        return i == n;
    }
}

标签:11,String,ss,之栈,public,int,算法,new,Stack
From: https://blog.csdn.net/m0_47017197/article/details/140070734

相关文章

  • 9.优化算法之哈希表
    classSolution{publicList<List<String>>groupAnagrams(String[]strs){Map<String,List<String>>map=newHashMap<>();for(Stringstr:strs){char[]array=str.toCharArray();Arrays.......
  • 基于摄像头抓取学生人脸朝向判断学生上课状态检测的算法
    智能检测学生听课状态的网络模型:开启高效学习的新篇章 在当今数字化教育的浪潮中,我们致力于研发一款创新的检测学生听课状态的网络模型,旨在为教育领域带来革命性的变革,提升教学质量,优化学生的学习体验。 一、模型概述这款网络模型基于先进的人工智能技术和深度学习算法......
  • 基于自适应波束成形算法的matlab性能仿真,对比SG和RLS两种方法
    1.程序功能描述基于自适应波束成形算法的matlab性能仿真,对比SG和RLS两种方法.            2.测试软件版本以及运行结果展示MATLAB2022a版本运行   3.核心程序forii=1:MTKLifSEL==1fori=1:length(r)......
  • PCL 基于点云RGB颜色的区域生长算法
    RGB颜色的区域生长算法一、概述1.1算法定义1.2算法特点1.3算法实现二、代码示例三、运行结果......
  • 算法笔记:模拟过程(螺旋遍历矩阵)
    1模拟过程“模拟过程题”通常指的是那些要求编程者通过编写代码来“模拟”或重现某个过程、系统或规则的题目。这类题目往往不涉及复杂的数据结构或高级算法,而是侧重于对给定规则的精确执行和逻辑的清晰表达。其中螺旋遍历矩阵的题目就是一类典型的模拟过程题,需要精心设......
  • 算法金 | Transformer,一个神奇的算法模型!!
    大侠幸会,在下全网同名「算法金」0基础转AI上岸,多个算法赛Top「日更万日,让更多人享受智能乐趣」抱个拳,送个礼在现代自然语言处理(NLP)领域,Transformer模型的出现带来了革命性的变化。它极大地提升了语言模型的性能和效率,而自注意力机制是其中的核心组件。今个儿我们将......
  • 11、 Django-模型基础-models-ORM框架-管理器对象
     #概述django根据属性的类型确定以下信息当前选择的数据库支持字段的类型渲染管理表单时使用的默认htm1控件在管理站点最低限度的验证django会为表增加自动增长的主键列,每个模型只能有一个主键列,如果使用选项设置某属性为主键列后则django不会再生成默认的主键列#属性命......
  • VMware安装Win11环境
    准备Win11的iso镜像下载链接:https://www.microsoft.com/zh-cn/software-download/windows11/?open_in_browser=true配置步骤步骤一——创建虚拟机1、点击创建新虚拟机2、使用典型模式3、选择镜像位置4、选择虚拟机存放位置5、输入密码,此密码可以随便写6、选择单个......
  • 0基础学C++ | 第11天 | 基础知识 | 引用
    目录引用的基本使用 引用的注意事项 引用做函数参数 引用做函数的返回值引用的本质引用的基本使用作用:引用就是给变量起别名,它不是新定义一个变量,而是给已存在变量取了一个别名,编译器不会为引用变量开辟内存空间,它和它引用的变量共用同一块内存空间。我的理解就是......
  • [JLU] 数据结构与算法上机题解思路分享-第二次上机
    前言首先,请务必自己尽全力尝试实现题目,直接看成品代码,思维就被拘束了,也很容易被查重。这里只是思路解析的博客,代码仓库在JLU_Data_Structures_Record希望你能在这里找到你想要的:)正文A二叉树的创建与遍历分数10作者朱允刚单位吉林大学通过带空指针信息的先根序列(......