结构设计
Last updated
Last updated
栈：先进后出FILO
队列：先进先出FIFO
准备两个栈，一个数据栈data,一个辅助栈help
push时，只需要向help栈中推
pop时，只要去data的栈顶元素，即data.pop(),但是data栈没有元素了需要怎样?将help栈的元素不断往data栈推，推完为止，如果data,help栈均无元素，报错
peek时，与pop的过程一样，只是在返回的时候，data.peek()
empty，当data,help均为空时，返回true
class MyQueue {
Stack<Integer> data;
Stack<Integer> help;
public MyQueue() {
data = new Stack<>();
help = new Stack<>();
}
public void push(int x) {
help.push(x);
}
public int pop() {
if (data.isEmpty() && help.isEmpty()) throw new RuntimeException("empty queue");
if (data.isEmpty()) {
while (!help.isEmpty()) data.push(help.pop());
}
return data.pop();
}
public int peek() {
if (data.isEmpty() && help.isEmpty()) throw new RuntimeException("empty queue");
if (data.isEmpty()) {
while (!help.isEmpty()) data.push(help.pop());
}
return data.peek();
}
public boolean empty() {
return data.isEmpty() && help.isEmpty();
}
}参考「232. 用栈实现队列」
class CQueue {
Stack<Integer> data;
Stack<Integer> help;
public CQueue() {
data = new Stack<>();
help =new Stack<>();
}
public void appendTail(int value) {
help.push(value);
}
public int deleteHead() {
//两个栈的数据都为空，返回-1
if(data.isEmpty() && help.isEmpty()) return -1;
//data的数据没有了从help中拿
if(data.isEmpty()){
while(!help.isEmpty()) data.push(help.pop());
}
//弹出data的栈顶元素
return data.pop();
}
} class CQueue {
Deque<Integer> data;
Deque<Integer> help;
public CQueue() {
data = new ArrayDeque<>();
help = new ArrayDeque<>();
}
public void appendTail(int value) {
help.addFirst(value);
// help.push(value);
}
public int deleteHead() {
if (data.isEmpty() && help.isEmpty()) return -1;
if (data.isEmpty()) {
while (!help.isEmpty()) {
// data.addFirst(help.pollFirst());
data.push(help.pop());
}
}
// return data.pollFirst();
return data.pop();
}
}队列是先进先出，栈是先进后出，在top()方法中，为了避免，数据拷贝，有一个swap()的动作，data与help的存储顺序是一样的
因为data队列的元素始终存在，判断栈是否为空的时候，只需要关注size(data)==0
top()与pop()方法只是在弹出data的最后一个元素的时候是否要继续放回help队列
class MyStack {
private Queue<Integer> data;
private Queue<Integer> help;
/**
* Initialize your data structure here.
*/
public MyStack() {
data = new LinkedList<>();
help = new LinkedList<>();
}
/**
* Push element x onto stack.
*/
public void push(int x) {
data.add(x);
}
/**
* Removes the element on top of the stack and returns that element.
*/
public int pop() {
if (data.isEmpty()) throw new RuntimeException("stack empty");
while (data.size() != 1) help.add(data.poll());
int res = data.poll();
swap();
return res;
}
/**
* Get the top element.
*/
public int top() {
if (data.isEmpty()) throw new RuntimeException("stack empty");
while (data.size() != 1) help.add(data.poll());
int res = data.poll();
help.add(res);
swap();
return res;
}
private void swap() {
Queue tmp = help;
help = data;
data = tmp;
}
/**
* Returns whether the stack is empty.
*/
public boolean empty() {
return data.size() == 0;
}
}shift()方法是为top() 与pop()方法准备的，做一件事：就是弹出队头到倒数第2个队尾元素的，将其送到队列的尾部，在执行top() 与pop()，弹出queue的队头元素，如果是top()，继续保留这个元素，pop()时扔掉
class MyStack {
private Queue<Integer> queue;
/**
* Initialize your data structure here.
*/
public MyStack() {
queue = new LinkedList<>();
}
/**
* Push element x onto stack.
*/
public void push(int x) {
queue.offer(x);
}
/**
* Removes the element on top of the stack and returns that element.
*/
public int pop() {
shift();
int res = queue.poll();
return res;
}
/**
* Get the top element.
*/
public int top() {
shift();
int res = queue.poll();
queue.offer(res);
return res;
}
public void shift() {
int size = queue.size();
for (int i = 0; i < size - 1; i++) {
queue.offer(queue.poll());
}
}
/**
* Returns whether the stack is empty.
*/
public boolean empty() {
return queue.isEmpty();
}
}基础版辅助栈，准备一个data, 数据栈，准备一个help 辅助栈
其中data的存数据的，help辅助栈用来存最小值，在push操作时，help如果栈顶元素大于待push的元素，将待push的元素塞进help中，如果不是，则重复塞一次help的栈顶元素，注意help为空的时候特殊处理下
准备两个栈，data和help，做push操作时，需要保持help栈顶的元素始终最小，data的数据正常推入，help栈顶维持最小，在执行getMin方法的时候，返回help的栈顶元素
class MinStack {
private Stack<Integer> data;
private Stack<Integer> help;
/**
* initialize your data structure here.
*/
public MinStack() {
data = new Stack<>();
help = new Stack<>();
}
public void push(int x) {
data.push(x);
if (help.isEmpty()) help.push(x);
else if (help.peek() < x) help.push(help.peek());
else help.push(x);
}
public void pop() {
if (data.isEmpty()) throw new RuntimeException("stack empty");
data.pop();
help.pop();
}
public int top() {
if (data.isEmpty()) throw new RuntimeException("stack empty");
return data.peek();
}
public int getMin() {
if (data.isEmpty()) throw new RuntimeException("stack empty");
return help.peek();
}
}升级版本辅助栈，当push 进去的时候，
当help的栈顶元素比新来的元素小的时候，这个时候保持help不变
当help的栈顶元素大于等于新来的元素时，help同步要推一份新的元素进来
当help元素为空的时候，也需要往里推
pop的时候，pop的元素是否和help 的元素有重叠，有就将help的元素pop出去，没有就维持不动，data栈正常pop
class MinStack {
Stack<Integer> data;
Stack<Integer> help;
/**
* initialize your data structure here.
*/
public MinStack() {
data = new Stack<>();
help = new Stack<>();
}
public void push(int x) {
if (help.isEmpty() || help.peek() >= x) {
help.push(x);
}
data.push(x);
}
public void pop() {
if (data.isEmpty()) throw new RuntimeException("The stack is empty");
int pop = data.pop();
if (pop == help.peek()) {
help.pop();
}
}
public int top() {
if (data.isEmpty()) throw new RuntimeException("The stack is empty");
return data.peek();
}
public int getMin() {
if (help.isEmpty()) throw new RuntimeException("The stack is empty");
return help.peek();
}
}class NumArray {
class TreeNode {
int val;
int start;
int end;
TreeNode left;
TreeNode right;
public TreeNode(int start, int end) {
this.start = start;
this.end = end;
}
}
TreeNode root = null;
private TreeNode buildTree(int[] nums, int start, int end) {
if (start > end) return null;
TreeNode curr = new TreeNode(start, end);
if (start == end) curr.val = nums[start];
else {
int mid = start + (end - start) / 2;
curr.left = buildTree(nums, start, mid);
curr.right = buildTree(nums, mid + 1, end);
curr.val = curr.left.val + curr.right.val;
}
return curr;
}
public NumArray(int[] nums) {
root = buildTree(nums, 0, nums.length - 1);
}
public void update(int i, int val) {
updateTree(root, i, val);
}
public void updateTree(TreeNode node, int i, int val) {
if (node.start == node.end) {
node.val = val;
} else {
int mid = node.start + (node.end - node.start) / 2;
if (i <= mid) updateTree(node.left, i, val);
else updateTree(node.right, i, val);
node.val = node.left.val + node.right.val;
}
}
public int sumRange(int i, int j) {
return queryTree(root, i, j);
}
public int queryTree(TreeNode node, int i, int j) {
System.out.println(String.format("i:%d,j:%d", i, j));
System.out.println(node);
System.out.println(String.format("Node.val:%d", node.val));
if (node.start == i && node.end == j) return node.val;
else {
int mid = node.start + (node.end - node.start) / 2;
if (j <= mid) {
return queryTree(node.left, i, j);
} else if (i >= mid + 1) {
return queryTree(node.right, i, j);
} else {
return queryTree(node.left, i, mid) + queryTree(node.right, mid + 1, j);
}
}
}
}class RandomizedSet {
Map<Integer, Integer> map = new HashMap<>();//k:插入的值，v:list的size
List<Integer> list = new ArrayList<>();
Random random = new Random();
/**
* Initialize your data structure here.
*/
public RandomizedSet() {
}
/**
* Inserts a value to the set. Returns true if the set did not already contain the specified element.
*/
public boolean insert(int val) {
if (map.containsKey(val)) return false;
map.put(val, list.size());
list.add(val);
return true;
}
/**
* Removes a value from the set. Returns true if the set contained the specified element.
*/
public boolean remove(int val) {
if (!map.containsKey(val)) return false;
int idx = map.get(val);//找到val的索引
int lastEle = list.get(list.size() - 1);//list中的最后一个元素
list.set(idx, lastEle);//当前的val用lastEle替换
map.put(lastEle, idx);//更新关系
//移除元素
list.remove(list.size() - 1);
map.remove(val);
return true;
}
/**
* Get a random element from the set.
*/
public int getRandom() {
int ranIdx = random.nextInt(list.size());
return list.get(ranIdx);
}
}需要一个哈希双端链表，DoubleLinkedNode
这个双端链表有下面的几个属性
class DoubleLinkedNode {
int key, value;//k,v
DoubleLinkedNode pre, next;//前驱接节点，后继节点
public DoubleLinkedNode(int key, int value) {
this.key = key;
this.value = value;
}
public DoubleLinkedNode() {
}
}将新加入的节点插入到双端链表的头部位置
addFirst(node)
/**
* 将节点加入到双向链表的开头的位置
*/
public void addFirst(DoubleLinkedNode node) {
node.pre = head;//1.当前节点的前驱结点指向head节点
node.next = head.next;//2.当前节点的后继节点指向head的后继节点
head.next.pre = node;//3.head节点的后继节点的前驱结点指向当前节点
head.next = node;//4.head的后继节点指向当前节点
}移除一个节点
removeNode(node)
/**
* 移除一个普通的节点
*
* @param node
*/
public void removeNode(DoubleLinkedNode node) {
DoubleLinkedNode next = node.next;
DoubleLinkedNode pre = node.pre;
pre.next = next;
next.pre = pre;
}弹出最末尾的节点，并返回最后的节点
popLast
/**
* 弹出最末尾的节点并将改节点返回
*
* @return
*/
public DoubleLinkedNode popLast() {
DoubleLinkedNode last = tail.pre;
removeNode(last);
return last;
}将一个已经在链表中存在的节点移动到链表的开头
moveToHead(node)
先移除这个节点移除，再将这个节点添加到链表的开头
/**
* 将当前节点移动到最头部位置
*
* @param node
*/
public void moveToHead(DoubleLinkedNode node) {
removeNode(node);
addFirst(node);
}下面开始
LRU
初始化
注意head节点和tail节点需要new出来
get(key)
如果cache中不存在key,返回-1
如果cache中存在，取出这个节点，将节点moveToHead，返回节点的值
put(k,v)
取出节点，分节点存在与否讨论：
节点不存在：新创建节点，将该节点插入到链表的头部，并将其put进cache中
做一个额外的判断：如果当前的cache的大小大于capacity，需要移除最末尾的节点，链表和$cache$都要做移除操作
节点存在:返回节点的值，将节点移动到链表头部
class LRUCache {
DoubleLinkedNode head, tail;//Node的收尾节点
int capacity;//容量
Map<Integer, DoubleLinkedNode> cache;//<k,v> k是key，v是key生成的node
/**
* 初始化
*
* @param capacity
*/
public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new HashMap<>();
this.head = new DoubleLinkedNode();
this.tail = new DoubleLinkedNode();
this.head.next = tail;
this.tail.pre = head;
}
public int get(int key) {
if (!cache.containsKey(key)) return -1;
DoubleLinkedNode node = cache.get(key);
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DoubleLinkedNode node = cache.get(key);
if (node == null) {
node = new DoubleLinkedNode(key, value);
addFirst(node);
cache.put(key, node);
if (cache.size() > capacity) {
DoubleLinkedNode last = popLast();
cache.remove(last.key);
}
} else {
node.value = value;
moveToHead(node);
}
}
}class RecentCounter {
Deque<Integer> q;
public RecentCounter() {
q = new LinkedList<>();
}
public int ping(int t) {
q.offerLast(t);
while (q.peek() < t - 3000) q.pollFirst();
return q.size();
}
}另
class RecentCounter {
PriorityQueue<Integer> pq;
int N = 3000;
public RecentCounter() {
pq = new PriorityQueue<>();
}
public int ping(int t) {
while (!pq.isEmpty() && pq.peek() < t - N) {
pq.poll();
}
pq.offer(t);
return pq.size();
}
}class Bank {
long[] balance;
int capacity;
public Bank(long[] balance) {
this.balance = new long[balance.length + 1];
this.capacity = balance.length + 1;
for (int i = 0; i < balance.length; i++) {
this.balance[i + 1] = balance[i];
}
}
public boolean transfer(int account1, int account2, long money) {
if (account1 > capacity || account2 > capacity) return false;
if (this.balance[account1] < money) return false;
this.balance[account1] -= money;
this.balance[account2] += money;
return true;
}
public boolean deposit(int account, long money) {
if (account > capacity) return false;
this.balance[account] += money;
return true;
}
public boolean withdraw(int account, long money) {
if (account > capacity) return false;
if (this.balance[account] < money) return false;
this.balance[account] -= money;
return true;
}
}注释的代码写法是等价的，详细参考
