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

LeetCode 热题 100_字符串解码(71_394_中等_C++)(栈)

LeetCode 热题 100_字符串解码(71_394)

    • 题目描述:
    • 输入输出样例:
    • 题解:
      • 解题思路:
        • 思路一(栈):
      • 代码实现
        • 代码实现(栈):
        • 以思路一为例进行调试

题目描述:

给定一个经过编码的字符串,返回它解码后的字符串。

编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。

此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。

输入输出样例:

示例 1:
输入:s = “3[a]2[bc]”
输出:“aaabcbc”

示例 2:
输入:s = “3[a2[c]]”
输出:“accaccacc”

示例 3:
输入:s = “2[abc]3[cd]ef”
输出:“abcabccdcdcdef”

示例 4:
输入:s = “abc3[cd]xyz”
输出:“abccdcdcdxyz”

提示:
1 <= s.length <= 30
s 由小写英文字母、数字和方括号 ‘[]’ 组成
s 保证是一个 有效 的输入。
s 中所有整数的取值范围为 [1, 300]

题解:

解题思路:

思路一(栈):

1、通过中括号内嵌中括号的情况,且内嵌的中括号首先计算,可以想到栈的方法解决此问题。
字符串中有四种字符:
① 数字:将数字转换为整数(数字的位数可为多位),称为字符串的重复次数
② 字母:将连续的字母提取出来,连接成字符串
③ 左括号:重复次数和字符串 分别入 数字栈和字符串栈
④ 右括号:弹出状态(出栈),重复n次对应字符串,并连接字符串

例子:s = “3[a2[c]]”
初始状态:k=0 (数字), current=“” (部分字符串), counts栈为空,strings栈为空
① 3 为数字字符,计算连续的数字字符并转换为整数,k=3;
② [ 为左括号,将k=3 和 current=““分别压入 counts栈={3}和strings={””}栈,重置k=0,current=“”
③ a 为字母,计算连接的字母,current=“a”;
④ 2 k=2;
⑤ [ 将k=2 和 current=“a” 分别压入 counts栈={3,2}和strings栈={“”,“a”},重置k=0,current=“”
⑥ c current=“c”;
⑦ ] 遇到右括号,将counts栈={3,2}中的2出栈,此时current=“c"重复2次 -> current=“cc”,strings栈={”“,“a”}中的"a"出栈,与current连接"acc”
⑧ ] 遇到右括号,counts栈={3}中的3出栈,此时current=“acc"重复3次->current = “accaccacc”,strings栈={”“}中的”“出栈,与current连接"accaccacc”

2、复杂度分析:
① 时间复杂度: O(S),S代表解码后得出的字符串长度,我们在遍历原字符串的同时会也会将解码后的字符串压入栈中,且进行字符串的连接。
② 空间复杂度:O(S),S代表解码后得出的字符串长度,栈的总大小最终与 S 相同。

代码实现

