力扣题解2390

大家好,欢迎来到无限大的频道。

今日继续给大家带来力扣题解。

题目描述​(中等):

从字符串中移除星号 

给你一个包含若干星号 * 的字符串 s 。

在一步操作中,你可以:

      • 选中 s 中的一个星号。

      • 移除星号 左侧 最近的那个 非星号 字符,并移除该星号自身。

返回移除 所有 星号之后的字符串。

注意:

      • 生成的输入保证总是可以执行题面中描述的操作。

      • 可以证明结果字符串是唯一的。

解题思路:

    ​我看到这个题,思路就是直接抽象,题目要求的就是字符串当中的星号和非星号区分开来,每当遇到一个星号时,移除前面最近的一个字符。这种行为可以被抽象为一个栈的操作,当遇到字符时,将其压入栈中;当遇到星号时,从栈中弹出一个字符。(作为一个中等题来说,多少有些简单了)

  1. 使用栈结构:我们可以使用一个栈来存储字符串中的字符。栈的顶端代表最近添加的字符。

  2. 遍历字符串:遍历给定的字符串 s:

    • 如果遇到一个普通字符(非星号),将其压入栈中。

    • 如果遇到一个星号(*),则从栈中弹出一个字符(如果栈不为空)。

  3. 重建字符串:遍历完字符串后,栈中剩下的字符就是移除星号后所需的字符串。将这些字符复制回原始字符串 s 中,并在末尾添加字符串结束符 \0。

  4. 释放内存:最后,释放用于存储栈的动态分配内存。

参考代码:
char* removeStars(char* s) {
    char* stack = malloc(strlen(s) + 1);
    int top = -1;

    for(int i = 0;s[i] != '\0'; i++){
        if (s[i] != '*'){
            stack[++top] = s[i];
        }else{
            if (top != -1){
                top--;
            }
        }
    }

    for (int i = 0; i <= top; i++){
        s[i] = stack[i];
    }

    s[top + 1] = '\0';
    free(stack);

    return s;
}

时间复杂度:​

      • 遍历字符串:字符串的长度为 n,我们需要遍历每个字符一次,因此这一部分的时间复杂度为 O(n)。

      • 重建字符串:在遍历完字符串后,我们还需要将栈中的字符复制回字符串中,这也是 O(n) 的操作。

综上所述,整体时间复杂度为 O(n)。

空间复杂度:

      • 栈的使用:我们使用了一个与输入字符串长度相同的栈来存储字符,最坏情况下(没有星号的情况下),栈的大小可以达到 n。

      • 额外的空间:除了栈之外,算法没有使用其他显著的额外空间。

因此,空间复杂度为 O(n)。

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

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

相关文章

清理C盘缓存,删除电脑缓存指令是什么

在处理计算机系统的C盘缓存清理任务时&#xff0c;需要谨慎操作以确保系统的稳定性和数据的安全性。通常&#xff0c;Windows操作系统中并没有直接的“一键清理C盘缓存”的单一命令&#xff0c;因为缓存文件分散存储于多个位置&#xff0c;并且有些缓存对于系统性能至关重要&am…

HarmonyOS元服务与卡片

元服务与卡片 文章目录 一、元服务1.介绍2.常见元服务项目步骤 二、卡片1.介绍2.卡片的创建3.卡片的数据的变更4.卡片的进程间通讯4.1使用工具包4.2使用步骤 5.卡片路由postCardAction&#xff1a;快速拉起后台5.1格式5.2快速拉起指定页面--router5.3调用后台功能--call5.3卡片…

基于Java的房地产在线营销管理系统研究与实现

目录 前言 功能设计 系统实现 获取源码 博主主页&#xff1a;百成Java 往期系列&#xff1a;Spring Boot、SSM、JavaWeb、python、小程序 前言 随着信息技术的迅猛发展&#xff0c;互联网已经渗透到我们生活的方方面面&#xff0c;为各行各业带来了前所未有的变革。房地产…

Linux学习笔记8 理解Ubuntu网络管理,做自己网络的主人

本文讲解了Ubuntu下网络由什么管理&#xff0c;介绍了临时ip和路由的设置方法&#xff0c;介绍了静态持久化网络配置的方法以及各网络管理软件之间的关系。 来看看Ubuntu网络管理。 序言 原本学习ubuntu网络管理就是为了检查nginx安装过程中使用wget获取压缩包为什么解析不出…

Python编码系列—Python适配器模式:无缝集成的桥梁

&#x1f31f;&#x1f31f; 欢迎来到我的技术小筑&#xff0c;一个专为技术探索者打造的交流空间。在这里&#xff0c;我们不仅分享代码的智慧&#xff0c;还探讨技术的深度与广度。无论您是资深开发者还是技术新手&#xff0c;这里都有一片属于您的天空。让我们在知识的海洋中…

Jenkins怎么设置每日自动执行构建任务?

在 Jenkins 中设置每日自动执行构建任务可以按照以下步骤进行&#xff1a; 一、安装必要插件 确保安装了 “Timestamper” 插件&#xff0c;这个插件可以为构建添加时间戳&#xff0c;方便查看构建的执行时间。 二、配置任务 打开需要设置每日自动执行的 Jenkins 任务。在 …

105.游戏安全项目-基址的技术原理-分析技巧

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 内容参考于&#xff1a;易道云信息技术研究院 本人写的内容纯属胡编乱造&#xff0c;全都是合成造假&#xff0c;仅仅只是为了娱乐&#xff0c;请不要盲目相信…

