代码随想录阅读笔记-栈与队列【删除字符串中的所有相邻重复项】

题目

给出由小写字母组成的字符串 S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。

在 S 上反复执行重复项删除操作,直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例:

  • 输入:"abbaca"
  • 输出:"ca"
  • 解释:例如,在 "abbaca" 中,我们可以删除 "bb" 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca",其中又只有 "aa" 可以执行重复项删除操作,所以最后的字符串为 "ca"。

提示:

  • 1 <= S.length <= 20000
  • S 仅由小写英文字母组成。

思路 

本题也是用栈来解决的经典题目。

那么栈里应该放的是什么元素呢?

我们在删除相邻重复项的时候,其实就是要知道当前遍历的这个元素,我们在前一位是不是遍历过一样数值的元素,那么如何记录前面遍历过的元素呢?

所以就是用栈来存放,那么栈的目的,就是存放遍历过的元素,当遍历当前的这个元素的时候,去栈里看一下我们是不是遍历过相同数值的相邻元素。

然后再去做对应的消除操作。 如动画所示:

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

从栈中弹出剩余元素,此时是字符串ac,因为从栈里弹出的元素是倒序的,所以再对字符串进行反转一下,就得到了最终的结果。

C++代码 :

class Solution {
public:
    string removeDuplicates(string S) {
        stack<char> st;
        for (char s : S) {
            if (st.empty() || s != st.top()) {
                st.push(s);
            } else {
                st.pop(); // s 与 st.top()相等的情况
            }
        }
        string result = "";
        while (!st.empty()) { // 将栈中元素放到result字符串汇总
            result += st.top();
            st.pop();
        }
        reverse (result.begin(), result.end()); // 此时字符串需要反转一下
        return result;

    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

当然可以拿字符串直接作为栈,这样省去了栈还要转为字符串的操作。

代码如下:

class Solution {
public:
    string removeDuplicates(string S) {
        string result;
        for(char s : S) {
            if(result.empty() || result.back() != s) {
                result.push_back(s);
            }
            else {
                result.pop_back();
            }
        }
        return result;
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1),返回值不计空间复杂度

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/486209.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

如何成功将自己开发的APP上架到应用商店

如何成功将自己开发的APP上架到应用商店 随着移动应用市场的蓬勃发展&#xff0c;开发一款优秀的APP已成为许多企业和个人的首要选择。然而&#xff0c;成功上架并有效推广APP至关重要。本文将逐步介绍完整的上架流程&#xff0c;包括准备所需材料、注册开发者账户、进行APP备…

OpenLayers基础教程——使用WebGLPoints加载海量点数据

1、前言 最近遇到一个问题&#xff1a;如何在OpenLayers中高效加载海量的场强点&#xff1f;由于项目中的一些要求&#xff0c;不能使用聚合的方法加载。一番搜索之后发现&#xff1a;OpenLayers中有一个WebGLPoints类&#xff0c;使用该类可以轻松应对几十万的数据量&#xf…

多目标追踪实现_3.9

目标 利用sort算法完成多目标追踪 在这里主要实现了一个多目标跟踪器&#xff0c;管理多个卡尔曼滤波器对象&#xff0c;主要包括以下内容&#xff1a; 初始化&#xff1a;最大检测数&#xff0c;目标未被检测的最大帧数 目标跟踪结果的更新&#xff0c;即跟踪成功和失败的目…

Android第一行代码——快速入门 Kotlin 编程(4.7 编写界面的最佳实践)

目录 4.7 编写界面的最佳实践 4.7.1 制作 9—Patch 图片 4.7.2 编写精美的聊天界面 4.7 编写界面的最佳实践 既然已经学习了那么多 UI 开发的知识,是时候实战一下了。这次我们要综合运用前面所学的大量内容来编写出一个较为复杂且相当美观的聊天…

【前端寻宝之路】JavaScript初学之旅

&#x1f308;个人主页: Aileen_0v0 &#x1f525;热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法|MySQL| ​&#x1f4ab;个人格言:“没有罗马,那就自己创造罗马~” #mermaid-svg-azUa9yH16cRXQUxE {font-family:"trebuchet ms",verdana,arial,sans-serif;f…

代码随想录算法训练营第十五天| 二叉树的层序遍历、226.翻转二叉树、101.对称二叉树

系列文章目录 目录 系列文章目录二叉树层序遍历&#xff08;10题&#xff09;102. 二叉树的层序遍历①DFS--递归方式②BFS--迭代方式--借助队列 107.二叉树的层次遍历 II199.二叉树的右视图637.二叉树的层平均值429.N叉树的层序遍历遍历每个节点的子节点 515.在每个树行中找最大…

Ftrans安全数据摆渡系统 构建便捷的内外网数据交换通道

安全数据摆渡系统是一种设计用于解决内外网环境下&#xff0c;数据传输、管理、共享问题的安全系统&#xff0c;通过加密、访问控制等策略&#xff0c;提供安全可靠的数据传输和共享服务&#xff0c;尤其适用于对网络安全建设要求高的行业&#xff0c;比如研发型企业、党政机构…

构建vue3项目以及bem架构

构建vue3vite项目 &#xff08;1&#xff09;使用vite初始化一个项目 npm init vitelatest &#xff08;2&#xff09;构建cli项目 vue create <project> bem架构 src下新建文件bem.scss $namespace: "xc" !default; $block-sel: "-" !defaul…

【LVGL-开关部件】

LVGL-开关部件 ■ LVGL-开关部件■ 开关部件&#xff1a;指示器打开的颜色■ 开关部件&#xff1a;不可修改■ 开关部件&#xff1a;获取开关状态■ 开关部件&#xff1a;示例一&#xff1a;制冷,制暖,开关 ■ LVGL-开关部件 ■ 开关部件&#xff1a;指示器打开的颜色 ■ 开关部…

Leetcode算法题笔记(2)

目录 图论51. 岛屿数量解法一 52. 腐烂的橘子解法一 53. 课程表解法一 54. 实现 Trie (前缀树)解法一 回溯55. 全排列解法一 56. 子集解法一解法二 57. 电话号码的字母组合解法一 58. 组合总和解法一解法二 59. 括号生成解法一解法二 60. 单词搜索解法一 图论 51. 岛屿数量 给…

PostgreSQL FDW(外部表) 简介

1、FDW: 外部表 背景 提供外部数据源的透明访问机制。PostgreSQL fdw(Foreign Data Wrapper)是一种外部访问接口,可以在PG数据库中创建外部表,用户访问的时候与访问本地表的方法一样,支持增删改查。 而数据则是存储在外部,外部可以是一个远程的pg数据库或者其他数据库(…

java数据结构与算法刷题-----LeetCode435. 无重叠区间

java数据结构与算法刷题目录&#xff08;剑指Offer、LeetCode、ACM&#xff09;-----主目录-----持续更新(进不去说明我没写完)&#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 文章目录 解题思路&#xff1a;贪心思想。时间复杂度O( n ∗ l o g 2 n n*…

闻了刚脱下的袜子导致肺部感染真菌?后果很严重

之前有网友分享自己只因闻了刚脱下的袜子&#xff0c;就导致了肺部感染真菌的经历&#xff0c;引发众多网友的关注与热议。 那么&#xff0c;臭袜子又怎么会和肺部感染有关系呢&#xff1f;臭袜子为什么不能闻呢&#xff1f;袜子上面到底有什么有危险的成分呢&#xff1f; 图源…

基于Matlab的血管图像增强算法,Matlab实现

博主简介&#xff1a; 专注、专一于Matlab图像处理学习、交流&#xff0c;matlab图像代码代做/项目合作可以联系&#xff08;QQ:3249726188&#xff09; 个人主页&#xff1a;Matlab_ImagePro-CSDN博客 原则&#xff1a;代码均由本人编写完成&#xff0c;非中介&#xff0c;提供…

Day20 代码随想录(1刷) 二叉树

目录 654. 最大二叉树 617. 合并二叉树 700. 二叉搜索树中的搜索 98. 验证二叉搜索树 654. 最大二叉树 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建: 创建一个根节点&#xff0c;其值为 nums 中的最大值。递归地在最大值 左边 的 子数…

Linux: 线程安全

Linux 线程共享了进程的资源(地址空间, 页表等), 多个线程同时访问同一个资源就可能产生问题:数据竞争 临界资源: 多个线程共享的资源临界区: 访问临界资源的区域互斥: 任何时刻, 只有一个执行流能进入临界区同步: 以一定顺序访问临界资源原子性: 要么完成, 玩么未完成 锁 死…

Unity Mobile Notifications推送问题

1.在部分机型点击通知弹窗进不去游戏 把这里改成自己的Activity 2.推送的时候没有横幅跟icon红点 主要是第一句话 注册的时候选项可以选择 defaultNotificationChannel new AndroidNotificationChannel(“default_channel”, “Default Channel”, “For Generic notifica…

由浅到深认识Java语言(24):Date类

该文章Github地址&#xff1a;https://github.com/AntonyCheng/java-notes 在此介绍一下作者开源的SpringBoot项目初始化模板&#xff08;Github仓库地址&#xff1a;https://github.com/AntonyCheng/spring-boot-init-template & CSDN文章地址&#xff1a;https://blog.c…

Zotero 配置教程Windonws与Linux

Zotero的安装 zotero 官网&#xff1a; Zotero | Your personal research assistant 官方文档 &#xff1a;start [Zotero Documentation] 推荐常用的插件 1、 茉莉花&#xff1a;https://github.com/l0o0/jasminum 2、 Doi管理&#xff1a;https://github.com/bwiernik/zo…

web表单标签与练习(3.18)

一、表单域 表单域是一个包含表单元素的区域。 在HTML标签中&#xff0c;< form >标签用于定义表单域&#xff0c;以实现用户信息和传递。 < form >会把它范围内的表单元素信息提交给服务器。 表单属性 action url地址 用于指定接收并处理表单数据的服务器程序的…