链表和数组

数组

• 数组是一种顺序存储结构，它需要一个连续的内存空间来存放数据。
• 数组随机访问一个元素时，可以通过下标直接访问任意元素，因为数组是连续存储的，所以就可以通过偏移量快速计算出元素的地址，因此数组访问元素的复杂度是O(1)。
• 数组插入和删除需要移动大量其他元素， 因为他们是顺序存储的， 所以当插入或删除的时候，都需要给它的到来腾位置，所以复杂度是O(n)。

链表

• 链表是一种链式存储结构，它不需要连续的内存空间，而是通过指针将一系列零散的内存空间串联起来。
• 链表随机访问一个元素时，我们需要从节点开始顺序遍历整个链表，直到找个目标元素，因为它是非连续存储的，找的当前元素必须找到上一个元素，找到上一个元素必须又找到更上一级的元素，以此类推。 因此链表随机访问元素的复杂度是O(n)。
• 链表插入和删除元素只需要修改相邻节点足以，所以复杂度是O(1)。

使用JS实现一个链表

• 首先链表我们知道的它是按照顺序，上一个指向下一个的，所以我们需要有个类来生成链表的数据结构。

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

• 然后开始实现一个简单的链表，append和print方法。当我们第一次append的时候，这时候head是没有值的，所以我们需要生成一个head，然后到后面添加的时候，我们需要浅拷贝一个head，然后while循环，找到这个链表的最后一个节点，把当前的值赋值给最后一个节点的next。

class LinkNodeList {
  constructor() {
    this.head = null;
  }

  append(val) {
    const newNode = new Node(val);
    if (!this.head) {
      this.head = newNode;
      return;
    }

    let current = this.head;
    //找到链表最后一个节点
    while (current.next) {
      current = current.next;
    }

    //给最后一个节点的next赋值
    current.next = newNode;
  }

  print() {
    let current = this.head;
    let ret = '';
    if (!this.head) {
      console.log('No data');
      return;
    }
    while (current) {
      ret += `${current.val} -> `;
      current = current.next;
    }
    console.log(ret);
  }
}

const linkList = new LinkNodeList();

linkList.append(1);
linkList.append(2);
linkList.append(3);
linkList.append(4);
linkList.print();

203. 移除链表元素

image.png

这里有一个新的概念，哨兵元素，就在链表的头，设置一个哨兵，它是肯定存在的。然后使用while循环，如果next值等于这个val，那么就指向下下个。

var removeElements = function (head, val) {
    let ele = {
        next: head
    }
    let p = ele
    while (p.next) {
        if (p.next.val === val) {
            p.next = p.next.next
        } else {
            p = p.next
        }
    }
    return ele.next
}; 

141. 环形链表

image.png

这个题就有两个思路

• 我们每次将值存在集合中，当集合中存在重复的时候，就return true，否则就往里面添加。
• 快慢指针，如果是环形，两者终能相遇。

var hasCycle = function (head) {
    // const cache = new Set()
    // while (head) {
    //     if (cache.has(head)) {
    //         return true;
    //     } else {
    //         cache.add(head)
    //     }
    //     head = head.next
    // }
    // return false

    let slow = head
    let fast = head
    while (fast && fast.next) {
        fast = fast.next.next
        slow = slow.next
        if(slow === fast) return true
    }
    return false
};

146. LRU 缓存

首先我们需要知道LRU缓存是什么，LRU 是 Least Recently Used（最近最少使用）的缩写，是一种常用的缓存淘汰策略。当我们经常使用的我们会放在最前面，然后当超过最大缓存数的时候，我们会淘汰最不常使用的，也就是最后一项数据。

我们在JS中，我们可以使用到Map的数据结构，因为这个Map，当我们set的时候，他是存储到末尾的，所以我们可以跟我们上述介绍的概念反过来。

当我们get读取缓存的时候，如果我们缓存有值，那么我们就delete当前key，然后重新set。这样就保证我们最近使用的值在末尾。
当我们put存值的时候，如果有值，我们同样需要删除当前key，然后重新set， 当我们需要Put一个新的值，但是大于缓存数的时候，我们就可以淘汰Map数据结构的第一个值（this.cache.keys().next().value），然后再set新的值

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
    this.cache = new Map()
    this.max = capacity
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
    if (this.cache.has(key)) {
        const tmp = this.cache.get(key)
        this.cache.delete(key)
        this.cache.set(key,tmp)
        return tmp
    }
    return -1
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
    if (this.cache.has(key)) {
        this.cache.delete(key)
    } else if (this.cache.size >= this.max) {
        this.cache.delete(this.cache.keys().next().value)
    }
    this.cache.set(key, value)
};


/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */