目录
BitMap
最小栈
AllOne
LRU
两个栈实现一个队列
BitMap
思路:
构造函数: 取商作为长度, 如果有余, 则长度 + 1
set 和 get 思路都是先取参数在 bitmap 中的 index 和 offset, 注意转化为 int, 然后进行相应的操作.
数据范围从 0 开始
- private long length;
- private static int[] bitsMap;
- // 构造函数中传入数据中的最大值
- public BitMap(long length) {
- this.length = length;
- // 根据长度算出, 所需数组大小
- // 即 length 除以 32 的商, 如果不能整除的话, 长度再加 1
- bitsMap = new int[(int) (length>> 5) + ((length & 31)> 0 ? 1 : 0)];
- }
- public void setBit(long index) {
- // 求出该 index 所在 bitMap 的下标
- int belowIndex = (int) (index>> 5);
- // 求出该值的偏移量 (求余)
- int offset = (int) (index & 31);
- int inData = bitsMap[belowIndex];
- // 0x01 为十六进制中的 1, 向左移动 offset 个位置后得出只有那个位置 a 为 1, 其他为 0 的二进制
- // 这个二进制数与 inData 进行 "或" 运算, 即把 inData 的二进制形式中 a 位置的数变为 1,
- bitsMap[belowIndex] = inData | (0x01 <<offset);
- }
- public int getBit(long index) {
- int intData = bitsMap[(int) (index>> 5)];
- int offset = (int) (index & 31);
- // 向右移动 offset, 与 0x01 进行 "与" 运算, 即判断 offset 那个位置的数是否与 1 相同, 即该数字存在, 从而返回 1
- return intData>> offset & 0x01;
- }
- public static void main(String[] args) {
- BitMap bitMap = new BitMap(32);
- bitMap.setBit(0);
- System.out.println(bitMap.getBit(0));
- System.out.println(bitMap.getBit(31)); // 32 就超范围了.
- // 结果为 1,0 表示存在和不存在
- }
最小栈
思路:
新建两个栈
push 和 pop 中, s1 照常执行. s2 判断其顶部元素是否大于等于 x, 如果是, 做相应操作. 在 push 中, 如果 s2 为空, 可以直接 push.
- // push
- s1.push(x);
- /** 注意 s2.peek()>= x 中的大于等于 */
- if (s2.isEmpty() || s2.peek()>= x) s2.push(x);
- // pop
- int x = s1.pop();
- if (s2.peek() == x) s2.pop();
- // top
- return s1.peek();
- // getMin
- return s2.peek();
- AllOne
- // 记录 key 和 key 的计数
- private Map<String, Integer> map;
- // 记录各层所包含的 key
- private List<Set<String>> list;
- // inc 和 dec: 先判断 key 是否存在, 然后取 key,list 中删除, 更新计数以及在 map 和 list 中的值和层
- // getMaxKey: 从后往前遍历 list, 只要 set 不为空, 就返回 set.iterator().next()
- // getMinKey: 从前往后遍历....
- // 遍历完都没有就返回 ""
- LRU
- // capacity,head,tail,map
- // 构造器: 实力化 map,head,tail 连接好两个节点
- public int get(int key) {
- Node node = map.get(key);
- if (node == null) return -1;
- moveToHead(node);
- return node.value;
- }
- private void moveToHead(Node node) {
- removeNode(node);
- addNode(node);
- }
- private void removeNode(Node node) {
- node.pre.next = node.next;
- node.next.pre = node.pre;
- }
- private void addNode(Node node) {
- node.pre = head;
- node.next = head.next;
- head.next.pre = node;
- head.next = node;
- }
- public void put(int key, int value) {
- Node node = map.get(key);
- if (node == null) {
- Node newNode = new Node();
- newNode.key = key;
- newNode.value = value;
- map.put(key, newNode);
- addNode(newNode);
- if (map.size()> capacity) {
- Node tail = popTail();
- map.remove(tail.key);
- }
- } else {
- node.value = value;
- moveToHead(node);
- }
- }
- private Node popTail() {
- Node node = tail.pre;
- removeNode(node);
- return node;
- }
两个栈实现一个队列
思路:
新建输入和输出栈
push 就 push 到 inputStack,pop 就先把 inputStack 中的元素放到 outputStack 后再从 outputStack 中 pop
peek 同样要执行 shiftStack, 返回时检查 outputStack 是否为空, 是返回 0
shiftStack: 如果 outputStack 为空, 就不断把 inputStack 中的元素放到 outputStack 中
empty 的判断是 inputStack 和 outputStack 同时为空
来源: http://www.bubuko.com/infodetail-2880211.html