Queue
FIFO first in first out 只要满足先进先出，那就是一个queue
Stack: push(),pop(),top()
LIFO last in first out
怎么用两个stack来模拟一个queue呢？
Solution:
Stack1: for new element, push to stack1
Stack2: to pop out 1st element:
Case1: if stack2 is empty, then we move all the element from stack1 to stack2, then pop from stack2
Case2: if stack2 is not empty, then just pop from stack2
Time: Push O(1), Pop O(n)
But when we consisdered Amortized time complexity of Pop() = O(1)
怎么用stack来实现时间复杂度为O(1)的min()函数？
Solution:
keep the add() and remove() in sync between stack1 and stack2
Stack1: for new element, push to stack1
Stack2: to push new element:
Case1: if stack2 is empty, then we push same element to stack2.
Case2: if stack2 is not empty, then we check if new element is smaller then stack2.top(), if so, push new element to stack2, else push stack2.top() to stack2.
Follow up question: 怎么优化空间复杂度，假设很多stack1内的元素是重复元素。
那么只需要再stack2中存push入这个数时的stack1的size即可，即说明stack1对应这个最小数时的index。
怎么用多个stack来排序数字?
怎么用多个stack来编写一个de-queue?
期望O(1)的摊销时间复杂度。
逆波兰表达式(stack的实践)
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new ArrayDeque<>();
for(String token: tokens){
switch (token){
case “+” -> {
int right = stack.pop();
int left = stack.pop();
stack.push(right + left);
}
case “-” -> {
int right = stack.pop();
int left = stack.pop();
stack.push(left – right);
}
case “*” -> {
int right = stack.pop();
int left = stack.pop();
stack.push(left * right);
}
case “/” -> {
int right = stack.pop();
int left = stack.pop();
stack.push(left / right);
}
default -> stack.push(Integer.parseInt(token));
}
}
return stack.pop();
}
}
Linked List
When you want to de-reference a ListNode, make sure it is not a NULL pointer
Never ever lost the control of the head pointer of the LinkedList.
经典题目：
反转链表
怎么找到linked list中间的node: 快慢指针
快慢指针来判定一个linkedlist是否有环
怎么在一个sorted linked list insert 一个node
merge 两个sorted linkedlist into one long sorted linked list
N1 -> N2 ->N3 -> … – > Nn Leetcode 147
N1 -> Nn -> N2 -> Nn-1
发表回复