西安网站推广,东营建设信息网站,廊坊网站建设策划,木马网站链接有什么废话不多说#xff0c;喊一句号子鼓励自己#xff1a;程序员永不失业#xff0c;程序员走向架构#xff01;本篇Blog的主题是【字符串转换】#xff0c;使用【字符串】这个基本的数据结构来实现#xff0c;这个高频题的站点是#xff1a;CodeTop#xff0c;筛选条件为喊一句号子鼓励自己程序员永不失业程序员走向架构本篇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]]” 中的 acur_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;StackInteger stack_multi new StackInteger();StackString stack_res new StackString();// 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]]]。