品牌力是什么?如何评估企业品牌影响力?

品牌影响力&#xff0c;其实就是指品牌在消费者心智中所占据的位置&#xff0c;以及它对消费者购买决策和行为的影响力。如果一个企业的品牌影响力越强&#xff0c;它在消费者心中的印象就越深刻&#xff0c;能够更有效地驱动消费者的购买行为&#xff0c;形成品牌忠诚度&#…

【C++ 学习】多态的基础和原理(10)

目录 前言1. 概念2. 多态的定义及实现2.1 多态的构成条件2.2 虚函数2.3 虚函数重写2.4 虚函数重写的例外2.4.1 协变2.4.1 析构函数的重写 2.5 多态调用和普通调用2.6 函数重写/函数隐藏/函数重载 的对比2.6.1 函数重写2.6.2 函数隐藏2.6.3 函数重载 2.7 C11 final 和override 3…

爬虫--翻页tips

免责声明&#xff1a;本文仅做分享&#xff01; 伪线程 from DrissionPage import ChromiumPage import timepage ChromiumPage() page.get("https://you.ctrip.com/sight/taian746.html") # 初始化 第0页 index_page 0# 翻页点击函数 sleep def page_turn():page…

计算机毕业设计 美妆神域网站的设计与实现 Java实战项目 附源码+文档+视频讲解

博主介绍&#xff1a;✌从事软件开发10年之余&#xff0c;专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精…

IP 协议分析《实验报告》

目录 一、 实验目的 二、实验设备和环境 三、实验记录 1、实验环境搭建 2、IP 协议分析 1.设置抓包接口 2.IP 报文分析 3.报文长度计算 4.生存时间 TTL 5.分析总结 3、IP分片 1.IP 分片简介 2.捕获分组 3.结果分析 一、 实验目的 1、掌握 IP 协议数据报格式&…

硬件工程师笔试面试——保险丝

目录 10、保险丝 10.1 基础 保险丝原理图 保险丝实物图 10.1.1 概念 10.1.2 保险丝的工作原理 10.1.3 保险丝的主要类型 10.1.4 保险丝的选择和使用注意事项 10.2 相关问题 10.2.1 保险丝的额定电流和额定电压是如何确定的? 10.2.2 保险丝的熔断速度对电路保护有何…

2024年PMP报考需要什么条件?怎么报名?

PMP证书报名的门槛并不高&#xff0c;在项目管理领域里也很热门&#xff0c;很多公司要求项目组成员去考PMP证书的&#xff0c;很多招聘JD也要求持PMP证书优先&#xff0c;如果你是在项目相关管理岗位工作&#xff0c;不妨一起考一个。 一、PMP报考条件 PMP 报考条件是需要35个…

AI是否会带来一场认知革命?Reid Hoffman 的独特见解

随着人工智能&#xff08;AI&#xff09;技术的迅猛发展&#xff0c;关于AI对人类社会及认知的影响&#xff0c;已经成为了学术界和业界热议的话题。硅谷著名投资人、LinkedIn联合创始人Reid Hoffman&#xff0c;在斯坦福大学的演讲中分享了他对AI的深刻看法。他认为&#xff0…

Windows版本下Redis安装与使用---详解

目录 1、下载Redis压缩包 2、解压到文件夹 3、启动Redis服务 4、打开Redis客户端进行连接 5、使用一些基础操作来测试 6、Redis常用的服务指令 7、C#项目使用redis 8、C#中使用StackExchange.Redis库操作Redis 9、执行 Redis 命令 10、常见报错和相关指令 1、下载Redi…

翻页时钟 2.0-自动置顶显示,点击小时切换显示标题栏不显示标题栏-供大家学习研究参考

更新内容 自动置顶显示点击小时切换显示标题栏&#xff0c;&#xff08;显示标题栏后可移动时钟位置&#xff0c;鼠标拖动边框调整时钟大小&#xff09;不显示标题栏时&#xff0c;透明部分光标可穿透修正一个显示bu 下载地址&#xff1a; https://download.csdn.net/download…

技术美术百人计划 | 《4.5 DOF景深算法》笔记

1. 景深定义 景深&#xff08;Depth of Field&#xff0c;DOF&#xff09;&#xff0c;是指在摄影机镜头或其他成像器前沿能够取得清晰图像的成像所测定的被摄物体前后距离范围。镜头光圈、镜头焦距、及焦平面到拍摄物的距离是影响景深的重要因素。在聚焦完成后&#xff0c;焦点…

基于SpringBoot的招生宣传管理系统【附源码】

基于SpringBoot的招生宣传管理系统&#xff08;源码L文说明文档&#xff09; 目录 4 系统设计 4.1 系统概述 4.2系统功能结构设计 4.3数据库设计 4.3.1数据库E-R图设计 4.3.2 数据库表结构设计 5 系统实现 5.1管理员功能介绍 5.1.1管理员登录 …

[数据集][目标检测]智慧交通铁路人员危险行为躺站坐检测数据集VOC+YOLO格式3766张4类别

图片数量(jpg文件个数)&#xff1a;3766 标注数量(xml文件个数)&#xff1a;3766 标注数量(txt文件个数)&#xff1a;3766 标注类别数&#xff1a;4 标注类别名称:["sitting","sleeping","standing","track"] 每个类别标注的框数&…