Queue & Stack Conclusion
本文蒐集
LeetCode 225: Implement Queue using Stacks
Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).
Implement the MyQueue class:
void push(int x)Pushes element x to the back of the queue.int pop()Removes the element from the front of the queue and returns it.int peek()Returns the element at the front of the queue.boolean empty()Returnstrueif the queue is empty,falseotherwise.
Notes:
- You must use only standard operations of a stack, which means only
push to top,peek/pop from top,size, andis emptyoperations are valid. - Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.
Follow-up: Can you implement the queue such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.
Example 1:
Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]
Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return falseConstraints:
1 <= x <= 9- At most
100calls will be made topush,pop,peek, andempty. - All the calls to
popandpeekare valid.
我的解法
class MyQueue:
def __init__(self):
"""
Initialize your data structure here.
"""
self.stack1 = []
self.stack2 = []
def push(self, x: int) -> None:
"""
Push element x to the back of queue.
"""
self.stack1.append(x)
def pop(self) -> int:
"""
Removes the element from in front of queue and returns that element.
"""
if self.stack2:
return self.stack2.pop()
while self.stack1:
self.stack2.append(self.stack1.pop())
if self.stack2:
return self.stack2.pop()
return 0
def peek(self) -> int:
"""
Get the front element.
"""
if self.stack2:
return self.stack2[-1]
while self.stack1:
self.stack2.append(self.stack1.pop())
if self.stack2:
return self.stack2[-1]
return 0
def empty(self) -> bool:
"""
Returns whether the queue is empty.
"""
if self.stack1 or self.stack2:
return False
return True
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()LeetCode 232: Implement Stack using Queues
Implement a last in first out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal queue (push, top, pop, and empty).
Implement the MyStack class:
void push(int x)Pushes element x to the top of the stack.int pop()Removes the element on the top of the stack and returns it.int top()Returns the element on the top of the stack.boolean empty()Returnstrueif the stack is empty,falseotherwise.
Notes:
- You must use only standard operations of a queue, which means only
push to back,peek/pop from front,size, andis emptyoperations are valid. - Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue), as long as you use only a queue's standard operations.
Example 1:
Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]
Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return FalseConstraints:
1 <= x <= 9- At most
100calls will be made topush,pop,top, andempty. - All the calls to
popandtopare valid.
Follow-up: Can you implement the stack such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer. You can use more than two queues.
我的解法
class MyStack:
def __init__(self):
"""
Initialize your data structure here.
"""
self.queue1 = []
self.queue2 = []
def push(self, x: int) -> None:
"""
Push element x onto stack.
"""
if self.empty():
self.queue1.append(x)
elif self.queue1:
self.queue2.append(x)
while self.queue1:
self.queue2.append(self.queue1.pop(0))
else:
self.queue1.append(x)
while self.queue2:
self.queue1.append(self.queue2.pop(0))
def pop(self) -> int:
"""
Removes the element on top of the stack and returns that element.
"""
if self.empty():
return 0
elif self.queue1:
return self.queue1.pop(0)
else:
return self.queue2.pop(0)
def top(self) -> int:
"""
Get the top element.
"""
if self.empty():
return 0
elif self.queue1:
return self.queue1[0]
else:
return self.queue2[0]
def empty(self) -> bool:
"""
Returns whether the stack is empty.
"""
if self.queue1 or self.queue2:
return False
return True
# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()LeetCode 394: Decode String
Given an encoded string, return its decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].
Example 1:
Input: s = "3[a]2[bc]"
Output: "aaabcbc"Input: s = "3[a2[c]]"
Output: "accaccacc"Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"Input: s = "abc3[cd]xyz"
Output: "abccdcdcdxyz"Constraints:
1 <= s.length <= 30sconsists of lowercase English letters, digits, and square brackets'[]'.sis guaranteed to be a valid input.- All the integers in
sare in the range[1, 300].
我的解法
class Solution:
def decodeString(self, s: str) -> str:
stack = []
temp = []
result = ''
number = ''
for i in s:
if i == ']':
c = stack.pop()
while c != '[':
temp.append(c)
c = stack.pop()
number = stack.pop()
try:
while True:
number = str(int(stack[-1])) + number
stack.pop()
except:
temp *= int(number)
while temp:
stack.append(temp.pop())
else:
stack.append(i)
for _ in stack:
result = result + _
return resultLeetCode 733: Flood Fill
An image is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535).
Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor, "flood fill" the image.
To perform a "flood fill", consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor.
At the end, return the modified image.
Example 1:
Input:
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation:
From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected
by a path of the same color as the starting pixel are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected
to the starting pixel.- The length of
imageandimage[0]will be in the range[1, 50]. - The given starting pixel will satisfy
0 <= sr < image.lengthand0 <= sc < image[0].length. - The value of each color in
image[i][j]andnewColorwill be an integer in[0, 65535].
我的解法
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
self.visited = set()
self.newColor = newColor
self.oldColor = image[sr][sc]
self.dfs(image, sr, sc)
return image
def dfs(self, image: List[List[int]], sr: int, sc: int):
if sr < 0 or sc < 0 or sr >= len(image) or sc >= len(image[0]) or image[sr][sc] != self.oldColor or (sr,sc) in self.visited:
return
image[sr][sc] = self.newColor
self.visited.add((sr, sc))
self.dfs(image, sr-1, sc)
self.dfs(image, sr+1, sc)
self.dfs(image, sr, sc-1)
self.dfs(image, sr, sc+1)LeetCode 542: 01 Matrix
Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.
Example 1:
Input:
[[0,0,0],
[0,1,0],
[0,0,0]]
Output:
[[0,0,0],
[0,1,0],
[0,0,0]]Input:
[[0,0,0],
[0,1,0],
[1,1,1]]
Output:
[[0,0,0],
[0,1,0],
[1,2,1]]Note:
- The number of elements of the given matrix will not exceed 10,000.
- There are at least one 0 in the given matrix.
- The cells are adjacent in only four directions: up, down, left and right.
我的解法 1
利用 DFS ，但是會 Time Limit Exceeded
# Time Limit Exceeded
class Solution:
def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == 1:
matrix[i][j] = float('inf')
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == 0:
self.dfs(matrix, i, j, 0)
return matrix
def dfs(self, m, i, j, count):
if i < 0 or i >= len(m) or j < 0 or j >= len(m[0]) or count > m[i][j]:
return
m[i][j] = count
count += 1
self.dfs(m, i+1, j, count)
self.dfs(m, i-1, j, count)
self.dfs(m, i, j+1, count)
self.dfs(m, i, j-1, count)我的解法 2
參考網友的 BFS1，大部分過程有想到但是一開始就把所有 0 加入 queue 卻沒想到～
class Solution:
def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
m, n = len(matrix), len(matrix[0])
queue = collections.deque()
res = [[-1 for _ in range(n)] for _ in range(m)]
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
res[i][j] = 0
queue.append((i, j))
while queue:
curI, curJ = queue.popleft()
for i, j in dirs:
neighBorI, neighBorJ = curI + i, curJ + j
if 0 <= neighBorI < m and 0 <= neighBorJ < n and res[neighBorI][neighBorJ] == -1:
res[neighBorI][neighBorJ] = res[curI][curJ] + 1
queue.append((neighBorI, neighBorJ))
return res再一次右下到左上可以彌補沒找到的方向 class Solution:
def updateMatrix(self, matrix):
m, n = len(matrix), len(matrix and matrix[0])
for i in range(m):
for j in range(n):
if matrix[i][j] != 0:
matrix[i][j] = float("inf")
if i > 0 and matrix[i - 1][j] + 1 < matrix[i][j]:
matrix[i][j] = matrix[i - 1][j] + 1
if j > 0 and matrix[i][j - 1] + 1 < matrix[i][j]:
matrix[i][j] = matrix[i][j - 1] + 1
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
if matrix[i][j] != 0:
if i + 1 < m and matrix[i + 1][j] + 1 < matrix[i][j]:
matrix[i][j] = matrix[i + 1][j] + 1
if j + 1 < n and matrix[i][j + 1] + 1 < matrix[i][j]:
matrix[i][j] = matrix[i][j + 1] + 1
return matrixN rooms and you start in room 0. Each room has a distinct number in 0, 1, 2, ..., N-1, and each room may have some keys to access the next room.
Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, ..., N-1] where N = rooms.length. A key rooms[i][j] = v opens the room with number v.
Initially, all the rooms start locked (except for room 0).
You can walk back and forth between rooms freely.
Return true if and only if you can enter every room.
Example 1:
Input: [[1],[2],[3],[]]
Output: true
Explanation:
We start in room 0, and pick up key 1.
We then go to room 1, and pick up key 2.
We then go to room 2, and pick up key 3.
We then go to room 3. Since we were able to go to every room, we return true.Input: [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can't enter the room with number 2.1 <= rooms.length <= 10000 <= rooms[i].length <= 1000- The number of keys in all rooms combined is at most
3000.
我的解法
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
queue = []
visited = set()
queue.append(0)
visited.add(0)
while queue:
length = len(queue)
for _ in range(length):
i = queue.pop(0)
for j in rooms[i]:
if j not in visited:
queue.append(j)
visited.add(j)
if len(visited) == len(rooms):
return True
else:
return False