给定 有效括号字符串 s
,返回 s
的 嵌套深度。嵌套深度是嵌套括号的 最大 数量。
示例 1:
输入:s = "(1+(2*3)+((8)/4))+1"
输出:3
解释:数字 8 在嵌套的 3 层括号中。
示例 2:
输入:s = "(1)+((2))+(((3)))"
输出:3
解释:数字 3 在嵌套的 3 层括号中。
示例 3:
输入:s = "()(())((()()))"
输出:3
提示:
1 <= s.length <= 100
s
由数字0-9
和字符'+'
、'-'
、'*'
、'/'
、'('
、')'
组成- 题目数据保证括号字符串
s
是 有效的括号字符串
自己的垃圾错误代码
class Solution:
def maxDepth(self, s: str) -> int:
count1,count2 = 0,0
lis = []
li = []
for i in range(len(s)):
if 48 <= ord(s[i]) <= 57:
lis.append(i)
for x in lis:
count1,count2 = 0,0
for j in range(x):
if s[j] == "(":
count1 += 1
elif s[j] == ")":
count2 += 1
else:
continue
count = count1 - count2
li.append(count)
if li:
return max(li)
else:
return 0 # 如果没有任何括号,返回0
计算了每一个数字所对应的count数,没包含最深嵌套层里没有数字的情况。
遍历纪录最大深度
class Solution:
def maxDepth(self, s: str) -> int:
max_depth = 0
current_depth = 0
for char in s:
if char == '(':
current_depth += 1
if current_depth > max_depth:
max_depth = current_depth
elif char == ')':
current_depth -= 1
return max_depth
最短代码
from itertools import accumulate # 引入 accumulate 函数
class Solution:
def maxDepth(self, s: str) -> int:
# 对字符串 s 中的每个字符 ch 进行处理
return max(
accumulate(
{'(': 1, ')': -1}[ch] for ch in s if ch in '()' # 如果 ch 是 '(' 或 ')', 将其映射到相应的值
),
default=0 # 如果 accumulate 结果为空,则 max 返回默认值 0
)
accumulate函数:
累积(accumulate)函数是Python标准库itertools
中的一个强大工具,用于对可迭代对象进行累积操作。它返回一个生成器对象,可以逐个生成累积的结果,而不需要显式编写循环。
语法
itertools.accumulate(iterable, func=operator.add)
其中,iterable
是一个可迭代对象,用于生成输入值序列。func
是一个可选的函数,用于指定累积的操作,默认为operator.add
,即使用加法进行累积。
解析
accumulate函数的功能是对传进来的iterable对象逐个进行某个操作(默认是累加,如果传了某个fun就是应用此fun
比如iterable=[1,2,3,4] 默认会先累加iterable 0~0(1), 然后0~1(1+2),最后0~3(1+2+3)
结果会是[1,3,6,10]
注意:accumulate函数返回是一个可迭代对象,可以用在for里面,而不是最后的累加结果,如果我们想要的是直接的结果
需要强制转化类型,比如转化成list
累积数字序列
accumulate
函数的基本用法是对数字序列执行累积操作。
自定义累积函数
accumulate
函数不仅仅限于对数字进行累积。它还可以使用自定义的二元操作函数来执行累积操作。
计算累积平均值
除了基本的累积操作,accumulate
还可以用于计算累积平均值。用一个自定义的累积函数calculate_mean
,它的累积结果是一个包含两个值的元组,分别表示总和和计数。初始值(0, 0)
用于开始累积。然后,在循环中计算每个累积点的平均值。
字符串连接
accumulate
不仅适用于数字,还可以用于字符串或其他可迭代对象。使用accumulate
函数和一个自定义的累积函数来连接字符串,生成连续的字符串。这对于构建长文本或消息非常有用
累积列表
除了数字和字符串,accumulate
还可以用于列表。使用accumulate
函数和一个自定义的累积函数,将每个元素依次添加到结果列表中。这是在构建累积列表时的一种常见用法。
生成括号深度变化的累积序列:
return max( accumulate( {'(': 1, ')': -1}[ch] for ch in s if ch in '()' ), default=0 )
这行代码是整个方法的核心。它通过以下步骤计算并返回最大嵌套深度:
生成一个映射迭代器:
{'(': 1, ')': -1}[ch] for ch in s if ch in '()'
这部分代码是一个生成器表达式。它遍历字符串
s
中的每个字符ch
,如果ch
是左括号'('
或右括号')'
,则将其映射到对应的值:左括号映射到1
,右括号映射到-1
。忽略其他字符。计算累积和:
accumulate({'(': 1, ')': -1}[ch] for ch in s if ch in '()')
这部分代码使用
accumulate
函数来计算括号深度变化的累积和,生成一个累积和序列。找到累积和的最大值:
max(..., default=0)
这部分代码使用
max
函数找到累积和序列中的最大值。如果累积和序列为空(即字符串s
中没有括号),则返回默认值0
。
栈思想
(使用一个堆栈计数器 stack
来跟踪当前的嵌套深度,并使用 cnt
来记录最大深度)
class Solution:
def maxDepth(self, s: str) -> int:
# 初始化堆栈计数器和最大深度计数器
stack, cnt = 0, 0
# 遍历字符串中的每个字符
for c in s:
# 如果字符是左括号 '('
if c == "(":
stack += 1 # 增加当前深度
cnt = max(cnt, stack) # 更新最大深度
# 如果字符是右括号 ')'
elif c == ")":
stack -= 1 # 减少当前深度
# 返回最大深度
return cnt