Unit 1 Practice I
LeetCode 225. Implement Stack using Queues
Implement the following operations of a stack using queues.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
empty() -- Return whether the stack is empty.
Notes:
You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).
Click to see the details of three solutions.
public class MyStack {
private Queue<Integer> queue = new LinkedList<>();
/** Initialize your data structure here. */
public MyStack() {
}
/** Push element x onto stack. */
public void push(int x) {
queue.add(x);
for (int i=1; i<queue.size(); i++)
queue.add(queue.remove());
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue.remove();
}
/** Get the top element. */
public int top() {
return queue.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue.isEmpty();
}
}
Unit 2 Practice II
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
挨个检查给的String里的每个character，如果是左括号，相应的右括号入栈；如果是右括号，先检查栈，如果为空，证明不能匹配，如果栈不空，弹出栈顶元素top，检查是否与当前的右括号匹配，不匹配返回false。当字符全都检查完后，判断栈是否为空，空则说明都匹配，不空则证明有没匹配的。
public boolean isValid(String s) {
Stack<Character> stack = new Stack<Character>();
for (char c: s.toCharArray()) {
if (c == '(') {
stack.push(')');
}
else if (c == '[') {
stack.push(']');
}
else if (c == '{') {
stack.push('}');
}
else if (stack.isEmpty() || stack.pop() != c) {
return false;
}
}
return stack.isEmpty();
}
Unit 3 Practice III
Implement the following operations of a queue using stacks.
push(x) -- Push element x to the back of queue.
pop() -- Removes the element from in front of queue.
peek() -- Get the front element.
empty() -- Return whether the queue is empty.
Notes:
You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).
public class MyQueue {
Stack<Integer> queue = new Stack<Integer>();
/** Initialize your data structure here. */
public MyQueue() {
}
/** Push element x to the back of queue. */
public void push(int x) {
Stack<Integer> temp = new Stack<Integer>();
while(!queue.empty()){
temp.push(queue.pop());
}
queue.push(x);
while(!temp.empty()){
queue.push(temp.pop());
}
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
return queue.pop();
}
/** Get the front element. */
public int peek() {
return queue.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return queue.empty();
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
Unit 4 Practice IV
LeetCode 102. Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
BTLOT.jpg
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int curDeep = 0;
while(!queue.isEmpty()) {
curDeep = queue.size();
List<Integer> levelResult = new ArrayList<>();
for (int i = 0; i < curDeep; i++) {
TreeNode peek = queue.poll();
levelResult.add(peek.val);
if(peek.left != null) {
queue.offer(peek.left);
}
if(peek.right!=null) {
queue.offer(peek.right);
}
}
result.add(levelResult);
}
return result;
}
