LeetCode 394. 字符串解码详解:Java栈实现与逐行解析
文章目录
- 1. 问题描述
- 2. 解决思路
- 核心问题
- 栈的应用
- 遍历逻辑
- 3. 完整代码实现
- 4. 关键代码解析
- 处理右括号 `]`
- 处理嵌套的示例
- 5. 复杂度分析
- 6. 总结
1. 问题描述
给定一个经过编码的字符串,要求将其解码为原始字符串。编码规则为 k[encoded_string]
,表示方括号内的 encoded_string
重复 k
次。其中 k
为正整数,且输入的字符串保证合法。编码字符串中可能存在多层嵌套括号,例如 3[a2[c]]
解码后为 accaccacc
。
示例:
- 输入:
s = "3[a2[c]]"
- 输出:
"accaccacc"
2. 解决思路
核心问题
处理嵌套括号和重复次数的叠加关系,需确保内层括号的字符串先解码,再与外层结果拼接。
栈的应用
- 双栈结构:使用两个栈分别存储重复次数和字符串片段。
- 次数栈 (
countStack
):存储遇到的重复次数k
。 - 字符串栈 (
stringStack
):存储遇到左括号[
前的字符串片段。
- 次数栈 (
- 当前状态维护:
num
:累积当前数字(可能为多位数)。res
:记录当前正在处理的字符串。
遍历逻辑
- 遇到数字:累积到
num
。 - 遇到左括号
[
:将num
和res
压入栈,并重置num
和res
。 - 遇到右括号
]
:弹出栈顶元素,拼接重复后的字符串。 - 遇到字母:直接追加到当前字符串。
3. 完整代码实现
import java.util.Stack;class Solution {public String decodeString(String s) {StringBuilder res = new StringBuilder(); // 当前处理的字符串Stack<Integer> countStack = new Stack<>(); // 存储重复次数k的栈Stack<StringBuilder> stringStack = new Stack<>(); // 存储外层字符串的栈int num = 0; // 当前累积的数字for (char c : s.toCharArray()) {if (Character.isDigit(c)) {// 处理多位数字,如 "100" 中的 '1','0','0'num = num * 10 + (c - '0');} else if (c == '[') {// 压栈:保存当前状态(重复次数和字符串)countStack.push(num);stringStack.push(res);// 重置状态,准备处理括号内的内容res = new StringBuilder();num = 0;} else if (c == ']') {// 弹出栈顶元素,拼接重复后的字符串int k = countStack.pop(); // 重复次数StringBuilder prev = stringStack.pop(); // 外层字符串片段String temp = res.toString(); // 当前括号内的结果for (int i = 0; i < k; i++) {prev.append(temp); // 重复k次并拼接}res = prev; // 更新当前字符串为拼接后的结果} else {// 字母字符直接追加res.append(c);}}return res.toString();}
}
4. 关键代码解析
处理右括号 ]
int k = countStack.pop(); // 弹出最近的重复次数k
StringBuilder prev = stringStack.pop(); // 弹出外层字符串片段
String temp = res.toString(); // 当前括号内的字符串for (int i = 0; i < k; i++) { prev.append(temp); // 将temp重复k次拼接到prev
}res = prev; // 更新当前字符串为拼接后的结果
- 弹出栈顶元素:
k
是当前括号的重复次数,prev
是进入当前括号前的外层字符串。 - 拼接逻辑:将当前括号内的字符串
temp
重复k
次,拼接到prev
后,更新res
。
处理嵌套的示例
以 3[a2[c]]
为例:
- 初始状态:
res = ""
,栈为空。 - 遇到
3[
:压栈countStack = [3]
,stringStack = [""]
,重置res = ""
。 - 处理
a
:res = "a"
。 - 遇到
2[
:压栈countStack = [3, 2]
,stringStack = ["", "a"]
,重置res = ""
。 - 处理
c
:res = "c"
。 - 遇到
]
:弹出k=2
和prev="a"
,拼接后res = "acc"
。 - 再次遇到
]
:弹出k=3
和prev=""
,拼接后res = "accaccacc"
。
5. 复杂度分析
- 时间复杂度:O(n),其中 n 是解码后的字符串长度。每个字符最多被处理一次。
- 空间复杂度:O(m),m 是输入字符串中括号的嵌套层数,栈的深度与嵌套层数相关。
6. 总结
通过栈结构,可以高效处理嵌套括号问题,每次遇到左括号时保存当前状态,遇到右括号时恢复状态并拼接结果。该方法逻辑清晰,能够处理任意层数的嵌套结构,是解决此类编码字符串问题的经典方案。
相关文章:
LeetCode 394. 字符串解码详解:Java栈实现与逐行解析
文章目录 1. 问题描述2. 解决思路核心问题栈的应用遍历逻辑 3. 完整代码实现4. 关键代码解析处理右括号 ]处理嵌套的示例 5. 复杂度分析6. 总结 1. 问题描述 给定一个经过编码的字符串,要求将其解码为原始字符串。编码规则为 k[encoded_string],表示方括…...
基于STC89C52的红外遥控的电子密码锁设计与实现
一、引言 电子密码锁作为一种安全便捷的门禁系统,广泛应用于家庭、办公室等场景。结合红外遥控功能,可实现远程控制开锁,提升使用灵活性。本文基于 STC89C52 单片机,设计一种兼具密码输入和红外遥控的电子密码锁系统,详细阐述硬件选型、电路连接及软件实现方案。 二、硬…...
Android 性能优化入门(一)—— 数据结构优化
1、概述 一款 app 除了要有令人惊叹的功能和令人发指交互之外,在性能上也应该追求丝滑的要求,这样才能更好地提高用户体验: 优化目的性能指标优化的方向更快流畅性启动速度页面显示速度(显示和切换)响应速度更稳定稳定性避免出现 应用崩溃&…...
深入理解Docker和K8S
深入理解Docker和K8S Docker 是大型架构的必备技能,也是云原生核心。Docker 容器化作为一种轻量级的虚拟化技术,其核心思想:将应用程序及其所有依赖项打包在一起,形成一个可移植的单元。 容器的本质是进程: 容器是在…...
5.18本日总结
一、英语 复习list3list28 二、数学 学习14讲部分内容,1000题13讲部分 三、408 学习计网5.3剩余内容 四、总结 计网TCP内容比较重要,连接过程等要时常复习;高数学到二重积分对定积分的计算相关方法有所遗忘,需要加强巩固。…...
muduo库TcpServer模块详解
Muduo库核心模块——TcpServer Muduo库的TcpServer模块是一个基于Reactor模式的高性能TCP服务端实现,负责管理监听端口、接受新连接、分发IO事件及处理连接生命周期。 一、核心组件与职责 Acceptor 监听指定端口,接受新连接,通过epoll监听l…...
深入理解 OpenCV 的 DNN 模块:从基础到实践
在计算机视觉领域蓬勃发展的当下,深度学习模型的广泛应用推动着技术的不断革新。OpenCV 作为一款强大且开源的计算机视觉库,其 DNN(Deep Neural Network)模块为深度学习模型的落地应用提供了高效便捷的解决方案。本文将以理论为核…...
MyBatis 延迟加载与缓存
一、延迟加载策略:按需加载,优化性能 1. 延迟加载 vs 立即加载:核心区别 立即加载:主查询(如查询用户)执行时,主动关联加载关联数据(如用户的所有账号)。 场景…...
6.2.2邻接表法-图的存储
知识总览: 为什么要用邻接表 因为邻接矩阵的空间复杂度高(O(n)),且不适合边少的稀疏图,所以有了邻接表 用代码表示顶点、图 声明顶点图信息 声明顶点用一维数组存储各个顶点的信息,一维数组字段包括2个,每个顶点的…...
【甲方安全建设】拉取镜像执行漏洞扫描教程
文章目录 前置知识镜像(Docker Image)是什么?镜像的 tag(标签)查看本地已有镜像的 tag查看远程仓库的所有 tag构建镜像与拉取镜像的区别正文安装docker拉取待扫描镜像安装 veinmind-runner 镜像下载 veinmind-runner 平行容器启动脚本快速扫描本地镜像/容器6. 生成 报告前…...
第四天的尝试
目录 一、每日一言 二、练习题 三、效果展示 四、下次题目 五、总结 一、每日一言 很抱歉的说一下,我昨天看白色巨塔电视剧,看的入迷了,同时也看出一些道理,学到东西; 但是把昨天的写事情给忘记了,今天…...
大数据场景下数据导出的架构演进与EasyExcel实战方案
一、引言:数据导出的演进驱动力 在数字化时代,数据导出功能已成为企业数据服务的基础能力。随着数据规模从GB级向TB级甚至PB级发展,传统导出方案面临三大核心挑战: 数据规模爆炸:单次导出数据量从万级到亿级的增长…...
svn: E170013 和 svn: E120171 的问题
在 Deepin23 上尝试用 svn 连接我的 Visual SVN 服务器,得到如下错误信息, > svn: E170013: Unable to connect to a repository at URL https://my.com/svn/mysource/branch_4.2.x > svn: E120171: 执行上下文错误: An error occurred during SSL…...
Limesurvay系统“48核心92GB服务器”优化方案
1、Redis maxmemory 16GB # 限制Redis内存(预留足够空间给其他服务) maxmemory-policy volatile-lru # 自动淘汰旧会话(仅对带TTL的键) save 300 100 # 仅保留一个条件减少阻塞 stop-writes-on-bgsave-error no #…...
DockerFile实战
背景 在上一篇文章中,我们对DockerFile有了一个较为深刻的认识,那么这篇文章,我将会向你展示如何自定义一个镜像并且在docker上运行。 一、基础指令 指令技术说明生产环境最佳实践典型错误示例FROM- 必须作为Dockerfile第一条指令 - 推…...
【Linux】简易版Shell实现(附源码)
🌟🌟作者主页:ephemerals__ 🌟🌟所属专栏:Linux 前言 之前我们学习了Linux的进程概念以及进程控制相关接口: 【Linux】进程控制-CSDN博客 本篇文章,我们将一起踏上一段有趣的旅程&a…...
MATLAB安装常见问题解决方案
目前新版本的matlab安装往往需要十几G的本地安装容量,例如matlab2022b、matlab2023b, 首先就是要保证本地硬盘空间足够大,如果没有足够的本地内存空间,那么可以尝试释放本地硬盘空间,或者安装所需内存空间较小的旧版本的matlab&am…...
在 Vue 中插入 B 站视频
前言 在 Vue 项目中,有时我们需要嵌入 B 站视频来丰富页面内容,为用户提供更直观的信息展示。本文将详细介绍在 Vue 中插入 B 站视频的多种方法。 使用<iframe>标签直接嵌入,<iframe>标签是一种简单直接的方式,可将 B 站视频嵌…...
【深度学习】#12 计算机视觉
主要参考学习资料: 《动手学深度学习》阿斯顿张 等 著 【动手学深度学习 PyTorch版】哔哩哔哩跟李沐学AI 目录 目标检测锚框交并比(IoU)锚框标注真实边界框分配偏移量计算损失函数 非极大值抑制预测 多尺度目标检测单发多框检测(S…...
QT学习3
QT项目视图 1、List View清单视图 private:QListView *listview1; private slots:void slotClickedFunc(const QModelIndex &index); #include "widget.h" #include "ui_widget.h"#include <QStringListModel>//字符串列表模型 #include <QS…...
Vue 3 动态 ref 的使用方式(表格)
一、问题描述 先给大家简单介绍一下问题背景。我正在开发的项目中,有一个表格组件,其中一列是分镜描述,需要支持视频上传功能。用户可以为每一行的分镜描述上传对应的视频示例。然而,在实现过程中,出现了一个严重的问…...
FAST-DDS源码分析PDP(一)
准备开一个FAST-DDS源码分析系列,源码版本FAST-DDS 1.1.0版本。 FAST-DDS这种网络中间件是非常复杂的,所以前期先去分析每个类的作用是什么,然后在结合RTPS DOC,FAST-DDS DEMO,以及FAST-DDS的doc去串起来逻辑。 Builtin Discovery…...
Flutter与Kotlin Multiplatform(KMP)深度对比及鸿蒙生态适配解析
Flutter 与 Kotlin Multiplatform(KMP)深度对比及鸿蒙生态适配解析 在跨平台开发领域,Flutter 与 Kotlin Multiplatform(KMP)代表了两种不同的技术路线:前者以 “统一 UI 体验” 为核心,后者以…...
深入了解linux系统—— 基础IO(上)
文件 在之前学习C语言文件操作时,我们了解过什么是文件,这里简单回顾一下: 文件存在磁盘中,文件有分为程序文件、数据文件;二进制文件和文本文件等。 详细描述见文章:文件操作——C语言 文件在磁盘里&a…...
C++ map multimap 容器:赋值、排序、大小与删除操作
概述 map和multimap是C STL中的关联容器,它们存储的是键值对(key-value pairs),并且会根据键(key)自动排序。两者的主要区别在于: map不允许重复的键multimap允许重复的键 本文将详细解析示例代码中涉及的map操作,包括赋值、排…...
EmuEdit
EmuEdit详解:统一多任务图像编辑的扩展性范式 引言:图像编辑的困境 近年来,扩散模型(Diffusion Models)在图像合成和编辑方面取得了巨大进展,如 Prompt-to-Prompt (P2P)、InstructPix2Pix、DiffEdit 等方法…...
Linux编译rpm包与deb包
注意: 本文内容于 2025-05-14 23:55:53 创建,可能不会在此平台上进行更新。如果您希望查看最新版本或更多相关内容,请访问原文地址:编译rpm包与deb包。感谢您的关注与支持! 近期在通过源码编译安装一些软件包时&#…...
GitHub 趋势日报 (2025年05月17日)
本日报由 TrendForge 系统生成 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日整体趋势 Top 10 排名项目名称项目描述今日获星总星数语言1TapXWorld/ChinaTextbookPDF教材。⭐ 2471⭐ 22302Roff2public-apis/public-a…...
[创业之路-362]:企业战略管理案例分析-3-战略制定-华为使命、愿景、价值观的演变过程
一、华为使命、愿景、价值观的演变过程 1、创业初期(1987 - 1994 年):生存导向,文化萌芽 使命愿景雏形:1994年华为提出“10年之后,世界通信行业三分天下,华为将占一份”的宏伟梦想,…...
Android 性能优化入门(二)—— 内存优化
1、概述 1.1 Java 对象的生命周期 各状态含义: 创建:分配内存空间并调用构造方法应用:使用中,处于被强引用持有(至少一个)的状态不可见:不被强引用持有,应用程序已经不再使用该对象…...
(5)python爬虫--BeautifulSoup(bs4)
文章目录 [TOC](文章目录) 前言一、安装bs4二、bs4的基础使用2.1 创建soup对象2.2 根据标签名查找节点2.3 根据函数来查找节点1. find函数2. find_all函数3. select函数 三、使用bs4获取节点信息3.1 获取节点内容3.2 获取节点的属性3.3 获取节点的属性值 四、测试练习 总结 前言…...
如何利用DeepSeek提升工作效率
1. 代码开发辅助 1.1 代码生成 根据需求描述生成代码框架 自动补全代码片段 生成单元测试用例 创建项目文档 1.2 代码优化 代码重构建议 性能优化方案 最佳实践推荐 设计模式应用 2. 问题诊断与解决 2.1 错误分析 编译错误解析 运行时错误诊断 内存泄漏检测 性…...
游戏引擎学习第292天:实现蛇
每次VLC 读取OSD 会有bug 修复一下 回顾并计划实现一种漂浮的移动方式,并制作一个贪吃蛇 虽然不完全记得之前具体计划,但感觉是想实现一个小蛇形生物,之前一直没来得及做。我们还打算让熟悉的伙伴能漂浮移动,所以今天会继续进行一…...
菱形继承原理
在C中,菱形继承的内存模型会因是否使用虚继承产生本质差异。我们通过具体示例说明两种场景的区别: 一、普通菱形继承的内存模型 class A { int a; }; class B : public A { int b; }; class C : public A { int c; }; class D : public B, public C { i…...
C++编程起步项目
员工信息管理系统 需求 Employee.h #pragma once#include<iostream> #include<string>using namespace std;class Employee { public:int id; // 编号string name; // 姓名string position; // 岗位int deptId; // 部门编号Employee();Employee(int id, string n…...
c++编写中遇见的错误
目录 一.获取动态数组的长度二.编译错误三、内存泄露 一.获取动态数组的长度 首先想到获取数组的长度的代码是: sizeof(arr) / sizeof(arr[0]);但是当将其使用到动态数组上时就会产生错误; int* help new int[3];for (int i 0; i < 3; i) {help[…...
股票数据源对接技术指南:印度尼西亚、印度、韩国
一、多国数据对接全景图 1. 核心数据领域对比 国家金融市场数据源宏观经济指标特色数据资源印度NSE/BSE实时行情RBI经济统计库UPI支付数据/GST税务记录印尼IDX交易所数据流BPS官方统计棕榈油产业数据/群岛物流信息韩国KRX综合指数KOSTAT国家统计K-POP消费趋势/半导体出口数据…...
常见面试题:Webpack的构建流程简单说一下。
文章目录 前言一、Webpack 的核心使命:模块化打包二、Webpack 构建流程详解三、构建流程的可视化演示项目结构构建流程图 四、构建流程中的关键技术点1. 依赖图的构建与优化2. 哈希与缓存策略3. 开发环境优化 五、简易版概括构建流程 总结 前言 在前端工程化中&…...
Elasticsearch基础篇-java程序通过RestClient操作es
目录 1.引入 2 初始化RestClient 1)引入es的RestHighLevelClient依赖: 2)因为SpringBoot默认的ES版本是7.17.10,所以我们需要覆盖默认的ES版本: 3)初始化RestHighLevelClient: 4)…...
SuperYOLO:多模态遥感图像中的超分辨率辅助目标检测之论文阅读
摘要 在遥感影像(RSI)中,准确且及时地检测包含数十像素的多尺度小目标仍具有挑战性。现有大多数方法主要通过设计复杂的深度神经网络来学习目标与背景的区分特征,常导致计算量过大。本文提出一种兼顾检测精度与计算代价的快速准确…...
k6学习k6学习k6学习k6学习k6学习k6学习
1.安装go 2.安装 xk6 (k6 扩展构建工具): go install go.k6.io/xk6/cmd/xk6latest3.构建自定义 k6 二进制文件(集成 faker 扩展): xk6 build --with github.com/gkarthiks/xk6-fakerlatest构建报错处理(代码拉取失败)࿱…...
ubuntu 安装mq
一、安装依赖 编译 Erlang 需要以下依赖库和工具: sudo apt update sudo apt install -y build-essential autoconf libncurses5-dev libssl-dev m4 unixodbc-dev libwxgtk3.0-gtk3-dev libgl1-mesa-dev libglu1-mesa-dev 二、解压源码包 tar -xzvf otp_src_21.…...
优化 Spring Boot 应用启动性能的实践指南
1. 引言 Spring Boot 以其“开箱即用”的特性深受开发者喜爱,但随着项目复杂度的增加,应用的启动时间也可能会变得较长。对于云原生、Serverless 等场景而言,快速启动是一个非常关键的指标。 2. 分析启动过程 2.1 启动阶段概述 Spring Boot 的启动流程主要包括以下几个阶…...
ubuntu18.04编译qt5.14.2源码
ubuntu18.04编译qt5.14.2源码 文章目录 ubuntu18.04编译qt5.14.2源码[toc]1 前言2 参考文档3 下载源码3.1 方法13.2 方法23.3 方法3 4 ubuntu编译qt源码4.1 环境准备4.2 设置交换分区大小4.3 编译源码4.4 添加环境变量4.5 验证编译结果4.6 编译帮助文档(qch…...
leetcodehot100刷题——排序算法总结
排序算法总结 冒泡排序介绍步骤(以升序排序为例)算法实现复杂度分析时间复杂度空间复杂度 是否为稳定排序:是稳定排序的定义 选择排序介绍步骤(以升序排序为例)算法实现复杂度分析时间复杂度空间复杂度 是否为稳定排序…...
多用途商务,电子产品发布,科技架构,智能手表交互等发布PPT模版20套一组分享
产品发布类PPT模版20套一组:产品发布PPT模版https://pan.quark.cn/s/25c8517b0be3 第一套PPT模版是一个总结用的PPT封面,背景浅灰色,有绿色叶片和花朵装饰,深绿色标题,多个适用场景和占位符。突出其清新自然的设计和商…...
2025年- H29-Lc137- 19.删除链表的倒数第N个节点(快慢指针)---java版
1.题目描述 2.思路 快慢指针都在虚拟头节点,然后让快指针先走n1步,接下来,快慢指针以前移动,直到快指针指向null,慢指针指向被删节点的前一个节点。 3.代码实现 方法一:不带测试用例 /*** Definition …...
新电脑软件配置二:安装python,git, pycharm
安装python 地址 https://www.python.org/downloads/ 不是很懂为什么这么多版本 安装windows64位的 这里我是凭自己感觉装的了 然后cmd输入命令没有生效,先重启下? 重启之后再次验证 环境是成功的 之前是输入的python -version 命令输入错误 安装pyc…...
医学影像开发的开源生态与技术实践:从DCMTK到DICOMweb的全面探索
🧑 博主简介:CSDN博客专家、CSDN平台优质创作者,高级开发工程师,数学专业,10年以上C/C++, C#, Java等多种编程语言开发经验,拥有高级工程师证书;擅长C/C++、C#等开发语言,熟悉Java常用开发技术,能熟练应用常用数据库SQL server,Oracle,mysql,postgresql等进行开发应用…...
【HarmonyOS 5开发入门】DevEco Studio安装配置完全指南
⭐本期内容:【HarmonyOS4+NEXT】Button组件核心特性 🏆系列专栏:鸿蒙HarmonyOS:探索未来智能生态新纪元 文章目录 前言下载开发工具安装开发工具配置开发环境新建项目项目结构概述运行项目Preview预览模拟器运行 报错处…...