【一道难题】

java2python

确实，网上检索“LeetCode-Python-1172”

java2python

你可能用的是C，怎么语句后面都是分号：
用python写了个，没有用python的heapq

1. #DinnerPlates(int capacity) - 给出栈的最大容量 capacity。
   
2. #void push(int val) - 将给出的正整数 val 推入 从左往右第一个 没有满的栈。
   
3. #int pop() - 返回 从右往左第一个 非空栈顶部的值，并将其从栈中删除；如果所有的栈都是空的，请返回 -1。
   
4. #int popAtStack(int index) - 返回编号 index 的栈顶部的值，并将其从栈中删除；如果编号 index 的栈是空的，请返回 -1。
   
5. 
   
6. class DP:
   
7.     stacks = []
   
8.     stacks_index = []
   
9.     capacity = 5
   
10. 
    
11.     @staticmethod
    
12.     def DinnerPlates(capacity):
    
13.         DP.capacity = capacity
    
14. 
    
15.     @staticmethod
    
16.     def free_pos(start=None, end =None):
    
17.         if start == None:
    
18.             start,end = 0,len(DP.stacks)
    
19.         selected = DP.stacks_index[start:end]
    
20.         return (end-start)* DP.capacity - sum(DP.stacks_index)
    
21.         
    
22.     @staticmethod
    
23.     def first_free(start,end):
    
24.         if start == end-1:
    
25.             if DP.stacks_index[start] < DP.capacity:
    
26.                 return start
    
27.             else:
    
28.                 return -1
    
29. 
    
30.         middle = (start + end)//2
    
31.         part1 = DP.first_free(start,middle)
    
32.         return part1 if part1 !=-1 else DP.first_free(middle,end)
    
33. 
    
34.     @staticmethod
    
35.     def first_filled(start,end):
    
36.         if start == end-1:
    
37.             if DP.stacks_index[start] > 0:
    
38.                 return start
    
39.             else:
    
40.                 return -1
    
41. 
    
42.         middle = (start + end)//2
    
43.         part1 = DP.first_filled(middle,end)
    
44.         return part1 if part1 !=-1 else DP.first_filled(start,middle)
    
45. 
    
46.     @staticmethod
    
47.     def push(val):
    
48.         if DP.free_pos()>0:
    
49.             index = DP.first_free(0,len(DP.stacks))
    
50.         else:
    
51.             index = len(DP.stacks)
    
52.             stack = [-1 for i in range(DP.capacity)]
    
53.             DP.stacks.append(stack)
    
54.             DP.stacks_index.append(0)
    
55.         DP.stacks[index][DP.stacks_index[index]] = val
    
56.         DP.stacks_index[index] += 1
    
57.     @staticmethod
    
58.     def pop():
    
59.         if sum(DP.stacks_index) == 0:
    
60.             return -1
    
61.         else:
    
62.             index = DP.first_filled(0,len(DP.stacks))
    
63.             DP.stacks_index[index] -= 1
    
64.             return DP.stacks[index][DP.stacks_index[index]]
    
65.     @staticmethod
    
66.     def popAtStack(index):
    
67.         if index < len(DP.stacks) and DP.stacks_index[index] > 0:
    
68.             DP.stacks_index[index] -= 1
    
69.             return DP.stacks[index][DP.stacks_index[index]]
    
70.         else:
    
71.             return -1
    
72.        
    
73. DP.DinnerPlates(2)
    
74. DP.push(1)
    
75. DP.push(2)
    
76. DP.push(3)
    
77. DP.push(4)
    
78. DP.push(5)
    
79. print(DP.stacks,DP.stacks_index,DP.capacity)
    
80. DP.popAtStack(0)
    
81. print(DP.stacks,DP.stacks_index,DP.capacity)
    
82. DP.push(20)
    
83. print(DP.stacks,DP.stacks_index,DP.capacity)
    
84. print(DP.stacks,DP.stacks_index,DP.capacity)
    
85. DP.popAtStack(0)
    
86. print(DP.stacks,DP.stacks_index,DP.capacity)
    
87. DP.push(20)
    
88. print(DP.stacks,DP.stacks_index,DP.capacity)
    
89. DP.push(21)
    
90. print(DP.stacks,DP.stacks_index,DP.capacity)
    
91. DP.popAtStack(0)
    
92. print(DP.stacks,DP.stacks_index,DP.capacity)
    
93. DP.popAtStack(2)
    
94. print(DP.stacks,DP.stacks_index,DP.capacity)
    
95. DP.pop()
    
96. print(DP.stacks,DP.stacks_index,DP.capacity)
    
97. DP.pop()
    
98. print(DP.stacks,DP.stacks_index,DP.capacity)
    
99. DP.pop()
    
100. print(DP.stacks,DP.stacks_index,DP.capacity)
     
101. DP.pop()
     
102. print(DP.stacks,DP.stacks_index,DP.capacity)
     
103. DP.pop()
     
104. print(DP.stacks,DP.stacks_index,DP.capacity)

复制代码

结果（栈列表，以及各栈的栈顶指针，指针为零，栈内值不设置为-1的，主要看栈顶指针）：
栈列表，栈顶指针，最后一个2是容量（这个可以无视）
[[1, 2], [3, 4], [5, -1]] [2, 2, 1] 2
[[1, 2], [3, 4], [5, -1]] [1, 2, 1] 2
[[1, 20], [3, 4], [5, -1]] [2, 2, 1] 2
[[1, 20], [3, 4], [5, -1]] [2, 2, 1] 2
[[1, 20], [3, 4], [5, -1]] [1, 2, 1] 2
[[1, 20], [3, 4], [5, -1]] [2, 2, 1] 2
[[1, 20], [3, 4], [5, 21]] [2, 2, 2] 2
[[1, 20], [3, 4], [5, 21]] [1, 2, 2] 2
[[1, 20], [3, 4], [5, 21]] [1, 2, 1] 2
[[1, 20], [3, 4], [5, 21]] [1, 2, 0] 2
[[1, 20], [3, 4], [5, 21]] [1, 1, 0] 2
[[1, 20], [3, 4], [5, 21]] [1, 0, 0] 2
[[1, 20], [3, 4], [5, 21]] [0, 0, 0] 2
[[1, 20], [3, 4], [5, 21]] [0, 0, 0] 2