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.
挨個(gè)檢查給的String里的每個(gè)character，如果是左括號(hào)命浴，相應(yīng)的右括號(hào)入棧齐邦；如果是右括號(hào)讥蔽，先檢查棧拧略，如果為空绷杜，證明不能匹配岛蚤，如果棧不空酝锅，彈出棧頂元素top，檢查是否與當(dāng)前的右括號(hào)匹配蒿赢，不匹配返回false润樱。當(dāng)字符全都檢查完后，判斷棧是否為空羡棵，空則說明都匹配壹若，不空則證明有沒匹配的。
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;
}
