leetCode刷题记录-链表

发表于 | 分类于 ， ，

146.LRU缓存算法

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

1
2
3
4
5
6
7
8
9
10
11
实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lru-cache
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

利用链表保持时序，利用hash存储节点

调试了好久，终于搞定了，需要仔细

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class ListNode {
  constructor(key, val, pre=null, next=null){
    this.key = key;
    this.val = val;
    this.pre = pre;
    this.next = next;
  }
}

var LRUCache = function (capacity) {
  // 最大长度
  this.capacity = capacity
  this.hash = new Map()
  // 计数器
  this.count = 0
  // 虚拟头部
  this.dummyHead = new ListNode(-1, -1)
  // 虚拟尾部
  this.dummyTail = new ListNode(-1, -1)
  this.dummyHead.next = this.dummyTail
  this.dummyTail.pre = this.dummyHead
  // 头部
  this.listHead = this.dummyHead
  // 尾部
  this.listTail = this.dummyTail
};

LRUCache.prototype.get = function(key) {
  if (this.hash.has(key)) {
    const existNode = this.hash.get(key)
    // 从原位置删除
    existNode.next.pre = existNode.pre
    existNode.pre.next = existNode.next
    // 把节点插入虚拟尾部之前
    this.insertBeforeTail(existNode)
    return this.hash.get(key).val
  }else{
    return -1
  }
};

LRUCache.prototype.put = function(key, value) {
  if (this.hash.has(key)) { // 已存在
    const existNode = this.hash.get(key)
    // 从原位置删除
    existNode.next.pre = existNode.pre
    existNode.pre.next = existNode.next
    // 题目有个变更要求
    existNode.val = value
    // 把节点插入虚拟尾部之前
    this.insertBeforeTail(existNode)
  } else { // 未存在
    const newNode = new ListNode(key, value)
    if (this.count < this.capacity) { // 容量没满
      // 把新节点插入虚拟尾部之前
      this.insertBeforeTail(newNode)
      // 用key记录节点
      this.hash.set(key, newNode)
      // 计数
      this.count++
    } else { // 容量满了
      // 删除节点记录
      this.hash.delete(this.listHead.next.key)
      // 把虚拟头部后边节点删除
      this.listHead.next = this.listHead.next.next
      this.listHead.next.pre = this.listHead 
      // 把新节点插入虚拟尾部之前   
      this.insertBeforeTail(newNode)
      // 用key记录节点
      this.hash.set(key, newNode)
    }
  }
};
LRUCache.prototype.insertBeforeTail = function (newNode) {
  // 把节点插入虚拟尾部之前
  this.listTail.pre.next = newNode
  newNode.pre = this.listTail.pre
  newNode.next = this.listTail
  this.listTail.pre = newNode
}

利用map数据结构

利用map特别简单

map数据结构兼顾有序性和hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var LRUCache = function(capacity) {
    this.capacity = capacity;
    this.map = new Map();
};

LRUCache.prototype.get = function(key) {
    if(this.map.has(key)){
        let temp=this.map.get(key)
         this.map.delete(key);
         this.map.set(key, temp);
         return temp
    }else{
        return -1
    }
};

LRUCache.prototype.put = function(key, value) {
    if(this.map.has(key)){
        this.map.delete(key);
    }
    this.map.set(key,value);
    if(this.map.size > this.capacity){
     
        this.map.delete(this.map.keys().next().value);
    }
};

380.O(1) 时间插入、删除和获取随机元素

实现RandomizedSet 类：

RandomizedSet() 初始化 RandomizedSet 对象
bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
示例：

输入
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
输出
[null, true, false, true, 2, true, false, 2]

解释
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。
randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。
randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/insert-delete-getrandom-o1
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

利用map进行设计，利用水塘抽样算法实现等概率

但是随机获取 时间复杂度不是O1,而是O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
var RandomizedSet = function() {
  this.hash = new Map()
};

RandomizedSet.prototype.insert = function(val) {
  if (this.hash.has(val)) {
    return false
  } else {
    this.hash.set(val, true)
    return true
  }
};

RandomizedSet.prototype.remove = function(val) {
  if (this.hash.has(val)) {
    this.hash.delete(val)
    return true
  } else {
    return false
  }
};

RandomizedSet.prototype.getRandom = function() {
  let count = 1;
  let iterator = this.hash.keys();
  let result = null;
  while (true) {
    const { value, done } = iterator.next()
    if (done) {
      break;
    }
    if (Math.floor(Math.random() * count) === 0) {
      result = value
    }
    count++
  }
  return result
};

利用hash实现O1存储删除，数组实现O1等概率访问

难点还是在于理解和设计，熟悉数据结构的基础方法时间复杂度

删除的前提是访问

数组某个元素和尾部交换后删除，O1

数组push 01

代码重点在于交换时，hash对应的index也需要考虑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
var RandomizedSet = function() {
  this.hash = Object.create(null, {})
  this.array = []
};

RandomizedSet.prototype.insert = function(val) {
  if (typeof this.hash[val] !== "undefined") {
    return false
  } else {
    this.array.push(val)
    // 存储位置
    this.hash[val] = this.array.length - 1
    return true
  }
};

RandomizedSet.prototype.remove = function(val) {
  if (typeof this.hash[val] !== "undefined") {
    // 待删除元素的索引
    const index = this.hash[val]
    // 对末尾元素进行操作
    const tailValue = this.array[this.array.length - 1]
    this.hash[tailValue] = index
    this.array[index] = tailValue
    // 删除
    this.array.pop()
    delete this.hash[val]
    return true
  } else {
    return false
  }
};

RandomizedSet.prototype.getRandom = function() {
  return this.array[Math.floor(Math.random()*this.array.length)]
};

232.用栈实现队列

题解简单易懂，主要是需要搞懂push pop穿插如果保证有序性就可以了,pop必须一次性从inStack全部转移过来才能保持顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
var MyQueue = function() {
  this.inStack = []
  this.outStack = []
};

MyQueue.prototype.push = function(x) {
  this.inStack.push(x)
};

MyQueue.prototype.pop = function() {
  if(!this.outStack.length){
    while(this.inStack.length){
      this.outStack.push(
        this.inStack.pop()
      )
    }
  }
  return this.outStack.pop()
};

MyQueue.prototype.peek = function() {
  if(!this.outStack.length){
    while(this.inStack.length){
      this.outStack.push(
        this.inStack.pop()
      )
    }
  }
  return this.outStack[this.outStack.length-1]
};

MyQueue.prototype.empty = function() {
  return !this.inStack.length && !this.outStack.length
};

225. 用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
var MyStack = function() {
  this.list = []
  this.tempList = []
};

MyStack.prototype.push = function(x) {
  if(this.list.length){
    while(this.list.length){
      this.tempList.push(this.list.shift())
    }
    this.list.push(x)
    while(this.tempList.length){
      this.list.push(this.tempList.shift())
    }
  }else{
    this.list.push(x)
  }
};

MyStack.prototype.pop = function() {
  return this.list.shift()
};

MyStack.prototype.top = function() {
  return this.list[0]
};

MyStack.prototype.empty = function() {
  return !this.list.length
};