5、数据结构

1、最小栈—*

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。push(x) -- 将元素 x 推入栈中。pop() -- 删除栈顶的元素。top() -- 获取栈顶元素。getMin() -- 检索栈中的最小元素。

var MinStack = function() {
  this.stack = [];
  this.minStack = [];
};

MinStack.prototype.push = function(x) {
  if (this.stack.length === 0 || this.minStack[this.minStack.length - 1] >= x) {
    this.minStack.push(x);
  }
  this.stack.push(x);
};

MinStack.prototype.pop = function() {
  const elem = this.stack.pop();
    // 每次push和pop都是从尾部处理，所以遍历过的最小值都在minStack中了
  if (this.minStack.length > 0 && this.minStack[this.minStack.length - 1] === elem) {
    this.minStack.pop();
  }
};

MinStack.prototype.top = function() {
  return this.stack[this.stack.length - 1];
};

MinStack.prototype.getMin = function() {
  return this.minStack[this.minStack.length - 1];
};

var MinStack = function() {
    this.stack=[];
    
};

MinStack.prototype.push = function(x) {
    var min;
    if(this.stack.length==0){
        min=x;
    }else{
        var currentMin=this.stack[this.stack.length-1];
        min=currentMin<x?currentMin:x;
    }
    this.stack.push(x);
    this.stack.push(min);
    
};

MinStack.prototype.pop = function() {
    this.stack.pop();
    this.stack.pop();
};

MinStack.prototype.top = function() {
    return this.stack[this.stack.length-2];
};

MinStack.prototype.getMin = function() {
    return this.stack[this.stack.length-1];
};

2、LRU缓存机制—*

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity
    this.map = new Map()
  }
  get(key) {
    let val = this.map.get(key)
    if (typeof val === 'undefined') { return -1 }
    this.map.delete(key)
    this.map.set(key, val)
    return val
  }
  put(key, value) {
    if (this.map.has(key)) { 
      this.map.delete(key) 
    }
    this.map.set(key, value)
    let keys = this.map.keys()
    while (this.map.size > this.capacity) { this.map.delete(keys.next().value) }
  }
}

class LinkedList {
    constructor(key, val) {
        this.pre = null;
        this.next = null;
        this.key = key;
        this.val = val;
    }
    
}

var LRUCache = function(capacity) {
    this.map = new Map();
    this.capacity = capacity;
};

LRUCache.prototype.get = function(key) {
    if (this.capacity == 1) {
        return this.map.get(key) || -1;
    }
    
    const node = this.map.get(key);
    if (!node) {
        return -1;
    }
    
    if (this.capacity > 1 && this.map.size > 1 && node != this.head) {
        if (node.next) {
            node.pre.next = node.next;
            node.next.pre = node.pre;
        } else {
            this.tail = node.pre;
            this.tail.next = null;
        }
        
        node.next = this.head;
        this.head.pre = node;
        this.head = node;
        this.head.pre = null;
    }
    
    return node.val;
};

LRUCache.prototype.put = function(key, value) {
    if (this.capacity == 1) {
        this.map.clear();
        this.map.set(key, value);
        return;
    }
    
    const val = this.map.get(key);
    if (val) {
        val.val = value;
        if (this.map.size > 1 && val != this.head) {
            if (val.next) {
                val.pre.next = val.next;
                val.next.pre = val.pre;
            } else {
                this.tail = val.pre;
                this.tail.next = null;
            }
        
            val.next = this.head;
            this.head.pre = val;
            this.head = val;
            this.head.pre = null;
        }
        return;    
    }
    
    if (this.map.size == this.capacity) {
        this.map.delete(this.tail.key);
        this.tail = this.tail.pre;
        this.tail.next = null;
    }
    
    const node = new LinkedList(key, value);
    this.map.set(key, node); 
    if (!this.tail) {
        this.head = node;
        this.tail = node;
        return;
    }
    
    node.next = this.head;
    this.head.pre = node;
    this.head = node;
};