首页 > 编程语言 >(算法)⽐较含退格的字符串————<栈—模拟>

(算法)⽐较含退格的字符串————<栈—模拟>

时间:2024-08-29 21:23:23浏览次数:12  
标签:String ret 算法 退格 字符串 public 模拟 string

1. 题⽬链接:844.⽐较含退格的字符串

2. 题⽬描述:

3. 解法(⽤数组模拟栈):

算法思路:

由于退格的时候需要知道「前⾯元素」的信息,⽽且退格也符合「后进先出」的特性。因此我们可以 使⽤「栈」结构来模拟退格的过程。

• 当遇到⾮# 字符的时候,直接进栈;

• 当遇到# 的时候,栈顶元素出栈。 

为了⽅便统计结果,我们使⽤「数组」来模拟实现栈结构。  

C++算法代码: 

class Solution 
{
public:
    //处理字符串
    string changestr(string key)
    {
        string a;
        for(int i=0;i<key.size();i++)
        {
            if(key[i]!='#')
            {
                a+=key[i];
            }
            else
            {
                if(a.size())
                {
                    a.pop_back();
                }
            }
        }
        return a;
    } 
    bool backspaceCompare(string s, string t)
    {
        return changestr(s)==changestr(t);
    }
};

Java算法代码:

class Solution
{
	public boolean backspaceCompare(String s, String t)
	{
		return changeStr(s).equals(changeStr(t));
	}
	public String changeStr(String s)
	{
		StringBuffer ret = new StringBuffer(); // ⽤数组模拟栈结构 
		for (int i = 0; i < s.length(); i++)
		{
			char ch = s.charAt(i);
			if (ch != '#')
			{
				ret.append(ch); // ⼊栈 
			}
			else
			{
				if (ret.length() > 0) ret.deleteCharAt(ret.length() - 1); // 出栈 
			}
		}
		return ret.toString();
	}
}

标签:String,ret,算法,退格,字符串,public,模拟,string
From: https://blog.csdn.net/2301_79580018/article/details/141687802

相关文章

  • 数据结构与算法 第3天(栈和队列)
    栈和队列也是线性表,限制插入和删除的位置只能在端点栈(stack)后进先出LIFO表尾进入,表尾删除一、案例案例一:进制转换例子159转换成八进制159/8=19...719/8=2...32/8=0...2结果为237案例二:括号匹配的检验左括号先入栈,右括号有匹配的话与左括号一起出栈案例三:表......
  • python实现RC4加解密算法
    目录RC4算法简介RC4算法的加密和解密流程RC4算法的Python实现代码解释RC4算法的应用场景RC4的安全性分析总结RC4(RivestCipher4)是一种流加密算法,由RonRivest于1987年设计。RC4广泛应用于各种加密协议,如SSL/TLS和WEP/WPA等。RC4算法因其简单、高效的特点受到广泛关......
  • Python实现SM4加解密算法
    目录SM4算法简介SM4算法的加密和解密流程SM4算法的Python实现代码解释总结SM4算法是中国国家密码局设计的块密码算法,广泛应用于无线局域网标准和其他安全通信系统中。以下是SM4算法的详细介绍,包括加密解密流程和Python的完整实现。SM4算法简介SM4是一种对称分组......
  • Python实现等距映射(ISOMAP)降维算法
    目录Python实现等距映射(ISOMAP)降维算法的博客引言ISOMAP算法原理ISOMAP的优势与局限Python实现ISOMAP算法1.创建ISOMAP类2.在瑞士卷数据集上应用ISOMAP3.结果分析总结运行结果Python实现等距映射(ISOMAP)降维算法的博客引言在高维数据处理中,降维是一种常用的技......
  • 代码随想录算法训练营,29日 | 704. 二分查找,27. 移除元素,977.有序数组的平方,209.长度最
    数组基础文档讲解︰代码随想录(programmercarl.com)1.连续空间、相同类型元素2.元素只能覆盖3.二维数组的地址连续吗(C++连续,Java不连续)704.二分查找题目链接:704.二分查找文档讲解︰代码随想录(programmercarl.com)视频讲解︰二分查找日期:2024-08-29思路:第一反应是想到二分查......
  • Java算法之Gnome 排序
    简介Gnome排序,又称为双向插入排序或鸡尾酒排序,是一种改进的插入排序算法。它在每次迭代中不仅将最小的元素移动到前面,同时也将最大的元素移动到后面。这种排序算法在每次迭代中同时向两个方向进行移动,因此得名。算法步骤从数组的两端开始,向中间进行扫描。如果左侧元素大于......
  • Java算法之基数排序(Radix Sort)
    简介基数排序是一种非比较型整数排序算法,其原理是按照低位先排序,然后收集,再按照高位排序,再收集,依次类推,直到最高位。这种方法可以视为对每个位上的数字进行稳定的排序。算法步骤确定最大数的位数。对每一位进行排序:从最低位开始,使用稳定的排序算法(如计数排序)对当前位进......
  • 30-物体检测算法R-CNN SSD YOLO
    1、R-CNN2、FastR-CNN3、FasterR-CNN4、MaskR-CNN5、SSD6、YOLO......
  • Spark MLlib模型训练—回归算法 Decision tree regression
    SparkMLlib模型训练—回归算法Decisiontreeregression在机器学习中,决策树是一种常用且直观的模型,广泛应用于分类和回归任务。决策树回归(DecisionTreeRegression)通过将数据集分割成多个区域,构建一棵树形结构,以预测目标变量的连续值。本文将详细探讨Spark中的决......
  • Spark MLlib模型训练—回归算法 GLR( Generalized Linear Regression)
    SparkMLlib模型训练—回归算法GLR(GeneralizedLinearRegression)在大数据分析中,线性回归虽然常用,但在许多实际场景中,目标变量和特征之间的关系并非线性,这时广义线性回归(GeneralizedLinearRegression,GLR)便应运而生。GLR是线性回归的扩展,能够处理非正态分布的目标......