免费网站收录网站推广微信搜索seo优化

1.有效的括号

问题：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

方法：栈（左入右出，注意栈空和栈有余）

# 栈（左括号入栈，右括号出栈，注意栈空和栈有余的情况）
def is_val(s):hash = {'(':')', '[':']', '{':'}'}# if not s:#     return Truestack = []index = 0while index < len(s):# 入栈情况（左括号）if s[index] in hash.keys():stack.append(s[index])# 出栈情况（右括号）elif s[index] in hash.values():# 空栈情况（会报错）if not stack:return False# 出栈 对比elif hash[stack.pop()] != s[index]:return Falseindex += 1# 栈剩余if stack:return Falsereturn True
print(is_val("([])"))

2.最小栈

问题：

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

方法：

# 注意：最小值要用栈来保存（否则更新不及时）
class MinStack:def __init__(self, nums=[]):self.nums = nums# self.min = float('inf')               # 注意：！！！ 这里需要用栈来保存最小值：如果用值来保存，元素出栈之后，最小值可能更新不及时 ！！！self.min_stack = []def push(self, val):self.nums.append(val)if not self.min_stack or self.min_stack[-1] >= val:self.min_stack.append(val)def pop(self):pop_val = self.nums.pop()if pop_val == self.min_stack[-1]:       # ！！！更新最小值！！！self.min_stack.pop()return pop_valdef top(self):if self.nums:return self.nums[-1]return Nonedef getMin(self):if self.min_stack:return self.min_stack[-1]else:return Nonem_s = MinStack()
print(m_s.push(-2))
print(m_s.push(0))
print(m_s.push(-3))
print(m_s.getMin())
print(m_s.pop())
print(m_s.top())
print(m_s.getMin())

注意，这里最小值要用栈来保存，如果用值保存最小值，有元素弹出之后，会导致更新不及时。

3.字符串解码

问题：

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

方法：栈保存局部数字和子串

# 栈保存局部数字和子串
def DecodeString(s):cur_num, cur_s = 0, ''local_s = []for i in range(len(s)):if s[i].isdigit():                              # 判断数字cur_num = 10 * cur_num + int(s[i])elif s[i] == '[':local_s.append([cur_num, cur_s])            # 入栈数字和之前的子串cur_s, cur_num = '', 0elif s[i] == ']':local_num, pre_s = local_s.pop()cur_s = pre_s + local_num * cur_s           # 右侧的cur_s是继'['之后累加的子串，左侧的pre_s是之前存下的子串else:cur_s += s[i]                               # 累加（包含总字符串和局部子串）return cur_sprint(DecodeString("2[abc]3[cd]ef"))