Day5LeetCode 150、逆波兰表达式求值中等√根据 逆波兰表示法求表达式的值。有效的算符包括 、 - 、 * 、 / 。每个运算对象可以是整数也可以是另⼀个逆波兰表达式。注意 两个整数之间的除法只保留整数部分。可以保证给定的逆波兰表达式总是有效的。换句话说表达式总会得出有效数值且不存在除数为 0 的情况。代码classSolution:defevalRPN(self,tokens:List[str])-int:stack[]op{:lambdaa,b:ab,-:lambdaa,b:a-b,*:lambdaa,b:a*b,/:lambdaa,b:int(a/b)}fortokenintokens:iftokeninop:bstack.pop()astack.pop()resop[token](a,b)stack.append(res)else:stack.append(int(token))returnstack[0]1-栈就像桶先放进去的东西压在底下只能拿最上面最后放进去的。两个核心操作append(x)往桶顶部丢一个数字入栈pop()拿走桶最顶上的数字出栈拿完就删掉创建一个空列表stack这里的列表操作可以很好的实现栈。2-运算符字典 lambdalambda关键字代表创建匿名小函数a,b函数的两个参数正好对应我们弹出来的 a、b 两个数字: 后面函数返回的计算结果LeetCode 155、最⼩栈中等√设计⼀个⽀持 push pop top 操作并能在常数时间内检索到最⼩元素的栈。push(x) —— 将元素 x 推⼊栈中。pop() —— 删除栈顶的元素。top() —— 获取栈顶元素。getMin() —— 检索栈中的最⼩元素。代码classMinStack:def__init__(self):# 主栈存所有元素self.stack[]# 辅助栈栈顶永远是当前最小值self.min_stack[]defpush(self,val:int)-None:self.stack.append(val)# 辅助栈为空 或 当前值栈顶最小值入辅助栈ifnotself.min_stackorvalself.min_stack[-1]:self.min_stack.append(val)defpop(self)-None:top_valself.stack.pop()# 如果弹出的是当前最小值辅助栈同步弹出iftop_valself.min_stack[-1]:self.min_stack.pop()deftop(self)-int:returnself.stack[-1]defgetMin(self)-int:returnself.min_stack[-1]思路:push pop top 操作都可以通过栈函数实现关键是在常数时间内检索到最⼩元素的栈。这时候就需要设置一个辅助栈min_stack记录最小值当入栈的是最小值或者等于最小值等于是为了使辅助栈最小值的个数和栈的最小值个数一致最小值出栈一个时辅助栈也出栈一个辅助栈也入栈一个最小值。1-push 入栈方法只有新数字小于等于当前最小值时才压进最小辅助栈。为什么用 而不是 如果有多个相同最小值辅助栈也要存对应个数pop 的时候才能同步删除。例连续压入 2、1、1min_stack 会存 [2,1,1]后面弹出一个 1辅助栈只删一个 1不会直接把最小值删掉2- pop 出栈方法stack.pop出栈并赋值给top_val和min_stack的最后一位比较。3-top () 获取栈顶纯主栈操作和辅助栈无关4-getMin () 获取当前最小值这就是双栈设计的核心优势不用遍历全部元素直接拿辅助栈顶部常数时间得到最小值。LeetCode 1614、括号的最⼤嵌套深度简单√如果字符串满⾜以下条件之⼀则可以称之为有效括号字符串*valid parentheses string可以简写为VPS1、字符串是⼀个空字符串 “” 或者是⼀个不为 “(” 或 “)” 的单字符。2、字符串可以写为 AB A 与 B 字符串连接其中 A 和 B 都是 有效括号字符串 。3、字符串可以写为 (A) 其中 A 是⼀个 有效括号字符串 。4、类似地可以定义任何有效括号字符串 S 的 嵌套深度 depth(S) 5、depth(“”) 06、depth© 0 其中 C 是单个字符的字符串且该字符不是 “(” 或者 “)”7、depth(A B) max(depth(A), depth(B)) 其中 A 和 B 都是 有效括号字符串8、depth(“(” A “)”) 1 depth(A) 其中 A 是⼀个 有效括号字符串例如 “” 、 “()()” 、 “()(()())” 都是 有效括号字符串嵌套深度分别为 0、1、2⽽ “)(” 、 “(()” 都不是有效括号字符串 。给你⼀个 有效括号字符串 s 返回该字符串的 s 嵌套深度 。代码classSolution:defmaxDepth(self,s:str)-int:max_depth0current0forcins:ifc(:current1max_depthmax(max_depth,current)elifc):current-1returnmax_depth思路括号嵌套深度的核心规律遇到左括号(嵌套深度1。遇到右括号)嵌套深度-1。其他字符数字、运算符不影响深度。遍历全程记录出现过的最大深度就是答案。LeetCode 20、有效的括号简单√给定⼀个只包括 ‘(’‘)’‘{’‘}’‘[’‘]’ 的字符串 s 判断字符串是否有效。有效字符串需满⾜1、左括号必须⽤相同类型的右括号闭合。2、左括号必须以正确的顺序闭合。代码classSolution:defisValid(self,s:str)-bool:# 右括号作为key对应匹配的左括号作为valuepairs{):(,}:{,]:[}stack[]forcharins:# 是右括号ifcharinpairs:# 栈空没有左括号匹配 或 栈顶和当前右括号不匹配ifnotstackorstack[-1]!pairs[char]:returnFalse# 匹配成功栈顶弹出stack.pop()# 是左括号直接入栈else:stack.append(char)# 最终栈必须全部清空所有左括号都完成配对returnlen(stack)0思路先定义配对然后遍历s。如果在配对的字典里即chr是右括号则需要比较not stack字符串开头就是右括号还没压入stackstack[-1] ! pairs[char]配对失败以上情况直接return false否则配对成功出栈。如果是左括号则压入。运行结束判断stack是否为空为空则ture。LeetCode 71、简化路径中等√给你⼀个字符串 path 表示指向某⼀⽂件或⽬录的 Unix ⻛格 绝对路径 以 ‘/’ 开头请你将其转化为更加简洁的规范路径。在 Unix ⻛格的⽂件系统中⼀个点 . 表示当前⽬录本身此外两个点 … 表示将⽬录切换到上⼀级指向⽗⽬录两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠即 ‘//’ 都被视为单个斜杠’/’ 。 对于此问题任何其他格式的点例如 ‘…’ 均被视为⽂件/⽬录名称。classSolution:defsimplifyPath(self,path:str)-str:stack[]# 按/分割路径连续/会分割出空字符串后续过滤掉partspath.split(/)forpartinparts:# 空字符串连续/拆分得到和.都直接跳过ifpartorpart.:continue# 返回上一级elifpart..:ifstack:stack.pop()# 正常目录名入栈else:stack.append(part)# 拼接结果根/ 目录用/分隔return//.join(stack)代码思路1-分割路径举例path.split(‘/’)会把/home//foo/切成[‘’, ‘home’, ‘’, ‘foo’, ‘’]后续遍历会把空字符串跳过自动解决多斜杠合并为单个的规则。2-遍历分段的 4 种情况part ‘’连续/产生的空片段直接跳过part ‘.’当前目录不用跳转直接跳过part ‘…’要回到父目录栈非空就弹出栈顶栈空代表已经在根目录不能再往上什么都不做其他情况合法的目录 / 文件名压入栈保留层级3-结果拼接‘/’.join(stack)会把栈里的目录用单个/连接前面再加/保证以根开头如果栈是空join得到空字符串最终返回/完美符合所有格式要求始终以/开头、目录间只有一个/、末尾不会不会包含.和…。Day6LeetCode 224、基本计算器困难给你⼀个字符串表达式 s 请你实现⼀个基本计算器来计算并返回它的值。代码classSolution:defcalculate(self,s:str)-int:stack[]res0# 当前累计结果sign1# 当前数字正负号初始为正i0nlen(s)whilein:cs[i]ifc :i1elifc.isdigit():# 处理多位数num0whileinands[i].isdigit():numnum*10int(s[i])i1ressign*numelifc:sign1i1elifc-:sign-1i1elifc(:# 压入括号前的结果和符号stack.append(res)stack.append(sign)res0sign1i1elifc):# 弹出符号和之前结果合并括号内的值res*stack.pop()resstack.pop()i1returnresLeetCode 2、两数相加中等给你两个 非空 的链表表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的并且每个节点只能存储 一位 数字。请你将两个数相加并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外这两个数都不会以 0 开头代码# Definition for singly-linked list.# class ListNode:# def __init__(self, val0, nextNone):# self.val val# self.next nextclassSolution:defaddTwoNumbers(self,l1:Optional[ListNode],l2:Optional[ListNode])-Optional[ListNode]:# 哑节点方便构建结果链表dummyListNode()curdummy carry0whilel1orl2orcarry:# 取当前位数字链表空则取0v1l1.valifl1else0v2l2.valifl2else0# 计算总和、当前位、新进位totalv1v2carry carrytotal//10cur.nextListNode(total%10)# 指针后移curcur.nextl1l1.nextifl1elseNonel2l2.nextifl2elseNonereturndummy.next思路创建一个新链表记录结果创建一个carry变量记录进位创建cur指针指向新链表计算结果存储位每计算完一次下移一位。当两张链表都没有走完或者进位还在就执行cur所指位的计算。注意这里也有假表头dummy防止两张链表均为空。LeetCode 32、最⻓有效括号困难给你⼀个只包含 ‘(’ 和 ‘)’ 的字符串找出最⻓有效格式正确且连续括号⼦串的⻓度。代码1classSolution:deflongestValidParentheses(self,s:str)-int:stack[-1]# 初始参照物max_len0fori,charinenumerate(s):ifchar(:stack.append(i)else:stack.pop()ifnotstack:stack.append(i)else:current_leni-stack[-1]max_lenmax(max_len,current_len)returnmax_lenLeetCode 394、字符串解码给定⼀个经过编码的字符串返回它解码后的字符串。编码规则为: k[encoded_string] 表示其中⽅括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输⼊字符串总是有效的输⼊字符串中没有额外的空格且输⼊的⽅括号总是符合格式要求的。此外你可以认为原始数据不包含数字所有的数字只表示重复的次数 k 例如不会出现像 3a 或 2[4] 的输⼊。代码classSolution:defdecodeString(self,s:str)-str:stack[]res# 当前正在拼接的字符串num0# 当前解析到的重复次数forcins:ifc.isdigit():# 处理多位数numnum*10int(c)elifc[:# 保存现场把之前的字符串和次数入栈stack.append((res,num))resnum0elifc]:# 弹出现场重复拼接prev_str,kstack.pop()resprev_strres*kelse:# 普通字母直接追加rescreturnresLeetCode 83、删除排序链表中的重复元素简单给定⼀个已排序的链表的头 head 删除所有重复的元素使每个元素只出现⼀次 。返回已排序的链表 。代码classSolution:defdeleteDuplicates(self,head:Optional[ListNode])-Optional[ListNode]:# 空链表直接返回ifnothead:returnhead curheadwhilecur.next:# 下一个节点和当前重复删除下一个ifcur.valcur.next.val:cur.nextcur.next.nextelse:# 不重复指针后移curcur.nextreturnheadLeetCode 82、删除排序链表中的重复元素 II迭代版给定⼀个已排序的链表的头 head 删除原始链表中所有重复数字的节点只留下不同的数字 。返回已排序的链表 。
