數(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)開(kāi)始順序遍歷整個(gè)鏈表，直到找個(gè)目標(biāo)元素，因?yàn)樗欠沁B續(xù)存儲(chǔ)的，找的當(dāng)前元素必須找到上一個(gè)元素，找到上一個(gè)元素必須又找到更上一級(jí)的元素，以此類(lèi)推。 因此鏈表隨機(jī)訪問(wèn)元素的復(fù)雜度是O(n)。
• 鏈表插入和刪除元素只需要修改相鄰節(jié)點(diǎn)足以，所以復(fù)雜度是O(1)。

使用JS實(shí)現(xiàn)一個(gè)鏈表

• 首先鏈表我們知道的它是按照順序，上一個(gè)指向下一個(gè)的，所以我們需要有個(gè)類(lèi)來(lái)生成鏈表的數(shù)據(jù)結(jié)構(gòu)。

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

• 然后開(kāi)始實(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. 移除鏈表元素

image.png

這里有一個(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)形鏈表

image.png

這個(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（最近最少使用）的縮寫(xiě)，是一種常用的緩存淘汰策略。當(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)
 */