數(shù)組
- 數(shù)組是一種順序存儲(chǔ)結(jié)構(gòu)陶耍,它需要一個(gè)連續(xù)的內(nèi)存空間來(lái)存放數(shù)據(jù)奋蔚。
- 數(shù)組隨機(jī)訪問(wèn)一個(gè)元素時(shí),可以通過(guò)下標(biāo)直接訪問(wèn)任意元素物臂,因?yàn)閿?shù)組是連續(xù)存儲(chǔ)的旺拉,所以就可以通過(guò)偏移量快速計(jì)算出元素的地址,因此數(shù)組訪問(wèn)元素的復(fù)雜度是O(1)棵磷。
- 數(shù)組插入和刪除需要移動(dòng)大量其他元素蛾狗, 因?yàn)樗麄兪琼樞虼鎯?chǔ)的, 所以當(dāng)插入或刪除的時(shí)候仪媒,都需要給它的到來(lái)騰位置沉桌,所以復(fù)雜度是O(n)谢鹊。
鏈表
- 鏈表是一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),它不需要連續(xù)的內(nèi)存空間留凭,而是通過(guò)指針將一系列零散的內(nèi)存空間串聯(lián)起來(lái)佃扼。
- 鏈表隨機(jī)訪問(wèn)一個(gè)元素時(shí),我們需要從節(jié)點(diǎn)開始順序遍歷整個(gè)鏈表蔼夜,直到找個(gè)目標(biāo)元素兼耀,因?yàn)樗欠沁B續(xù)存儲(chǔ)的,找的當(dāng)前元素必須找到上一個(gè)元素求冷,找到上一個(gè)元素必須又找到更上一級(jí)的元素瘤运,以此類推。 因此鏈表隨機(jī)訪問(wèn)元素的復(fù)雜度是O(n)匠题。
- 鏈表插入和刪除元素只需要修改相鄰節(jié)點(diǎn)足以拯坟,所以復(fù)雜度是O(1)。
使用JS實(shí)現(xiàn)一個(gè)鏈表
- 首先鏈表我們知道的它是按照順序韭山,上一個(gè)指向下一個(gè)的郁季,所以我們需要有個(gè)類來(lái)生成鏈表的數(shù)據(jù)結(jié)構(gòu)。
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
- 然后開始實(shí)現(xiàn)一個(gè)簡(jiǎn)單的鏈表钱磅,append和print方法梦裂。當(dāng)我們第一次append的時(shí)候,這時(shí)候head是沒(méi)有值的续搀,所以我們需要生成一個(gè)head塞琼,然后到后面添加的時(shí)候,我們需要淺拷貝一個(gè)head禁舷,然后while循環(huán),找到這個(gè)鏈表的最后一個(gè)節(jié)點(diǎn)毅往,把當(dāng)前的值賦值給最后一個(gè)節(jié)點(diǎn)的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;
//找到鏈表最后一個(gè)節(jié)點(diǎn)
while (current.next) {
current = current.next;
}
//給最后一個(gè)節(jié)點(diǎn)的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. 移除鏈表元素
這里有一個(gè)新的概念,哨兵元素攀唯,就在鏈表的頭洁桌,設(shè)置一個(gè)哨兵,它是肯定存在的侯嘀。然后使用while循環(huán)另凌,如果next值等于這個(gè)val,那么就指向下下個(gè)戒幔。
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. 環(huán)形鏈表
這個(gè)題就有兩個(gè)思路
- 我們每次將值存在集合中吠谢,當(dāng)集合中存在重復(fù)的時(shí)候,就return true诗茎,否則就往里面添加工坊。
- 快慢指針,如果是環(huán)形,兩者終能相遇王污。
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(最近最少使用)的縮寫,是一種常用的緩存淘汰策略昭齐。當(dāng)我們經(jīng)常使用的我們會(huì)放在最前面尿招,然后當(dāng)超過(guò)最大緩存數(shù)的時(shí)候,我們會(huì)淘汰最不常使用的阱驾,也就是最后一項(xiàng)數(shù)據(jù)就谜。
我們?cè)贘S中,我們可以使用到Map的數(shù)據(jù)結(jié)構(gòu)啊易,因?yàn)檫@個(gè)Map吁伺,當(dāng)我們set的時(shí)候,他是存儲(chǔ)到末尾的租谈,所以我們可以跟我們上述介紹的概念反過(guò)來(lái)篮奄。
當(dāng)我們get讀取緩存的時(shí)候,如果我們緩存有值割去,那么我們就delete當(dāng)前key窟却,然后重新set。這樣就保證我們最近使用的值在末尾呻逆。
當(dāng)我們put存值的時(shí)候夸赫,如果有值开缎,我們同樣需要?jiǎng)h除當(dāng)前key诉瓦,然后重新set, 當(dāng)我們需要Put一個(gè)新的值化戳,但是大于緩存數(shù)的時(shí)候宜雀,我們就可以淘汰Map數(shù)據(jù)結(jié)構(gòu)的第一個(gè)值(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)
*/