我试图通过“值”传递参数。我已经尝试对递归传递的参数进行深度复制,以防止任何更改循环回父函数调用
下面是一段代码,试图生成所有可能括号的数组
def generateParenthesis(n):
#Iterate for each move.
M = 2 * n
retArray = []
def recHelper(numMoves, perm, stack):
print("Function call: ", numMoves, perm, stack)
newPerm = copy.deepcopy(perm)
newStack = stack.copy()
#Base case, no moves
if (numMoves == 0):
retArray.append(newPerm)
return
#Case when left move is valid
if (numMoves != len(newStack)):
#Apply the left move. Pass it recursively
newPerm +='('
#Update the stack accordingly
newStack.append('(')
#Decrease numMoves
newNumMoves = numMoves - 1
#Call it recursively
recHelper(newNumMoves, newPerm, newStack)
#Case when right move is valid
if len(newStack) != 0:
#Apply the right move. Pass it recursively
newPerm +=')'
#Update the stack accordingly, delete the top, last elm
newStack.pop()
#Decrease numMoves
newNumMoves = numMoves - 1
#Call it recursively
recHelper(newNumMoves, newPerm, newStack)
#done
return
recHelper(M, "", [])
return retArray
不幸的是,调用generateParenthesis(1)
返回['()','()(', '()()']
,而不是['()']
经过3个小时的简化,我得到了这个工作代码
例如,现在它为
generateParenthesis(4)
查找类似(()())()
的内容该代码是非常自解释的。您将保留打开/关闭圆括号的计数,并且只有在有对应的打开圆括号时才保留关闭圆括号
我选择不使用堆栈,因为Python中的所有内容都是通过“指针副本”传递的,因此堆栈(即OP中的列表)需要在函数体中花费高昂的
list(stack)
,从而创建列表的本地副本请注意,我创建了新字符串(
partial + '('
,例如),这些新字符串对象通过“指针复制”传递给递归调用(对不起,我现在没有更好的术语。但这很重要)
编辑
您的解决方案存在变量
newPerm
的问题。它的值正在泄漏到第二个递归函数中。此外,您需要了解,除了堆栈之外,不需要复制所有值看看如何简化您的功能。我认为它起作用了:
相关问题 更多 >
编程相关推荐