一、实现栈
class MyStack {
private List<Integer> data;
public MyStack{
data = new ArrayList<>();
public void push(int x){
data.add(x);
}
public boolean isEmpty(){
return data.isEmpty();
}
public int top(){
return data.get(data.size()-1);
}
public boolean pop(){
if (isEmpty()){
return false;
}
data.remove(data.size()-1)
return true
}
public class Main{
public static void main(String[] args){
Mystack s = new MyStack();
s.push(1)
s.push(2)
s.push(3)
for (int i = 0;i<4;i++){
if (!s.isEmpty(){
System.out.println(s.top());
}
System.out.println(s.pop());
}
}
}
二、栈的用法
public class Main{
public static void main(String[] args){
Stack<Integer> s = new Stack<>();
s.push(5);
s.push(13);
s.push(8);
s.push(6);
if (s.empty() == true){
System.out.println("Stack is empty!");
return;
}
s.pop();
System.out.println("The top element is: " + s.peek());
System.out.println("The size is: "+s.size());
}
}
三、例题
1. 最小栈
https://leetcode-cn.com/leetbook/read/queue-stack/g5l7d/
class MinStack:
def __init__(self):
self.stList = []
def push(self, val: int) -> None:
self.stList.append(val)
def pop(self) -> None:
self.stList.pop(-1)
def top(self) -> int:
return self.stList[-1]
def getMin(self) -> int:
min =self.stList[0]
for i in range(1, len(self.stList)):
if self.stList[i]<min:
min = self.stList[i]
return min
结果: 改进: 为了缩减用时,新建一个最小栈list,用于存储每轮入栈时的最小栈,并在每次出栈时也pop掉该list的最后一个值。这样保证了min随着出栈而改变。
class MinStack:
def __init__(self):
self.stList = []
self.minList = []
def push(self, val: int) -> None:
self.stList.append(val)
if self.minList == []:
self.minList.append(val)
elif val < self.minList[-1]:
self.minList.append(val)
else:
self.minList.append(self.minList[-1])
def pop(self) -> None:
self.stList.pop(-1)
self.minList.pop(-1)
def top(self) -> int:
return self.stList[-1]
def getMin(self) -> int:
return self.minList[-1]
结果:
改进: 当栈进出大的元素时,对minList是没有影响的,所以改进算法:==>当新入栈的元素大于min时,minlist不改动;当出栈的元素大于min时,minlist不改动。只有小于或等于min时,minlist才变化。 这样可以减少内存。
(改动为注释处。) (注意:self.stList.pop() == self.getMin() 尽管为判断语句,pop()依然是执行了的)
class MinStack:
def __init__(self):
self.stList = []
self.minList = []
def push(self, val: int) -> None:
self.stList.append(val)
if self.minList == []:
self.minList.append(val)
elif val <= self.minList[-1]:
self.minList.append(val)
def pop(self) -> None:
if self.stList.pop() == self.getMin():
self.minList.pop()
def top(self) -> int:
return self.stList[-1]
def getMin(self) -> int:
return self.minList[-1]
结果:
2. 有效的括号
https://leetcode-cn.com/leetbook/read/queue-stack/g9d0h/ 思路:当出现左括号,入栈对应右括号,即可保证正确的顺序;若之后出现的右括号不符合出栈的符号时,或无出栈元素/多了元素,则为false
class Solution:
def isValid(self, s: str) -> bool:
strList = list(s)
theStack = []
if len(strList) == 0:
return False
for element in strList:
print(element)
if element == '(':
theStack.append(')')
print(theStack)
elif element == '[':
theStack.append(']')
elif element == '{':
theStack.append('}')
elif (len(theStack)==0) or (element != theStack.pop()) :
print(theStack)
return False
if len(theStack)!=0:
return False
return True
优化: 优化最后三行,直接改为返回一个判断的结果
class Solution:
def isValid(self, s: str) -> bool:
strList = list(s)
theStack = []
if len(strList) == 0:
return False
for element in strList:
if element == '(':
theStack.append(')')
elif element == '[':
theStack.append(']')
elif element == '{':
theStack.append('}')
elif (len(theStack)==0) or (element != theStack.pop()) :
return False
return len(theStack)==0
结果: 提升了速度
3. 每日温度
https://leetcode-cn.com/leetbook/read/queue-stack/genw3/ 1)用暴力法,可以通过简短的案例;但测试案例不通过,案例非常长,严重超时,
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
outcome = []
for i in range(0,n-1):
for j in range(i+1, n):
if temperatures[i]<temperatures[j]:
outcome.append(j-i)
break
elif j == n-1:
outcome.append(0)
outcome.append(0)
return outcome
2)用栈解法
思路:考虑用栈记录每个元素下标,存放尚未找到更大元素的元素下标。当新元素比前元素大时,出栈前元素下标,记录下标差,入栈新元素下标;当新元素比前元素小时,入栈新元素下标,等待更大的元素入栈。
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
theStack = []
n = len(temperatures)
outcome = [0]*n
for i in range(0,n):
while (len(theStack)!= 0) and (temperatures[i]>temperatures[theStack[-1]]):
index = theStack.pop()
outcome[index] = i - index
theStack.append(i)
return outcome
结果:
3)最后,原网页从后往前找的方法,i从后往前,j从i+1开始与i元素比较大小,不服条件就跳res[j]格再比较:
public int[] dailyTemperatures(int[] T) {
int[] res = new int[T.length];
for (int i = res.length - 1; i >= 0; i--) {
int j = i + 1;
while (j < res.length) {
if (T[j] > T[i]) {
res[i] = j - i;
break;
} else if (res[j] == 0) {
break;
} else {
j += res[j];
}
}
}
return res;
}
作者:数据结构和算法
链接:https://leetcode-cn.com/leetbook/read/queue-stack/genw3/?discussion=OGBxRQ
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
此方法较快:
4. 逆波兰表达式求值
https://leetcode-cn.com/leetbook/read/queue-stack/gomvm/
算法已给出:
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
theStack = []
for element in tokens:
if element not in ["+","-","*","/"]:
theStack.append(element)
else:
num2 = theStack.pop()
num1 = theStack.pop()
expression = num1+ element + num2
tempResult = int(eval(expression))
theStack.append(str(tempResult))
return int(theStack.pop())
结果: 其他方法: 对于运算符,直接分类讨论,执行用时会减少
四、栈与深度优先搜索
-dfs的访问方式适合用栈:从最后访问的节点一直延伸(入栈),没有可访问的就出栈,然后继续
1. 实现DFS-模板1:递归
https://leetcode-cn.com/leetbook/read/queue-stack/gp5a7/
boolean DFS(Node cur, Node target, Set<Node> visited){
return true if cur is target:
for (next: each neighbor of cur){
if (next is not in visited){
add next to visited;
return true if DFS(next, target, visited) == true;
}
}
return false;
}
2. 习题
1. 克隆图
https://leetcode-cn.com/leetbook/read/queue-stack/gmcr6/
错误做法:直接clone node.neighbors——在neighbor的newNode未创建前,是无法添加进curNewNode.neighbors。
"""
# Definition for a Node.
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
"""
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
stack = []
nodeList = []
visited = set()
created = set()
createdNei = set()
stack.append(node)
visited.add(node.val)
while len(stack)!= 0:
cur = stack.pop()
newNode = Node(cur.val,[])
created.add(node.val)
print(newNode.val)
if newNode.val == 1:
result = newNode
for neighbor in cur.neighbors:
if neighbor.val not in visited:
stack.append(neighbor)
visited.add(neighbor.val)
if cur.val not in createdNei:
newNei = Node(neighbor.val,[])
newNode.neighbors.append(newNei)
createdNei.add(cur.val)
return newNode
正确解法(参照原网页):
dfs递归,建立newNode,然后用val标记各个newNode,存入字典。在给newNode添加neighbor时,dfs进行递归:未clone的(不在字典里的)neighbor先clone,已clone的直接返回新节点。
"""
# Definition for a Node.
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
"""
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
visited = {}
return self.dfsClone(node, visited)
def dfsClone(self, node, visited:{}):
if node == None:
return None
if node.val in visited.keys():
return visited.get(node.val)
else:
newNode = Node(node.val, [])
visited[node.val] = newNode
for neighbor in node.neighbors:
newNode.neighbors.append(self.dfsClone(neighbor, visited))
return newNode
①neighbor作为属性,在递归时进行clone会造成嵌套的循环吗? ——No.[].append操作在内部dfs返回值之前,不执行;当最深的neighbor的新节点都创建完,一步步会返回值,因此不会有循环。 ②什么时候完成.append()操作?newNode.neighbors时候变化? ——当有return完成时(有返回值时),neighbor有增加。
以三点为例,计算过程和对应newNode.neighbor的状态: 结果:
2. 目标和
https://leetcode-cn.com/leetbook/read/queue-stack/ga4o2/。
错误一:一开始,在dfs方法中使用count作为一个变量,但这样每次调用dfs,count都从0开始计算,return后方法结束,对外部的count并没有产生影响。为了将其作为全局变量,使用global限定,依旧出错(python变量名解析遵循LEGB法则)。
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
count = 0
return self.dfsCalculate(nums,0,target,count,0)
def dfsCalculate(self,nums: List[int],tempRes:int, target: int,count,i):
if i == len(nums):
if tempRes == target:
count+=1
return
if i<len(nums):
addRes = tempRes + nums[i]
subRes = tempRes - nums[i]
print("i: %d addRes: %d subRes: %d tempRes: %d"%(i,addRes,subRes,tempRes))
self.dfsCalculate(nums,addRes,target,count,i+1)
self.dfsCalculate(nums,subRes,target,count,i-1)
return count
修正:参考https://www.pythonheidong.com/blog/article/519926/d1050cf106431680133b/ 在目标函数设置self.count=0变量,self.count可在被调用的dfs中被直接修改,不是作为参数传导。最后在目标函数中返回self.count。 修改后解决了问题。
可通过部分测试。但长的案例超时,不通过
class Solution:
def dfsCalculate(self,nums: List[int],tempRes:int, target: int,i):
if i == len(nums):
if tempRes == target:
self.count+=1
return self.count
addRes = tempRes + nums[i]
subRes = tempRes - nums[i]
self.dfsCalculate(nums,addRes,target,i+1)
self.dfsCalculate(nums,subRes,target,i+1)
return self.count
def findTargetSumWays(self, nums: List[int], target: int) -> int:
self.count = 0
self.dfsCalculate(nums,0,target,0)
return self.count
结果: 将dfsCalculate的return self.count 都换成只return,多通过3个案例,之后的案例还是超时。
由讨论区,本题使用动态规划可解决超时问题(留待dp专项再做)。 另,原方法使用JAVA可通过:
class Solution {
private int count = 0;
public int findTargetSumWays(int[] nums, int target) {
dfsCalculate(nums, 0, target, 0);
return count;
}
public void dfsCalculate(int[] nums, int temptSum, int target, int i){
if (i == nums.length){
if (temptSum == target){
count ++;
}
return;
}
int addSum = temptSum + nums[i];
int mnsSum = temptSum - nums[i];
dfsCalculate(nums, addSum, target, i+1);
dfsCalculate(nums, mnsSum, target, i+1);
return;
}
}
结果:
3. 实现DFS-模板2:显式栈
https://leetcode-cn.com/leetbook/read/queue-stack/g2g9c/ 递归方法缺点:深度过大时,堆栈溢出 使用显式栈:
boolean DFS(int root, int target){
Set<Node> visited;
Stack<Node> s;
add root to s;
while (s is not empty){
Node cur = the top element in s;
return true if cur is target;
for (Node next: the neightbors of cur){
if (next is not in visited){
add next to s;
add next to visited;
}
}
remove cur from s;
}
return false;
}
4. 习题
1. 二叉树的中序遍历
https://leetcode-cn.com/leetbook/read/queue-stack/gnq5i/ 题目要求用迭代算法,思路: 中序遍历遵循左-中-右的访问顺序,因此先找到最左的节点(一路找.left直到.left=None,并将一路的节点都存入stack),pop出该最左节点,记录其val,然后看是否有右子树:若有,再搜寻右子树的最左节点,重复上一步骤;若无,再pop出一个节点,记录val,查看右子树。直到stack为空。
简单来说,对于节点,都是先确认.left为None/已被访问过,然后记录val,再然后查看有无.right,有right再查看.left,无right再pop,记录,看right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
theStack = []
theList = []
cur = root
while (cur!=None) or (len(theStack)!=0):
while cur!=None:
theStack.append(cur)
cur = cur.left
cur = theStack.pop()
theList.append(cur.val)
cur = cur.right
return theList
结果:
五、 小结
1. 用栈实现队列
https://leetcode-cn.com/leetbook/read/queue-stack/gvtxe/ 思路:建立两个栈,第一个栈存储queue,第二个栈翻转第一个栈的数据,从而实现queue。 注意:在第二个栈中的元素未全部pop出去时,不添入第一个栈的元素,否则pop()顺序会被打乱。
class MyQueue:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, x: int) -> None:
self.stack1.append(x)
def pop(self) -> int:
if len(self.stack2)== 0:
while len(self.stack1)!=0:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
def peek(self) -> int:
if len(self.stack2)== 0:
while len(self.stack1)!=0:
self.stack2.append(self.stack1.pop())
return self.stack2[-1]
def empty(self) -> bool:
if len(self.stack2)==0 and len(self.stack1)==0:
return True
else:
return False
2. 用队列实现栈
https://leetcode-cn.com/leetbook/read/queue-stack/gw7fg/ 1)用单个队列实现栈 思路:每次向队列添加新元素后,都把前面的元素依次pop出并添加到队列后面==>保留的队列本身是翻转的数据
class MyStack:
def __init__(self):
self.q = []
def push(self, x: int) -> None:
n = len(self.q)
self.q.append(x)
for i in range(n):
self.q.append(self.q.pop(0))
def pop(self) -> int:
return self.q.pop(0)
def top(self) -> int:
return self.q[0]
def empty(self) -> bool:
return len(self.q)==0
2) 两个队列实现栈 思路:一个队列append数据,当遇到pop或top时,将这个队列除了最后一个元素,都pop并存到另一个队列,然后–pop():返回pop(最后一个元素),–top():复制最后一个元素,将其pop存到另一个元素后,返回复制的值
class MyStack:
def __init__(self):
self.q1 = []
self.q2 = []
def push(self, x: int) -> None:
if len(self.q2) == 0:
self.q1.append(x)
else:
self.q2.append(x)
def pop(self) -> int:
if len(self.q1)!= 0:
n = len(self.q1)
for i in range(n-1):
self.q2.append(self.q1.pop(0))
return self.q1.pop()
if len(self.q2)!= 0:
n = len(self.q2)
for i in range(n-1):
self.q1.append(self.q2.pop(0))
return self.q2.pop()
def top(self) -> int:
if len(self.q1)!= 0:
n = len(self.q1)
for i in range(n-1):
self.q2.append(self.q1.pop(0))
x = self.q1[0]
self.q2.append(self.q1.pop(0))
return x
if len(self.q2)!= 0:
n = len(self.q2)
for i in range(n-1):
self.q1.append(self.q2.pop(0))
x = self.q2[0]
self.q1.append(self.q2.pop(0))
return x
def empty(self) -> bool:
if len(self.q1)==0 and len(self.q2) == 0:
return True
else:
return False
3. 字符串解码
解法参考:https://leetcode-cn.com/leetbook/read/queue-stack/gdwjv/?discussion=A8wST0
- 遇数字用num = num * 10 + d来解决多位数字的字符串转数字问题
- 遇[:将之前的字母串入栈,数字入栈; 遇]:将数字出栈,并乘以[后的字符,然后在前面加上出栈的字母串。
class Solution:
def decodeString(self, s: str) -> str:
numStack = []
alphaStack = []
alphaFrag = ''
num = 0
for i in range(len(s)):
if s[i].isalpha():
alphaFrag += s[i]
elif s[i].isdigit():
d = int(s[i])
num = num *10 + d
elif s[i] == '[':
alphaStack.append(alphaFrag)
alphaFrag = ''
numStack.append(num)
num = 0
elif s[i] == ']':
times = numStack.pop()
alphaFrag = alphaFrag * times
alpha = alphaStack.pop()
alphaFrag = alpha + alphaFrag
return alphaFrag
4. 图像渲染
类似小岛问题 注意:1)需要visited避免递归次数超出限制 2)dfs中return的条件可以简化
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
k = image[sr][sc]
visited = set()
return self.dfsColor(image, sr, sc, newColor, k, visited)
def dfsColor(self, image, i, j, newColor, k, visited):
if (image[i][j] == k) and ((i,j) not in visited):
image[i][j] = newColor
visited.add((i,j))
if (j-1>=0):
self.dfsColor(image,i,j-1,newColor,k,visited)
if (j+1<len(image[0])):
self.dfsColor(image,i,j+1,newColor,k,visited)
if (i-1>=0):
self.dfsColor(image,i-1,j,newColor,k,visited)
if (i+1<len(image)):
self.dfsColor(image,i+1,j,newColor,k,visited)
else:
return
return image
dfs中return的条件可简化,但是效率可能下降。
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
k = image[sr][sc]
visited = set()
return self.dfsColor(image, sr, sc, newColor, k, visited)
def dfsColor(self, image, i, j, newColor, k, visited):
if (i<0) or (i>= len(image)) or (j<0) or (j>=len(image[0])) or ((i,j) in visited):
return
if (image[i][j] == k):
image[i][j] = newColor
visited.add((i,j))
self.dfsColor(image,i,j-1,newColor,k,visited)
self.dfsColor(image,i,j+1,newColor,k,visited)
self.dfsColor(image,i-1,j,newColor,k,visited)
self.dfsColor(image,i+1,j,newColor,k,visited)
return image
5. 0-1矩阵
https://leetcode-cn.com/leetbook/read/queue-stack/g7pyt/
思路:目标函数扫描每个格子,对于非1 的格子,调用bfs查找0。bfs使用队列模板。 结果:通过大部分测试,最长的测试通不过,chao
class Solution:
def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
m = len(mat)
n = len(mat[0])
distMat = [[0 for x in range(n)]for y in range(m)]
for i in range(m):
for j in range(n):
if mat[i][j] == 0:
distMat[i][j] = 0
else:
distMat[i][j] = self.bfs( mat, i, j)
return distMat
def bfs(self, mat, a, b) -> int:
m = len(mat)
n = len(mat[0])
depth = -1
q = []
q.append((a,b))
visited = set()
visited.add((m,n))
while(len(q)!=0):
depth+=1
size = len(q)
for each in range(size):
pos = q.pop(0)
i = pos[0]
j = pos[1]
if mat[i][j] == 0:
return depth
if (j-1>=0) and ((i,j-1) not in visited):
q.append((i,j-1))
visited.add((i,j-1))
if j+1<n and ((i,j+1) not in visited):
q.append((i,j+1))
visited.add((i,j+1))
if (i-1>=0) and ((i-1,j) not in visited):
q.append((i-1,j))
visited.add((i-1,j))
if (i+1<m) and ((i+1,j) not in visited):
q.append((i+1,j))
visited.add((i+1,j))
return -1
6. 钥匙和房间
https://leetcode-cn.com/leetbook/read/queue-stack/gle1r/
思路
对每个房间依次设为目标房间,每一轮查看目标房间是否能到达。从room[0]开始,用stack存储能到达、待查看的房间,然后pop出进行查看这个房间的钥匙是否为目标钥匙。
一个要点:visited的set存储的是什么、或什么是否把点存入visited——它是出现过的key?查看过的房间?因这题相当于有环有向图,从之前的单项节点图直观思考不一样。那我们可以从前面的思路的stack来看:visited是避免单个节点重复入栈,那我们直接把房间0和append入栈的节点放入visited,每次append前进行不在visited的判断,即可。
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
roomSize = len(rooms)
for target in range(1, roomSize):
if self.dfs(rooms, target) == False:
return False
return True
def dfs(self, rooms, target):
stack = []
visited = set()
visited.add(0)
for key in rooms[0]:
if key == target:
return True
else:
stack.append(key)
visited.add(key)
while len(stack) != 0:
roomNum = stack.pop()
for key in rooms[roomNum]:
if key == target:
return True
else:
if key not in visited:
stack.append(key)
visited.add(key)
return False
改进1
1)测试使用in能否更快。即查询target是否在某房间的所有钥匙中,而不是每个钥匙依次查是否为target 结果:更慢了 不存储到keys比上面更慢。
☆ 改进2
2)题目探究从房间0进入,是否能进入所有房间,那么我们可对这一步能进入的房间进行标记,并递归下一步能进入的所有房间。如果最后仍然有房间不能进入,则返回False,否则返回True
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
roomSize = len(rooms)
self.noted = [0]*roomSize
self.dfsNote(rooms, 0)
if 0 in self.noted:
return False
else:
return True
def dfsNote(self, rooms, i):
if self.noted[i] == 1:
return
if self.noted[i] == 0:
self.noted[i] =1
for key in rooms[i]:
self.dfsNote(rooms, key)
效果不错
|