leetcode-142-146

leetcode142题146题:

leetcode142题(环形链表):

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

示例:

示例

示例

解答(双指针法):

假设非环部分的长度是x,从环起点到相遇点的长度是y。环的长度是c。
现在走的慢的那个指针走过的长度肯定是x+n1c+y,走的快的那个指针的速度是走的慢的那个指针速度的两倍。这意味着走的快的那个指针走的长度是2(x+n1c+y)。

还有一个约束就是走的快的那个指针比走的慢的那个指针多走的路程一定是环长度的整数倍。根据上面那个式子可以知道2(x+n1c+y)-x+n1c+y=x+n1c+y=n2c。

所以有x+y=(n2-n1)*c,这意味着什么?我们解读下这个数学公式:非环部分的长度+环起点到相遇点之间的长度就是环的整数倍。这在数据结构上的意义是什么?现在我们知道两个指针都在离环起点距离是y的那个相遇点,而现在x+y是环长度的整数倍,这意味着他们从相遇点再走x距离就刚刚走了很多圈,这意味着他们如果从相遇点再走x就到了起点。
那怎么才能再走x步呢?答:让一个指针从头部开始走,另一个指针从相遇点走,等这两个指针相遇那就走了x步此时就是环的起点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var detectCycle = function(head) {
var slow = head;
var fast = head;
while(fast!=null&&fast.next!=null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){//slow和fast能够相遇就表明必定有环存在
fast = head;//让fast重新从头指针开始,再次与slow相遇的位置就是环起点的位置
while(slow!=fast){
slow = slow.next;
fast = fast.next;
}
return fast;
}
}
return null;
};

leetcode146题(LRU缓存机制):

运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。

示例:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4

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

使用js的对象和双向链表解决;使用js的Map对象解决

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
//利用对象和双向链表解决
/**
* @param {number} capacity
*/
var LRUCache = function(capacity) {
this.capacity = capacity;
this.obj = {};//obj中存储链表节点
//新建两个节点,head和tail,head后面存旧的元素,tail前面存新的元素
this.head = new listNode();
this.tail = new listNode();
//初始化链表
this.head.next = this.tail;
this.tail.prev = this.head;
};
var listNode = function(key,val){//定义双向链表节点
this.key = key;
this.val = val;
this.prev = null;
this.next = null;
}
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
if(this.obj[key]!=undefined){//如果存在于对象中,将其放在链表末尾,同时返回其对应的值
this.moveToTail(key);
return this.obj[key].val;
}
return -1;//否则直接返回-1
};

/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {
if(this.obj[key]!=undefined){//如果存在于对象中,就不需要在链表中添加新的节点
//直接更新对象中的对应值,直接将其放在链表尾部即可
this.obj[key].val = value;
this.moveToTail(key);
}else{
var length = 0;
for(var prop in this.obj){//计算对象长度
length++;
}
if(length==this.capacity){//如果长度与容量相等,需要删除链表中的节点
delete this.obj[this.head.next.key];
this.head.next = this.head.next.next;
this.head.next.prev = this.head;
}
var newNode = new listNode(key,value);//删除之后,将新的节点添加到链表尾部
this.obj[key] = newNode;
newNode.prev = this.tail.prev;
newNode.next = this.tail;
this.tail.prev.next = newNode;
this.tail.prev = newNode;
}
};

//将节点移动到链表尾部的函数
LRUCache.prototype.moveToTail = function(key) {
node = this.obj[key];
node.prev.next = node.next;
node.next.prev = node.prev;
node.prev = this.tail.prev;
node.next = this.tail;
this.tail.prev.next = node;
this.tail.prev = node;
}
/**
* 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)
*/
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
//利用js的map数据结构解决
var LRUCache = function(capacity) {
this.cache = new Map();//一个Map对象在迭代时会根据对象中元素的插入顺序来进行
this.capacity = capacity;
}
LRUCache.prototype.get = function(key, value) {
let cache = this.cache;
if (cache.has(key)) {
let temp = cache.get(key)
cache.delete(key);
cache.set(key, temp);//设置新值,相当于插入,那么会在最前面
return temp;
} else {
return -1;
}
}
LRUCache.prototype.put = function(key, value) {
let cache = this.cache;
if (cache.has(key)) {
cache.delete(key);
} else if (cache.size >= this.capacity) {//如果此时容量与最大容量相等,那么需要删掉第一个
cache.delete(cache.keys().next().value);
//next()方法,调用返回一个包含两个属性的对象,分别是value和done,value表示当前位置的值,done表示是否迭代完,当为true的时候,调用next就无效了。
}
cache.set(key, value);
}
分享到