做网站的价位,怎么推广自己的网站,网络推广培训职业学校,网站的建设意义其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
2.1 什么情况会用到栈
2.2 方法一#xff1a;辅助栈法
三、代码
3.1 方法一#xff1a;辅助栈法
四… 其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
2.1 什么情况会用到栈
2.2 方法一辅助栈法
三、代码
3.1 方法一辅助栈法
四、复杂度分析
4.1 方法一辅助栈法 前言
这是力扣的 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 30s 由小写英文字母、数字和方括号 [] 组成s 保证是一个 有效 的输入。s 中所有整数的取值范围为 [1, 300] 二、题解 2.1 什么情况会用到栈
栈是一种数据结构其特点是后进先出Last In First OutLIFO。在算法中栈在很多情况下是非常有用的下面是一些常见的情况
括号匹配当你有一个包含括号的字符串并且你想要检查这个字符串中的括号是否匹配你可以使用栈。从左到右扫描字符串如果遇到左括号如“(”“{”或“[”则将其压入栈。如果遇到右括号则从栈顶弹出一个元素并检查它们是否匹配。如果它们不匹配那么这个字符串就不是有效的。深度优先搜索DFS在图的遍历中栈经常被用于实现深度优先搜索。首先将起始节点压入栈。然后当栈不为空时弹出栈顶元素并访问它。对于每个刚刚访问过的节点将其未被访问过的邻居节点压入栈。函数调用在计算机程序的执行中函数调用通常使用栈来管理。当一个函数被调用时它的参数和局部变量被压入栈。当函数执行结束时这些数据从栈中弹出。文本编辑器中的撤销/重做功能许多文本编辑器使用撤销/重做功能来允许用户撤销他们最近所做的更改。这些功能通常使用一个操作栈每个操作例如插入或删除文本都被压入栈。用户可以多次撤销每次撤销都从栈中弹出并反转一个操作。解析语法在编译原理中栈被广泛用于解析语法。例如在解析一个算术表达式时你可以使用栈来保持追踪括号和操作符的优先级。
这只是栈在算法中的一些应用实际上还有很多其他的应用场景。
2.2 方法一辅助栈法 本题难点在于括号内嵌套括号需要从内向外生成与拼接字符串这与栈的先入后出特性对应。 思路与算法 本题用到两个辅助栈一个存次数一个存字母 构建辅助栈 stack 遍历字符串 s 中每个字符 c
当 c 为数字时将数字字符转化为数字 cnt 用于后续倍数计算当 c 为字母时在 sb 尾部添加 c当 c 为 [ 时将当前 cnt 和 sb 入栈并分别置空置 0
记录此 [ 前的临时结果 sb 至栈用于发现对应 ] 后的拼接操作
记录此 [ 前的倍数 cnt 至栈用于发现对应 ] 后获取 cnt × [...] 字符串。
进入到新 [ 后sb 和 cnt 重新记录。
当 c 为 ] 时stack 出栈拼接字符串 sb last_sb cntNow * sb其中:
last_sb 是上个 [ 到当前 [ 的字符串例如 3[a2[c]] 中的 acntNow 是当前 [ 到 ] 内字符串的重复倍数例如 3[a2[c]] 中的 2。
返回字符串 sb 。 三、代码
3.1 方法一辅助栈法
Java版本
class Solution {public String decodeString(String s) {StringBuilder sb new StringBuilder();int cnt 0;LinkedListInteger n new LinkedList();LinkedListString str new LinkedList();for (char c : s.toCharArray()) {if (c [) {n.addLast(cnt);str.addLast(sb.toString());cnt 0;sb new StringBuilder();} else if (c ]) {StringBuilder tmp new StringBuilder();Integer cntNow n.removeLast();for (int i 0; i cntNow; i) tmp.append(sb);sb new StringBuilder(str.removeLast() tmp);} else if (c 0 c 9) {cnt cnt * 10 Integer.parseInt(String.valueOf(c));} else {sb.append(c);}}return sb.toString();}
}
C版本
class Solution {
public:std::string decodeString(std::string s) {std::stackint counts;std::stackstd::string strings;std::string result;int count 0;for (char c : s) {if (c [) {counts.push(count);count 0;strings.push(result);result ;} else if (c ]) {std::string temp result;result strings.top();strings.pop();int repeatCount counts.top();counts.pop();for (int i 0; i repeatCount; i) {result temp;}} else if (std::isdigit(c)) {count count * 10 (c - 0);} else {result c;}}return result;}
};Python版本
class Solution:def decodeString(self, s: str) - str:stack []for char in s:if char ]:tmp while stack[-1] ! [:tmp stack.pop() tmpstack.pop() # remove [k while stack and stack[-1].isdigit():k stack.pop() kstack.append(tmp * int(k))else:stack.append(char)return .join(stack)Go版本
package mainimport (fmtstrconvunicode
)func decodeString(s string) string {stack : []string{}for _, char : range s {if char ] {tmp : for stack[len(stack)-1] ! [ {lastIdx : len(stack) - 1tmp stack[lastIdx] tmpstack stack[:lastIdx]}stack stack[:len(stack)-1] // remove [k : for len(stack) 0 unicode.IsDigit(rune(stack[len(stack)-1][0])) {lastIdx : len(stack) - 1k stack[lastIdx] kstack stack[:lastIdx]}n, _ : strconv.Atoi(k)newStr : for i : 0; i n; i {newStr tmp}stack append(stack, newStr)} else {stack append(stack, string(char))}}return fmt.Sprint(stack)
}func main() {s : 3[a]2[bc]result : decodeString(s)fmt.Println(result)
}四、复杂度分析
4.1 方法一辅助栈法
时间复杂度 O(N)一次遍历 s空间复杂度 O(N)辅助栈在极端情况下需要线性空间例如 2[2[2[a]]]。
