漯河网站推广公司,济南专业做网站公司,lamp网站怎么建设,浙江省建设信息港查1.有效的括号
问题#xff1a;
给定一个只包括 (#xff0c;)#xff0c;{#xff0c;}#xff0c;[#xff0c;] 的字符串 s #xff0c;判断字符串是否有效。
有效字符串需满足#xff1a;
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右…1.有效的括号
问题
给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。
有效字符串需满足
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。
方法栈左入右出注意栈空和栈有余
# 栈左括号入栈右括号出栈注意栈空和栈有余的情况
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))
