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

【数据结构-字符串 三】【字符串转换】字符串解码

废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是【字符串转换】,使用【字符串】这个基本的数据结构来实现,这个高频题的站点是:CodeTop,筛选条件为:目标公司+最近一年+出现频率排序,由高到低的去牛客TOP101去找,只有两个地方都出现过才做这道题(CodeTop本身汇聚了LeetCode的来源),确保刷的题都是高频要面试考的题。
在这里插入图片描述

明确目标题后,附上题目链接,后期可以依据解题思路反复快速练习,题目按照题干的基本数据结构分类,且每个分类的第一篇必定是对基础数据结构的介绍

字符串解码【MID】

字符串和栈结合的一道题

题干

在这里插入图片描述

解题思路

原题解地址,本题难点在于括号内嵌套括号,需要从内向外生成与拼接字符串,这与栈的先入后出特性对应

算法流程:构建辅助栈 stack, 遍历字符串 s 中每个字符 c;

  • 当 c 为数字时,将数字字符转化为数字 multi,用于后续倍数计算;
  • 当 c 为字母时,在 res 尾部添加 c;
  • 当 c 为 [ 时,将当前 multi 和 res 入栈,并分别置空置 0:记录此 [ 前的临时结果 res 至栈,用于发现对应 ] 后的拼接操作;记录此 [ 前的倍数 multi 至栈,用于发现对应 ] 后,获取 multi × […] 字符串。进入到新 [ 后,res 和 multi 重新记录。
  • 当 c 为 ] 时,stack 出栈,拼接字符串 res = last_res + cur_multi * res,其中:last_res是上个 [ 到当前 [ 的字符串,例如 “3[a2[c]]” 中的 a;cur_multi是当前 [ 到 ] 内字符串的重复倍数,例如 “3[a2[c]]” 中的 2。

返回字符串 res。

代码实现

给出代码实现基本档案

基本数据结构字符串
辅助数据结构
算法迭代
技巧

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param s string字符串* @param n int整型* @return string字符串*/public String decodeString(String s) {// 1 定义结果集、倍数、乘积栈和临时结果栈,以 3[a2[c]]为例StringBuilder res = new StringBuilder();int multi = 0;Stack<Integer> stack_multi = new Stack<Integer>();Stack<String> stack_res = new Stack<String>();// 2 遍历字符,依据不同的情况进行判断,字符串中只有4种字符,对应4种情况for (Character c : s.toCharArray()) {if (c == '[') {// 2-1 如果是左括号,则临时存储倍数和临时结果集用于后续拼接。并重置倍数和临时结果stack_multi.push(multi);stack_res.push(res.toString());multi = 0;res = new StringBuilder();} else if (c == ']') {// 2-2 如果是右括号StringBuilder tmp = new StringBuilder();// 弹出上个倍数并计算当前结果集:计算结果为:ccint cur_multi = stack_multi.pop();for (int i = 0; i < cur_multi; i++) {tmp.append(res);};// 与上个临时结果合并,计算结果为:accres = new StringBuilder(stack_res.pop() + tmp);} else if (c >= '0' && c <= '9') {// 2-3 如果是倍数,这里*10是因为要考虑重复次数大于10的情况,例如11multi = multi * 10 + Integer.parseInt(c + "");} else {// 2-4 如果是字符,直接放入结果集res.append(c);}}return res.toString();}
}

复杂度分析

时间复杂度 O(N),一次遍历 s;
空间复杂度 O(N),辅助栈在极端情况下需要线性空间,例如 2[2[2[a]]]。

相关文章:

【数据结构-字符串 三】【字符串转换】字符串解码

废话不多说&#xff0c;喊一句号子鼓励自己&#xff1a;程序员永不失业&#xff0c;程序员走向架构&#xff01;本篇Blog的主题是【字符串转换】&#xff0c;使用【字符串】这个基本的数据结构来实现&#xff0c;这个高频题的站点是&#xff1a;CodeTop&#xff0c;筛选条件为&…...

LabVIEW中不同颜色连线的含义

LabVIEW中不同颜色连线的含义 LabVIEW中的连线具有不同的颜色&#xff0c;样式和宽度。每个都代表了什么&#xff1f; 下表列出了常见的连线类型&#xff1a; 相关信息 请注意&#xff0c;类的连线颜色是可更改的。该表显示其默认外观。 连线用于在程序框图各对象间传递数据…...

如何才能在Ubuntu系统部署RabbitMQ服务器并公网访问

在Ubuntu系统上部署RabbitMQ服务器并公网访问&#xff0c;可以按照以下步骤进行&#xff1a; 安装RabbitMQ服务器&#xff1a; 在终端中输入以下命令安装RabbitMQ服务器&#xff1a; sudo apt-get update sudo apt-get install rabbitmq-server启动RabbitMQ服务器&#xff1a; …...

PCL点云处理之使用变换矩阵对点云去中心化(二百零七)

PCL点云处理之使用变换矩阵对点云去中心化(二百零七) 一、算法介绍二、算法实现1.代码2.效果三、总结一、算法介绍 点云去中心化是点云处理中的一种常见操作,借助PCL可以很快实现这一处理,具体处理步骤如下 1、计算点云中心,这个有现成函数直接调用 2、构建偏移变换矩阵,…...

ubuntu编译安装并测试opencv

下载opencv工程 git clone https://github.com/opencv/opencv.git git -C opencv checkout 4.x构建并编译opencv 在build目录下使用cmake构建生成makefile cd opencv mkdir -p build && cd build cmake -D CMAKE_BUILD_TYPERelease -D OPENCV_GENERATE_PKGCONFIGON …...

Vue3最佳实践 第七章 TypeScript 上

​ 在浏览网上的JavaScript相关文档时&#xff0c;大家可能已经注意到了一个趋势&#xff1a;越来越多的项目和教程都采用了TypeScript编写代码。对于那些没有TypeScript经验的人来说&#xff0c;阅读这些由TypeScript编写的代码可能会感到有些压力。   ​Vue3的出现无疑加剧…...

【maven私库nexus开机自启动】

linux设置nexus开机自启动_linux centos maven私服nexus安装搭建并设置开机启动 linux centos maven私服nexus安装搭建并设置开机启动&#xff0c;这里是用添加服务的方式开机启动nexus。 1.先要下载jdk并安装&#xff0c;配置java环境变量&#xff0c;直接去oracle下载把&am…...

ctfshow-web5(md5弱比较)

打开题目链接是html和php代码 html没啥有用信息&#xff0c;这里审一下php代码 &#xff1a; 要求使用get方式传入两个参数 v1&#xff0c;v2 ctype_alpha()函数&#xff1a;用于检查给定的字符串是否仅包含字母&#xff1b; is_numeric()函数&#xff1a;检测字符串是否只由…...

【GIT版本控制】--子模块

一、创建与管理子模块 Git 子模块允许你在一个 Git 仓库中引用另一个仓库。这对于在一个项目中使用其他项目的特定版本非常有用。以下是创建和管理 Git 子模块的基本步骤&#xff1a; 添加子模块&#xff1a;在父仓库的根目录中&#xff0c;使用以下命令添加子模块&#xff1…...

享元模式 基于享元模式的对象池设计与开发应用(设计模式与开发实践 P12)

文章目录 反例应用对象池对象池应用 享元模式&#xff08;flyweight&#xff09;是一种进行性能优化的模式&#xff0c;通过共享技术来支持大量细粒度的对象 如果系统中创建了大量相似的对象&#xff0c;我们就可以通过享元模式节省内存 反例 服装厂生产了一堆衣服&#xff…...

postman测试文件上传接口教程

postman是一个很好的接口测试软件&#xff0c;有时候接口是Get请求方式的&#xff0c;肯定在浏览器都可以测了&#xff0c;不过对于比较规范的RestFul接口&#xff0c;限定了只能post请求的&#xff0c;那你只能通过工具来测了&#xff0c;浏览器只能支持get请求的接口&#xf…...

【bug日记】spring项目使用配置类和测试类操作数据库

最近学校课程要求使用spring操作数据库&#xff0c;时间有点久了&#xff0c;操作都不太熟悉了&#xff0c;遇到了很多坑&#xff0c;特此记录一下。 导入依赖 <!-- Spring Framework --> <dependency><groupId>org.springframework</groupId><ar…...

Django之主键外键详解

在ORM操作处了解的文章中&#xff0c;我们已经初步接触到了主键与外键的字段定义&#xff0c;那么本文以详细介绍主键外键的使用方法等 1.外键 在Django中&#xff0c;外键是一种关系字段&#xff0c;用于建立不同模型之间的关联关系。外键字段允许一个模型引用另一个模型的主…...

HDLbits: ece241 2014 q7b

题目要求用10进制的BCD计数器来构造1000计数&#xff0c;其实也是将1000hz的时钟信号改造成1hz&#xff0c;我们首先计算出10的三次方等于1000&#xff0c;需要三个10进制的计数器&#xff0c;去计999的中高低位。 最低位的计数器一直在对时钟信号计数&#xff0c;因此enable1…...

C++多态的理解

C多态的理解 1 C多态的概念2 C多态的类型3 虚函数实现多态案例分析3.1 非虚函数成员函数调用的案例3.1.1 测试代码3.1.2 测试运行结果 3.2 虚函数成员函数调用案例3.2.1 虚函数实现测试代码3.2.2 测试运行结果 3.3 基类析构函数的实现3.3.1 析构函数定义和实现案例3.3.2 基类析…...

关于深拷贝和浅拷贝你需要了解的内容

深拷贝&#xff08;Deep Copy&#xff09;和浅拷贝&#xff08;Shallow Copy&#xff09;是在复制对象或数据结构时使用的两种不同的策略&#xff0c;它们的主要区别在于复制后新旧对象之间的关系以及对嵌套对象的处理方式。 浅拷贝&#xff1a; 浅拷贝创建一个新对象&#xff…...

Visual Studio自定义模板参数、备注

模板路径&#xff1a; VS2022 x64&#xff1a;C:\Program Files\Microsoft Visual Studio\2022\Enterprise\Common7\IDE\ItemTemplatesVS2022 x86&#xff1a;C:\Program Files (x86)\Microsoft Visual Studio\2022\Enterprise\Common7\IDE\ItemTemplates 一、声明和启用模板…...

机器学习-数值特征

离散值处理 import pandas as pd import numpy as npvg_df pd.read_csv(datasets/vgsales.csv, encoding "ISO-8859-1") vg_df[[Name, Platform, Year, Genre, Publisher]].iloc[1:7]NamePlatformYearGenrePublisher1Super Mario Bros.NES1985.0PlatformNintendo2…...

Rocky(centos)安装nginx并设置开机自启

一、安装nginx 1、安装依赖 yum install -y gcc-c pcre pcre-devel zlib zlib-devel openssl openssl-devel 2、去官网下载最新的稳定版nginx nginx: downloadhttp://nginx.org/en/download.html 3、将下载后的nginx上传至/usr/local下 或者执行 #2023-10-8更新 cd /usr/…...

Android约束布局ConstraintLayout的Guideline,CardView

Android约束布局ConstraintLayout的Guideline&#xff0c;CardView <?xml version"1.0" encoding"utf-8"?> <androidx.constraintlayout.widget.ConstraintLayout xmlns:android"http://schemas.android.com/apk/res/android"xmlns:a…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...