Leetcode刷题python3版第一周（下）

Day5

LeetCode 150、逆波兰表达式求值（中等√）

根据 逆波兰表示法，求表达式的值。
有效的算符包括 + 、 - 、 * 、 / 。每个运算对象可以是整数，也可以是另⼀个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
代码：

classSolution:defevalRPN(self,tokens:List[str])->int:stack=[]op={'+':lambdaa,b:a+b,'-':lambdaa,b:a-b,'*':lambdaa,b:a*b,'/':lambdaa,b:int(a/b)}fortokenintokens:iftokeninop:b=stack.pop()a=stack.pop()res=op[token](a,b)stack.append(res)else:stack.append(int(token))returnstack[0]

1-栈
就像桶，先放进去的东西压在底下，只能拿最上面最后放进去的。
两个核心操作：
append(x)：往桶顶部丢一个数字（入栈）
pop()：拿走桶最顶上的数字（出栈，拿完就删掉）
创建一个空列表stack，这里的列表操作可以很好的实现栈。
2-运算符字典 + lambda
lambda：关键字，代表创建匿名小函数
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_stackorval<=self.min_stack[-1]:self.min_stack.append(val)defpop(self)->None:top_val=self.stack.pop()# 如果弹出的是当前最小值，辅助栈同步弹出iftop_val==self.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、1
min_stack 会存 [2,1,1]，后面弹出一个 1，辅助栈只删一个 1，不会直接把最小值删掉
2- pop 出栈方法
stack.pop出栈并赋值给top_val和min_stack的最后一位比较。
3-top () 获取栈顶
纯主栈操作，和辅助栈无关
4-getMin () 获取当前最小值
这就是双栈设计的核心优势：不用遍历全部元素，直接拿辅助栈顶部，常数时间得到最小值。

LeetCode 1614、括号的最⼤嵌套深度（简单√）

如果字符串满⾜以下条件之⼀，则可以称之为有效括号字符串*（valid parentheses string，可以简写为VPS）：
1、字符串是⼀个空字符串 “” ，或者是⼀个不为 “(” 或 “)” 的单字符。
2、字符串可以写为 AB （ A 与 B 字符串连接），其中 A 和 B 都是 有效括号字符串 。
3、字符串可以写为 (A) ，其中 A 是⼀个 有效括号字符串 。
4、类似地，可以定义任何有效括号字符串 S 的 嵌套深度 depth(S) ：
5、depth(“”) = 0
6、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_depth=0current=0forcins:ifc=='(':current+=1max_depth=max(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：字符串开头就是右括号，还没压入stack
stack[-1] != pairs[char]：配对失败
以上情况直接return false，否则（配对成功），出栈。
如果是左括号，则压入。
运行结束判断stack是否为空，为空则ture。

LeetCode 71、简化路径（中等√）

给你⼀个字符串 path ，表示指向某⼀⽂件或⽬录的 Unix ⻛格 绝对路径 （以 ‘/’ 开头），请你将其转化为更加简洁的规范路径。
在 Unix ⻛格的⽂件系统中，⼀个点（ . ）表示当前⽬录本身；此外，两个点 （ … ） 表示将⽬录切换到上⼀级（指向⽗⽬录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即， ‘//’ ）都被视为单个斜杠’/’ 。 对于此问题，任何其他格式的点（例如， ‘…’ ）均被视为⽂件/⽬录名称。

classSolution:defsimplifyPath(self,path:str)->str:stack=[]# 按/分割路径，连续/会分割出空字符串，后续过滤掉parts=path.split('/')forpartinparts:# 空字符串（连续/拆分得到）和.都直接跳过ifpart==''orpart=='.':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得到空字符串，最终返回/，完美符合所有格式要求：始终以/开头、目录间只有一个/、末尾不会不会包含.和…。

Day6

LeetCode 224、基本计算器（困难）

给你⼀个字符串表达式 s ，请你实现⼀个基本计算器来计算并返回它的值。

代码：

classSolution:defcalculate(self,s:str)->int:stack=[]res=0# 当前累计结果sign=1# 当前数字正负号，初始为正i=0n=len(s)whilei<n:c=s[i]ifc==' ':i+=1elifc.isdigit():# 处理多位数num=0whilei<nands[i].isdigit():num=num*10+int(s[i])i+=1res+=sign*numelifc=='+':sign=1i+=1elifc=='-':sign=-1i+=1elifc=='(':# 压入括号前的结果和符号stack.append(res)stack.append(sign)res=0sign=1i+=1elifc==')':# 弹出符号和之前结果，合并括号内的值res*=stack.pop()res+=stack.pop()i+=1returnres

LeetCode 2、两数相加（中等）

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头

代码：

# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:defaddTwoNumbers(self,l1:Optional[ListNode],l2:Optional[ListNode])->Optional[ListNode]:# 哑节点，方便构建结果链表dummy=ListNode()cur=dummy carry=0whilel1orl2orcarry:# 取当前位数字，链表空则取0v1=l1.valifl1else0v2=l2.valifl2else0# 计算总和、当前位、新进位total=v1+v2+carry carry=total//10cur.next=ListNode(total%10)# 指针后移cur=cur.nextl1=l1.nextifl1elseNonel2=l2.nextifl2elseNonereturndummy.next

思路：创建一个新链表记录结果，创建一个carry变量记录进位，创建cur指针指向新链表计算结果存储位，每计算完一次下移一位。当两张链表都没有走完或者进位还在就执行cur所指位的计算。注意这里也有假表头dummy，防止两张链表均为空。

LeetCode 32、最⻓有效括号（困难）

给你⼀个只包含 ‘(’ 和 ‘)’ 的字符串，找出最⻓有效（格式正确且连续）括号⼦串的⻓度。

代码1：

classSolution:deflongestValidParentheses(self,s:str)->int:stack=[-1]# 初始参照物max_len=0fori,charinenumerate(s):ifchar=='(':stack.append(i)else:stack.pop()ifnotstack:stack.append(i)else:current_len=i-stack[-1]max_len=max(max_len,current_len)returnmax_len

LeetCode 394、字符串解码

给定⼀个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string] ，表示其中⽅括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输⼊字符串总是有效的；输⼊字符串中没有额外的空格，且输⼊的⽅括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输⼊。
代码：

classSolution:defdecodeString(self,s:str)->str:stack=[]res=""# 当前正在拼接的字符串num=0# 当前解析到的重复次数forcins:ifc.isdigit():# 处理多位数num=num*10+int(c)elifc=='[':# 保存现场：把之前的字符串和次数入栈stack.append((res,num))res=""num=0elifc==']':# 弹出现场，重复拼接prev_str,k=stack.pop()res=prev_str+res*kelse:# 普通字母直接追加res+=creturnres

LeetCode 83、删除排序链表中的重复元素（简单）

给定⼀个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现⼀次 。返回已排序的链表 。

代码：

classSolution:defdeleteDuplicates(self,head:Optional[ListNode])->Optional[ListNode]:# 空链表直接返回ifnothead:returnhead cur=headwhilecur.next:# 下一个节点和当前重复，删除下一个ifcur.val==cur.next.val:cur.next=cur.next.nextelse:# 不重复，指针后移cur=cur.nextreturnhead

LeetCode 82、删除排序链表中的重复元素 II（迭代版）

给定⼀个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回已排序的链表 。