代码实现(栈):
class Solution {
public:string decodeString(string s) {stack<int> counts;  // 用来存储数字 (重复次数),栈用来存储每个 "[" 对应的重复次数stack<string> strings;  // 用来存储之前的部分字符串,栈用来存储每个 "[" 之前的字符串string current = "";  // 用来存储当前正在构建的字符串(用于存放当前解析出来的子字符串)int k = 0;  // 用来存储当前的重复次数// 遍历字符串中的每个字符for (char c : s) {if (isdigit(c)) {// 如果是数字,构建重复次数 k,直到遇到非数字字符k = k * 10 + (c - '0');  // 处理可能多位的数字} else if (c == '[') {// 如果遇到 '[',说明要开始一个新的子字符串块counts.push(k);  // 将当前的重复次数推入栈中strings.push(current);  // 将当前构建的字符串推入栈中current = "";  // 清空当前字符串,准备构建新的子字符串k = 0;  // 重置重复次数为 0,开始处理新的重复数字} else if (c == ']') {// 如果遇到 ']',说明当前子字符串块的解析结束string temp = current;   // 将当前的字符串保存到 temp 中current = strings.top(); // 从栈中获取之前的字符串部分strings.pop();  // 弹出栈中的字符串部分int repeatCount = counts.top();  // 从栈中获取重复次数counts.pop();  // 弹出栈中的重复次数// 将当前子字符串重复 repeatCount 次,并拼接到之前的部分for (int i = 0; i < repeatCount; i++) {current += temp;  // 重复并拼接}} else {// 普通字符,直接加入当前正在构建的字符串current += c;}}return current;  // 返回解码后的最终字符串}
};
以思路一为例进行调试
#include<iostream>
#include<stack>
using namespace std;class Solution {
public:string decodeString(string s) {stack<int> counts;  // 用来存储数字 (重复次数),栈用来存储每个 "[" 对应的重复次数stack<string> strings;  // 用来存储之前的部分字符串,栈用来存储每个 "[" 之前的字符串string current = "";  // 用来存储当前正在构建的字符串(用于存放当前解析出来的子字符串)int k = 0;  // 用来存储当前的重复次数// 遍历字符串中的每个字符for (char c : s) {if (isdigit(c)) {// 如果是数字,构建重复次数 k,直到遇到非数字字符k = k * 10 + (c - '0');  // 处理可能多位的数字} else if (c == '[') {// 如果遇到 '[',说明要开始一个新的子字符串块counts.push(k);  // 将当前的重复次数推入栈中strings.push(current);  // 将当前构建的字符串推入栈中current = "";  // 清空当前字符串,准备构建新的子字符串k = 0;  // 重置重复次数为 0,开始处理新的重复数字} else if (c == ']') {// 如果遇到 ']',说明当前子字符串块的解析结束string temp = current;   // 将当前的字符串保存到 temp 中current = strings.top(); // 从栈中获取之前的字符串部分strings.pop();  // 弹出栈中的字符串部分int repeatCount = counts.top();  // 从栈中获取重复次数counts.pop();  // 弹出栈中的重复次数// 将当前子字符串重复 repeatCount 次,并拼接到之前的部分for (int i = 0; i < repeatCount; i++) {current += temp;  // 重复并拼接}} else {// 普通字符,直接加入当前正在构建的字符串current += c;}}return current;  // 返回解码后的最终字符串}
};int main(int argc, char const *argv[])
{string str="3[a2[c]]";Solution s;string ans=s.decodeString(str);cout<<ans;return 0;
}

LeetCode 热题 100_字符串解码(71_394)原题链接
欢迎大家和我沟通交流(✿◠‿◠)

相关文章:

LeetCode 热题 100_字符串解码(71_394_中等_C++)(栈)

LeetCode 热题 100_字符串解码&#xff08;71_394&#xff09; 题目描述&#xff1a;输入输出样例&#xff1a;题解&#xff1a;解题思路&#xff1a;思路一&#xff08;栈&#xff09;&#xff1a; 代码实现代码实现&#xff08;栈&#xff09;&#xff1a;以思路一为例进行调…...

「DataX」数据迁移-IDEA运行DataX方法总结

背景 业务需求希望把Oracle数据库中的数据&#xff0c;迁移至MySql数据库中&#xff0c;因为需要迁移全量和增量的数据&#xff0c;所以希望想用数据迁移工具进行操作。 经过一些调研查询&#xff0c;最终打算使用DataX进行数据的迁移。 DataX简单介绍 DataX 是阿里云 DataW…...

【 <一> 炼丹初探:JavaWeb 的起源与基础】之 Servlet 过滤器:实现请求的预处理与后处理

<前文回顾> 点击此处查看 合集 https://blog.csdn.net/foyodesigner/category_12907601.html?fromshareblogcolumn&sharetypeblogcolumn&sharerId12907601&sharereferPC&sharesourceFoyoDesigner&sharefromfrom_link <今日更新> 一、过滤器&…...

DeepSeek与浏览器自动化AI Agent构建指南

文章使用到的模型可以用硅基流动中的&#xff1a; 注册链接&#xff1a;硅基流动统一登录 邀请码&#xff1a;FytHp9Xa 一、技术选型阶段 1. 基础组件选择 AI模型&#xff1a;DeepSeek-R1开放API&#xff08;对话/推理&#xff09;或DeepSeek-Coder&#xff08;代码生成&#…...

面试中常问的mysql数据库指令【杭州多测师_王sir】

数据库中的修改表结构、增删改查、用户权限操作DDL 》数据库定义语言 create database&#xff0c;create table drop tableDML 》数据库操作语言 insert into&#xff0c;delete from&#xff0c;update set&#xff0c;DQL 》数据库查询语言 select .... from....crea…...

深度学习驱动的智能化革命:从技术突破到行业实践

第一章 深度学习的技术演进与核心架构 1.1 从浅层网络到深度学习的范式转变 深度学习的核心在于通过多层次非线性变换自动提取数据特征,其发展历程可划分为三个阶段:符号主义时代的规则驱动(1950s-1980s)、连接主义时代的浅层网络(1990s-2000s)以及深度学习时代的端到端…...

基于编译器特性浅析C++程序性能优化

最近在恶补计算机基础知识&#xff0c;学到CSAPP第五章的内容&#xff0c;在这里总结并且展开一下C程序性能优化相关的内容。 衡量程序性能的方式 一般而言&#xff0c;程序的性能可以用CPE&#xff08;Cycles Per Element&#xff09;来衡量&#xff0c;其指的是处理每个元素…...

服务器上通过ollama部署deepseek

2025年1月下旬&#xff0c;DeepSeek的R1模型发布后的一周内就火了&#xff0c;性能比肩OpenAI的o1模型&#xff0c;且训练成本仅为560万美元&#xff0c;成本远低于openAI&#xff0c;使得英伟达股票大跌。 下面我们来看下如何个人如何部署deepseek-r1模型。 我是用的仙宫云的…...

Android Coil总结

文章目录 Android Coil总结概述添加依赖用法基本用法占位图变形自定义ImageLoader取消加载协程支持缓存清除缓存监听 简单封装 Android Coil总结 概述 Coil 是一个用于 Android 的 Kotlin 图像加载库&#xff0c;旨在简化图像加载和显示的过程。它基于 Kotlin 协程&#xff0…...

《安富莱嵌入式周报》第351期:DIY半导体制造,工业设备抗干扰提升方法,NASA软件开发规范,小型LCD在线UI编辑器,开源USB PD电源,开源锂电池管理

周报汇总地址&#xff1a;嵌入式周报 - uCOS & uCGUI & emWin & embOS & TouchGFX & ThreadX - 硬汉嵌入式论坛 - Powered by Discuz! 视频版&#xff1a; https://www.bilibili.com/video/BV16C95YEEZs 《安富莱嵌入式周报》第351期&#xff1a;DIY半导体…...

Redis在人员管理系统中的应用示例

用户会话管理 场景&#xff1a;用户登录后存储会话信息&#xff0c;支持多服务器共享 实现&#xff1a; 用户登录成功后&#xff0c;生成唯一Token&#xff08;如JWT&#xff09;&#xff0c;作为Redis的Key Value存储用户ID、角色、权限等信息&#xff0c;设置过期时间&…...

The Wedding Juicer POJ - 2227

采取从外层边界&#xff0c;一步一步向内部拓展的策略&#xff0c;具体来说&#xff0c;一开始将最外面一层的点加入队列&#xff0c;并标记这些点的坐标已经被访问 取出队列中高度最低的点&#xff0c;将其弹出&#xff0c;查看其上下左右的点&#xff0c;如果新点没有被访问…...

# 深入理解RNN(一):循环神经网络的核心计算机制

深入理解RNN&#xff1a;循环神经网络的核心计算机制 RNN示意图 引言 在自然语言处理、时间序列预测、语音识别等涉及序列数据的领域&#xff0c;循环神经网络(RNN)一直扮演着核心角色。尽管近年来Transformer等架构逐渐成为主流&#xff0c;RNN的基本原理和思想依然对于理…...

分布式锁—6.Redisson的同步器组件

大纲 1.Redisson的分布式锁简单总结 2.Redisson的Semaphore简介 3.Redisson的Semaphore源码剖析 4.Redisson的CountDownLatch简介 5.Redisson的CountDownLatch源码剖析 1.Redisson的分布式锁简单总结 (1)可重入锁RedissonLock (2)公平锁RedissonFairLock (3)联锁MultiL…...

同步 Fork 仓库的命令

同步 Fork 仓库的命令 要将您 fork 的仓库的 main 分支与原始仓库&#xff08;fork 源&#xff09;同步&#xff0c;您可以使用以下命令&#xff1a; 首先&#xff0c;确保您已经添加了原始仓库作为远程仓库&#xff08;如果尚未添加&#xff09;&#xff1a; git remote add…...

基于PySide6的CATIA零件自动化着色工具开发实践

引言 在汽车及航空制造领域&#xff0c;CATIA作为核心的CAD设计软件&#xff0c;其二次开发能力对提升设计效率具有重要意义。本文介绍一种基于Python的CATIA零件着色工具开发方案&#xff0c;通过PySide6实现GUI交互&#xff0c;结合COM接口操作实现零件着色自动化。该方案成…...

OpenManus 的提示词

OpenManus 的提示词 引言英文提示词的详细内容工具集的详细说明中文翻译的详细内容GitHub 仓库信息背景分析总结 引言 OpenManus 是一个全能 AI 助手&#xff0c;旨在通过多种工具高效地完成用户提出的各种任务&#xff0c;包括编程、信息检索、文件处理和网页浏览等。其系统提…...

Ubuntu-docker安装mysql

只记录执行步骤。 1 手动下载myql镜像&#xff08;拉去华为云镜像&#xff09; docker pull swr.cn-east-3.myhuaweicloud.com/library/mysql:latest配置并启动mysql 在opt下创建文件夹 命令&#xff1a;cd /opt/ 命令&#xff1a;mkdir mysql_docker 命令&#xff1a;cd m…...

Electron桌面应用开发:自定义菜单

完成初始应用的创建Electron桌面应用开发&#xff1a;创建应用&#xff0c;随后我们就可以自定义软件的菜单了。菜单可以帮助用户快速找到和执行命令&#xff0c;而不需要记住复杂的快捷键&#xff0c;通过将相关功能组织在一起&#xff0c;用户可以更容易地发现和使用应用程序…...

理解 JavaScript 中的浅拷贝与深拷贝

在 JavaScript 开发中&#xff0c;我们经常需要复制对象或数组。然而&#xff0c;复制的方式不同&#xff0c;可能会导致不同的结果。本文将详细介绍 浅拷贝 和 深拷贝 的概念、区别以及实现方式&#xff0c;帮助你更好地理解和使用它们。 1. 什么是浅拷贝&#xff1f; 定义 …...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

站群服务器的应用场景都有哪些?

站群服务器主要是为了多个网站的托管和管理所设计的&#xff0c;可以通过集中管理和高效资源的分配&#xff0c;来支持多个独立的网站同时运行&#xff0c;让每一个网站都可以分配到独立的IP地址&#xff0c;避免出现IP关联的风险&#xff0c;用户还可以通过控制面板进行管理功…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

API网关Kong的鉴权与限流:高并发场景下的核心实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中&#xff0c;API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关&#xff0c;Kong凭借其插件化架构…...