python-3.x - 关于从堆栈中删除中间元素时递归堆栈的问题
问题描述
我有运行代码从堆栈中删除中间元素，这不是问题。这是我的代码；
def insert(stack,temp,curr,n):
#print(curr,stack)
if curr!=n//2:
print(curr)
stack.append(temp)
#return
return
def delete_middle(stack,n,curr):
while len(stack)>0:
temp=stack.pop()
delete_middle(stack,n,curr+1)
insert(stack,temp,curr,n)
#print(stack)
return stack
delete_middle([2,4,1,18,34],5,0)
我的代码工作正常。但我试图了解递归堆栈是如何工作的。例如，我们正在对delete_middle()大约5时间（与列表长度相同stack）进行递归调用。每次指针变量 ,curr都会更新为指向当前元素。如您所见，最后一个值为curr5，但由于堆栈的长度为 0，因此不再有递归调用。然后insert()调用该函数。
有趣的是，如果我查看currinside的值insert()，我们会得到以下输出；
4
3
2
1
0
为什么我们在这里看不到第一个值为curr5 的值？我将非常感谢这里的一些反馈。我可以对它的时间复杂度有一些想法吗？它似乎是堆栈O(N)的N大小。但我对此有点生疏。将在这里欣赏一些见解。谢谢
解决方案
编辑：
只有在递归函数使用空堆栈后，才会执行插入函数。
START DELETE 0 [only one while loop executed]
START DELETE 1 [only one while loop executed]
START DELETE 2 [only one while loop executed]
START DELETE 3 [only one while loop executed]
START DELETE 4 [only one while loop executed]
START DELETE 5 [NO while loop executed because list is empty]
-------------------------
START INSERT iteration 4
END INSERT iteration 4
END DELETE 4
-------------------------
START INSERT iteration 3
END INSERT iteration 3
END DELETE 3
-------------------------
START INSERT iteration 2
END INSERT iteration 2
END DELETE 2
-------------------------
START INSERT iteration 1
END INSERT iteration 1
END DELETE 1
-------------------------
START INSERT iteration 0
END INSERT iteration 0
END DELETE 0
因此，我们首先运行插入函数 (4)，因为在执行最后一个 delete_middle(5) 时，列表堆栈是空的，并且它没有按所述运行插入函数：
while len(stack)>0:
...........
insert(stack,temp,curr,n)
上面的delete_middlewithn=5将不会执行，因为len(stack)==0.
中间是如何工作的：
#first executed delete_middle([2,4,1,18,34],5,0)
def delete_middle(stack,n,curr): iteration 1
while len(stack)>0: initial stack [2,4,1,18,34]
temp=stack.pop() stack after removal [2,4,1,18]
.....
delete_middle(stack,n,curr+1) -> becomes: delete_middle([2,4,1,18],5,1) iteration 2
while len(stack)>0: initial stack [2,4,1,18]
temp=stack.pop() stack after removal [2,4,1]
.....
delete_middle(stack,n,curr+1) > becomes: delete_middle([2,4,1],5,2) and so on until stack = [] (empty)
.....
(!) During these iterations insert(stack,temp,curr,n) is not executed because:
插入如何运行：
delete_middle([2,4,1,18,34],5,0)
# Iteration 1
#delete_middle(stack, n, curr+1)
delete_middle([2,4,1,18], 5, 1 )
insert not executed!
# Iteration 2
delete_middle([2,4,1],5,2)
insert not executed!
# Iteration 3
delete_middle([2,4],5,3)
insert not executed!
# Iteration 4
delete_middle([2],5,4)
insert not executed!
# Iteration 5
delete_middle([],5,5) # returns nothing because it does not enter the while loop
insert not executed!
Only from now -> each insert will be executed from inside delete_middle!
insert 4
insert 3
insert 2
insert 1
关于时间复杂度：
Time complexity = time taken to build the final list;
= (1 pop + 1 insert) * n
= O(n)
在最坏的情况下，您可以说复杂度为 O(n)，因为将列表大小减少 1 个元素涉及将 1 个元素附加到列表中，这是因为每个级别只有一个递归。（而 .. return缩进）
虽然 pop 是 O(1) 并且列表每次都会减少 (O(log n))，但是当每个middle_delete被调用时，您的算法的运行时间会随着输入数据的大小而增加，总共执行 (n-1) appends；附加整个剩余列表。
结束编辑
关于您的代码，是的，它可以工作，但如果可以的话，会有一些限制：
- 目标列表的长度必须是奇数
- 需要一些额外的不必要的*标准 (
curr,n) [不必要的见最后部分] - 功能未“完全正确”执行
说明：
自己试试
回答结束（对我有耐心:)）
- 例如：
在您的代码中：
while len(stack)>0:
.....
return stack
基本上，您似乎返回了 while 循环的第一个值。例子：
c = 0
def func(d):
while d < 5:
d+=1
return d
print(func(c))
递归效果是通过在 while 循环中巧妙地使用None生成的 func(insert) 来触发的。这就像拉手断而不是踏板。:)
关于您的问题：
如下所示，（中间函数被执行+插入函数）为每个元素。
delete middle iterion 0
--------------------------
temp 34 0
delete middle iterion 1
--------------------------
temp 18 1
delete middle iterion 2
--------------------------
temp 1 2
delete middle iterion 3
--------------------------
temp 4 3
delete middle iterion 4
--------------------------
temp 2 4
delete middle iterion 5
--------------------------
======================
insert iteration 4
curr:4, stack:[], temp:2,n:5
======================
insert iteration 3
curr:3, stack:[2], temp:4,n:5
======================
insert iteration 2
curr:2, stack:[2, 4], temp:1,n:5
======================
insert iteration 1
curr:1, stack:[2, 4], temp:18,n:5
======================
insert iteration 0
curr:0, stack:[2, 4, 18], temp:34,n:5
[2, 4, 18, 34]
为什么我们在这里看不到 curr 的第一个值是 5？
如果curr从 0 开始 ( )，您将看到从 4->0 的迭代，而当初始 curr 为 1 时，迭代将为 5->1；因此将触发 5 (N) 个删除函数调用。
- 我用一个简单的逻辑重构了你的代码：
如果您有一个目标列表 [1,2,..,n-1,n] 并且您想使用递归函数删除中间部分，那么这种方法可能会吸引您：
让我们从列表的每个元素的 0 计数器开始，count = 0
计数器将增加 1count+=1
现在，要从每一侧（左、右）消除一个元素以到达中间，我们可以说：如果 count 为 0 或 count 甚至从列表中删除最后一项，如果不删除第一项，则列表丢失每次迭代一项。
if count == 0 and count % 2 == 0:
target_list.pop(-1)
else:
target_list.pop(0)
那么如果列表有偶数个项目呢？然后我们也将包括这个场景：if len(target) == 2.
我还建议使用一个小技巧，即函数参数的默认值仅在定义函数时评估一次。
我的意思是什么？检查常见错误 #1的示例。
要将上面的所有内容包含到最终的 func (O(N)) 中：
def eliminate_middle(target, count=0, beg_l=[],end_l=[]):
print(count) # O(N)
if len(target) == 1: # if target has only one element
return beg_l+sorted(end_l)
else:
if count == 0 or count % 2 == 0:
if len(target) == 2: # case len(target) is Even
return beg_l+sorted(end_l) #eliminates the two middle elements
end_l.append(target.pop(-1)) #target loses last element
return eliminate_middle(target,count+1)
else:
beg_l.append(target.pop(0)) # target loses first element
return eliminate_middle(target, count+1)
print(eliminate_middle([2,4,1,18,34]))
推荐阅读
- go - 如何将值分配给反射字段（）？
- python - 如何在 `LogEntry` 模型上修复 django 管理页面中的对象表示。django 2.2
- swift - 如何在存储在数组/ Swift 5 中的视图中显示所有 TextField
- javascript - 根据从下拉列表中选择的选项加载 Fullcalendar 数据库
- angular - Angular 9 引入了需要加载的全局“$localize()”函数
- python - 如何进行延迟并打印？
- angular - 实施 Lz-string 1.4.4 库以使用 CompressTOUTF16 函数 angular7？
- javascript - 在输入时调整文本区域的大小
- node.js - 如何在表单数据项上设置自定义标题？
- python - 如何正确排序 Python 的 PrettyTable 整数列