数组
- 数组是一种顺序存储结构，它需要一个连续的内存空间来存放数据。
- 数组随机访问一个元素时，可以通过下标直接访问任意元素，因为数组是连续存储的，所以就可以通过偏移量快速计算出元素的地址，因此数组访问元素的复杂度是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)
*/
