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

算法竞赛（Python）-堆栈

news 来源：原创 2025/7/4 20:16:03

文章目录

一基础知识
二题目
- 有效的括号
- 字符串解码

一基础知识

堆栈（Stack）：简称为栈。一种线性表数据结构，是一种只允许在表的一端进行插入和删除操作的线性表。
我们把栈中允许插入和删除的一端称为「栈顶（top）」；另一端则称为「栈底（bottom）」。当表中没有任何数据元素时，称之为「空栈」。
堆栈有两种基本操作：「插入操作」和「删除操作」。
栈的插入操作又称为「入栈」或者「进栈」。
栈的删除操作又称为「出栈」或者「退栈」。

简单来说，栈是一种「后进先出（Last In First Out）」的线性表，简称为「LIFO 结构」。
我们可以从两个方面来解释一下栈的定义：
第一个方面是「线性表」。
栈首先是一个线性表，栈中元素具有前驱后继的线性关系。栈中元素按照a1,a2,…,an的次序依次进栈。栈顶元素为an。
第二个方面是「后进先出原则」。
根据堆栈的定义，每次删除的总是堆栈中当前的栈顶元素，即最后进入堆栈的元素。而在进栈时，最先进入堆栈的元素一定在栈底，最后进入堆栈的元素一定在栈顶。也就是说，元素进入堆栈或者退出退栈是按照「后进先出（Last In First Out）」的原则进行的。

二题目

有效的括号

描述：给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 ss。
要求：判断字符串 ss 是否有效（即括号是否匹配）。
说明：
有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。
示例：
输入：s = “()”
输出：True
输入：s = “()[]{}”
输出：True

思路 1：栈
括号匹配是「栈」的经典应用。我们可以用栈来解决这道题。具体做法如下：
1、先判断一下字符串的长度是否为偶数。因为括号是成对出现的，所以字符串的长度应为偶数，可以直接判断长度为奇数的字符串不匹配。如果字符串长度为奇数，则说明字符串s中的括号不匹配，直接返回False。
2、使用栈stack来保存未匹配的左括号。然后依次遍历字符串s中的每一个字符。
如果遍历到左括号时，将其入栈。
如果遍历到右括号时，先看栈顶元素是否是与当前右括号相同类型的左括号。
如果是与当前右括号相同类型的左括号，则令其出栈，继续向前遍历。
如果不是与当前右括号相同类型的左括号，则说明字符串s中的括号不匹配，直接返回False。
3、遍历完，还要再判断一下栈是否为空。
如果栈为空，则说明字符串s中的括号匹配，返回True。
如果栈不为空，则说明字符串s中的括号不匹配，返回False。

class Solution:def isValid(self, s: str) -> bool:if len(s) % 2 == 1:return Falsestack = list()for ch in s:if ch == '(' or ch == '[' or ch == '{':stack.append(ch)elif ch == ')':if len(stack) !=0 and stack[-1] == '(':stack.pop()else:return Falseelif ch == ']':if len(stack) !=0 and stack[-1] == '[':stack.pop()else:return Falseelif ch == '}':if len(stack) !=0 and stack[-1] == '{':stack.pop()else:return Falseif len(stack) == 0:return Trueelse:return False

字符串解码

描述：给定一个经过编码的字符串 s。
要求：返回 s 经过解码之后的字符串。
说明：
编码规则：k[encoded_string]。encoded_string 为字符串，k 为整数。表示字符串 encoded_string 重复 k 次。
1≤s.length≤301≤s.length≤30。
s 由小写英文字母、数字和方括号 [] 组成。
s 保证是一个有效的输入。
s 中所有整数的取值范围为 [1,300][1,300]。

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

输入：s = “3[a2[c]]”
输出：“accaccacc”

思路 1：栈
1.使用两个栈stack1、stack2。stack1用来保存左括号前已经解码的字符串，stack2用来存储左括号前的数字。
2.用res存储待解码的字符串、num存储当前数字。
3.遍历字符串。
1.如果遇到数字，则累加数字到num。
2.如果遇到左括号，将当前待解码字符串入栈 stack1，当前数字入栈 stack2，然后将 res、nums 清空。
3.如果遇到右括号，则从stack1的取出待解码字符串res，从stack2中取出当前数字num，将其解码拼合成字符串赋值给 res。
4.如果遇到其他情况（遇到字母），则将当前字母加入res中。
4、遍历完输出解码之后的字符串res。

class Solution:def decodeString(self, s: str) -> str:stack1 = []stack2 = []num = 0res = ""for ch in s:if ch.isdigit():num = num * 10 + int(ch)elif ch == '[':stack1.append(res)stack2.append(num)res = ""num = 0elif ch == ']':cur_res = stack1.pop()cur_num = stack2.pop()res = cur_res + res * cur_numelse:res += chreturn res

文章目录

一 基础知识

二 题目

有效的括号

字符串解码

相关文章：

一基础知识

二题目