微信网站有什么作用,wordpress首页文章随机显示,工业设计展会2023,wordpress双语LeetCode Hot 100 是最常被考察的题目集合#xff0c;涵盖了面试中常见的算法和数据结构问题。刷 Hot100可以让你在有限的时间内集中精力解决最常考的问题。鼓励大家不仅要写出代码#xff0c;最好理解问题的本质、优化解法和复杂度分析。遇到问题要多交流多求问多分享#… LeetCode Hot 100 是最常被考察的题目集合涵盖了面试中常见的算法和数据结构问题。刷 Hot100可以让你在有限的时间内集中精力解决最常考的问题。鼓励大家不仅要写出代码最好理解问题的本质、优化解法和复杂度分析。遇到问题要多交流多求问多分享“多折腾”能加深印象。欢迎留言交流~ Hot100 刷题计划 Day04 Day4 栈专题 Day4 栈专题
4天为一个周期学习3天刷题1天回顾。今天就是第4天了我们复习之前带着刷下较简单的数据结构——栈。
20. 有效的括号
给定一个只包括 ‘(’‘)’‘{’‘}’‘[’‘]’ 的字符串 s 判断字符串是否有效。
有效字符串需满足
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。
思路
栈是先入后出匹配括号也是找最后相对应的。只有3种括号在看到左括号压栈的时候直接使用待匹配的右括号。只需要找到后续与栈顶元素相同的右括号出栈。最后栈为空则有效。
class Solution:def isValid(self, s: str) - bool:stack []for i in s:if i (:stack.append()) # 将待匹配的括号分别压入栈elif i [:stack.append(])elif i {:stack.append(})elif not stack or i ! stack[-1]: # 如果还有括号未匹配栈为空或者不匹配return Falseelse:stack.pop() # 匹配成功栈顶元素出栈return True if not stack else False # 栈为空则有效反之无效155. 最小栈
设计一个支持 push pop top 操作并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop()删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int getMin() 获取堆栈中的最小元素。
pop、top 和 getMin 操作总是在 非空栈 上调用。
思路 要快速找栈中的最小值。栈先进后出可以在每个元素位置维护之前元素最小值栈顶标记则为栈最小值。
class MinStack:def __init__(self):self.stack [(0, inf)] # 除了栈元素还维护一个最小值def push(self, val: int) - None:self.stack.append((val, min(self.stack[-1][1], val)))def pop(self) - None:self.stack.pop()def top(self) - int:return self.stack[-1][0]def getMin(self) - int:return self.stack[-1][1]# Your MinStack object will be instantiated and called as such:
# obj MinStack()
# obj.push(val)
# obj.pop()
# param_3 obj.top()
# param_4 obj.getMin()394. 字符串解码
给定一个经过编码的字符串返回它解码后的字符串。
编码规则为: k[encoded_string]表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的输入字符串中没有额外的空格且输入的方括号总是符合格式要求的。
此外你可以认为原始数据不包含数字所有的数字只表示重复的次数 k 例如不会出现像 3a 或 2[4] 的输入。
思路 栈匹配的问题核心是遇到“ [ ”入栈遇到“ ] ”出栈。记录下的res需要匹配数字所以入栈需要记录下数字。还需要之前的字符串才能得到结果相当于递归的更深一层返回值。
class Solution:def decodeString(self, s: str) - str:res # 当前解码结果multi 0 # 当前数字stack [] # 栈用于存储 [数字, 之前的解码结果]for char in s:if char.isdigit(): # 如果是数字字符multi multi * 10 int(char) # 计算数字elif char [: # 遇到 [将当前数字和解码结果入栈stack.append([multi, res])multi, res 0, # 重置数字和解码结果elif char ]: # 遇到 ]出栈并更新解码结果cur_multi, last_res stack.pop()res last_res cur_multi * res # 拼接字符串更新解码结果(从最后一个右括号开始res开始找栈)else: # 普通字符直接拼接到解码结果res charreturn res739. 每日温度
给定一个整数数组 temperatures 表示每天的温度返回一个数组 answer 其中 answer[i] 是指对于第 i 天下一个更高温度出现在几天后。如果气温在这之后都不会升高请在该位置用 0 来代替。
思路 使用一个栈记录目前待匹配元素遍历数组如果遇到大于栈顶元素的值就持续对比更新ans.
class Solution:def dailyTemperatures(self, temperatures: List[int]) - List[int]:stack [0] # 使用单调栈记录未匹配找到更大值的元素ans [0] * len(temperatures) # 所有位置初始化为0for i in range(1, len(temperatures)):# 如果当前元素比栈顶元素要大匹配到就更新ans并弹出栈中已匹配元素继续对比while stack and temperatures[i] temperatures[stack[-1]]:ans[stack[-1]] i - stack[-1]stack.pop()# 所有元素都要入栈往后匹配更大值stack.append(i)return ans
