Skip to content

Commit 7bf09db

Browse files
awangdevawangdev
committed
3.8.2016 n
1 parent cead373 commit 7bf09db

File tree

3 files changed

+109
-105
lines changed

3 files changed

+109
-105
lines changed

‎Java/LRU Cache.java

Lines changed: 79 additions & 62 deletions
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@
1111

1212
巧妙点：
1313
1. head和tail特别巧妙：除掉头和尾，和加上头和尾，就都特别快。
14-
2. 用双向的pointer: pre和next， 当需要除掉任何一个node的时候，只要知道要除掉哪一个，
14+
2. 用双向的pointer: pre和next, 当需要除掉任何一个node的时候，只要知道要除掉哪一个，
1515
直接把node.pre和node.next耐心连起来就好了，node就自然而然的断开不要了。
1616

1717
一旦知道怎么解决了，就不是很特别，并不是难写的算法。
@@ -38,79 +38,96 @@ It looks like we need to do some design, according to (http://www.cnblogs.com/yu
3838
Note:
3939
Be careful: when removing a node due to capacity issue, remember to remove both 1st node(head.next) and the corresponding entry in the map: map.remove(head.next.key)
4040
*/
41-
public class LRUCache {
42-
private class LinkNode {
43-
int key;
44-
int val;
45-
LinkNode pre = null;
46-
LinkNode next = null;
47-
LinkNode(int key, int val) {
48-
this.key = key;
49-
this.val = val;
50-
}
51-
}
5241

53-
private int cap;
54-
private HashMap<Integer, LinkNode> map;
55-
private LinkNode head;
56-
private LinkNode tail;
42+
//Use double linked list to store value.
43+
//Store key in hashmap<key, node> to find node easily
44+
//Functions: insert in front, remove node,
45+
public class LRUCache {
46+
class DoubleLinkedListNode {
47+
int key, val;
48+
DoubleLinkedListNode next,prev;
49+
public DoubleLinkedListNode(int key, int val){
50+
this.key = key;
51+
this.val = val;
52+
next = null;
53+
prev = null;
54+
}
55+
}
56+
public int capacity;
57+
public HashMap<Integer, DoubleLinkedListNode> map;
58+
public DoubleLinkedListNode head, tail;
5759
public LRUCache(int capacity) {
58-
this.cap = capacity;
59-
this.map = new HashMap<Integer, LinkNode>();
60-
this.head = new LinkNode(-1, -1);
61-
this.tail = new LinkNode(-1, -1);
60+
this.capacity = capacity;
61+
this.map = new HashMap<Integer, DoubleLinkedListNode>();
62+
this.head = new DoubleLinkedListNode(-1, -1);
63+
this.tail = new DoubleLinkedListNode(-1, -1);
6264
head.next = tail;
63-
tail.pre = head;
65+
head.prev = tail;
66+
tail.next = head;
67+
tail.prev = head;
6468
}
6569

6670
public int get(int key) {
67-
if (map.containsKey(key)) {
68-
LinkNode temp = map.get(key);
69-
moveUsedToTail(temp);
70-
return temp.val;
71-
} else {
72-
return -1;
73-
}
71+
if (map.containsKey(key)) {
72+
DoubleLinkedListNode node = map.get(key);
73+
moveToHead(node);
74+
return node.val;
75+
} else {
76+
return -1;
77+
}
7478
}
7579

7680
public void set(int key, int value) {
77-
if (map.containsKey(key)) {
78-
LinkNode temp = map.get(key);
79-
temp.val = value;
80-
moveUsedToTail(temp);
81-
} else {
82-
if (map.size() >= cap) {
83-
map.remove(head.next.key);
84-
removeHead();
85-
}
86-
LinkNode newNode = new LinkNode(key, value);
87-
addTail(newNode);
88-
map.put(key, newNode);
89-
}
81+
if (map.containsKey(key)) {
82+
map.get(key).val = value;
83+
moveToHead(map.get(key));
84+
} else {
85+
DoubleLinkedListNode node = new DoubleLinkedListNode(key, value);
86+
if (map.size() >= this.capacity) {
87+
DoubleLinkedListNode rm = tail.prev;
88+
remove(rm);
89+
map.remove(rm.key);
90+
}
91+
insertHead(node);
92+
map.put(key, node);
93+
}
94+
}
95+
96+
public void moveToTail(DoubleLinkedListNode node) {
97+
remove(node);
98+
insertTail(node);
99+
}
100+
101+
public void moveToHead(DoubleLinkedListNode node) {
102+
remove(node);
103+
insertHead(node);
104+
}
105+
106+
//Helper functions
107+
public void insertHead(DoubleLinkedListNode node) {
108+
DoubleLinkedListNode next = head.next;
109+
head.next = node;
110+
node.prev = head;
111+
node.next = next;
112+
next.prev = node;
113+
}
114+
115+
public void insertTail(DoubleLinkedListNode node) {
116+
DoubleLinkedListNode prev = tail.prev;
117+
prev.next = node;
118+
node.prev = prev;
119+
node.next = tail;
120+
tail.prev = node;
121+
}
122+
123+
public void remove(DoubleLinkedListNode node) {
124+
DoubleLinkedListNode front = node.prev;
125+
DoubleLinkedListNode end = node.next;
126+
front.next = end;
127+
end.prev = front;
90128
}
91129

92-
public void moveUsedToTail(LinkNode node) {
93-
removeNode(node);
94-
addTail(node);
95-
}
96-
97-
public void removeHead(){//O(1)
98-
removeNode(head.next);
99-
}
100-
public void addTail(LinkNode node){//O(1)
101-
tail.pre.next = node;
102-
node.pre = tail.pre;
103-
node.next = tail;
104-
tail.pre = node;
105-
}
106-
public void removeNode(LinkNode node) {//O(1)
107-
node.pre.next = node.next;
108-
node.next.pre = node.pre;
109-
}
110130
}
111-
112-
````
113-
````
114131
/*
115132
First Attempt: time exceeds
116133

‎Java/Median of two Sorted Arrays.java

Lines changed: 27 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,14 @@
1+
H
2+
3+
Not done
4+
5+
```
16
/*
27
38
Median of two Sorted Arrays
49
5-
There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays.
10+
There are two sorted arrays A and B of size m and n respectively.
11+
Find the median of the two sorted arrays.
612
713
Example
814
Given A=[1,2,3,4,5,6] and B=[2,3,4,5], the median is 3.5.
@@ -18,12 +24,25 @@ The overall run time complexity should be O(log (m+n)).
1824
*/
1925

2026
/*
21-
Thoughts:
22-
Trivial: merge and find median. NOPE: have to be in log(m+n) time
23-
http://www.jiuzhang.com/solutions/median-of-two-sorted-arrays/
27+
From leetcode:
28+
There are two sorted arrays nums1 and nums2 of size m and n respectively.
29+
Find the median of the two sorted arrays.
30+
The overall run time complexity should be O(log (m+n)).
31+
32+
Hide Company Tags Google Uber Zenefits
33+
Hide Tags Divide and Conquer Array Binary Search
34+
35+
*/
36+
/*
37+
Thoughts:
38+
Trivial: merge and find median. NOPE: have to be in log(m+n) time
39+
http://www.jiuzhang.com/solutions/median-of-two-sorted-arrays/
40+
41+
http://articles.leetcode.com/find-k-th-smallest-element-in-union-of
42+
43+
Good one: http://blog.csdn.net/yutianzuijin/article/details/11499917
44+
http://blog.csdn.net/zxzxy1988/article/details/8587244
2445
25-
http://fisherlei.blogspot.com/2012/12/leetcode-median-of-two-sorted-arrays.html
26-
2746
*/
2847

2948
class Solution {
@@ -37,3 +56,5 @@ public double findMedianSortedArrays(int[] A, int[] B) {
3756
}
3857
}
3958

59+
60+
```

‎ReviewPage.md

Lines changed: 3 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -3784,7 +3784,7 @@ timeout method, 天真的来了一个O(n) 的解法，结果果然timeout.
37843784

37853785
巧妙点：
37863786
1. head和tail特别巧妙：除掉头和尾，和加上头和尾，就都特别快。
3787-
2. 用双向的pointer: pre和next， 当需要除掉任何一个node的时候，只要知道要除掉哪一个，
3787+
2. 用双向的pointer: pre和next, 当需要除掉任何一个node的时候，只要知道要除掉哪一个，
37883788
直接把node.pre和node.next耐心连起来就好了，node就自然而然的断开不要了。
37893789

37903790
一旦知道怎么解决了，就不是很特别，并不是难写的算法。
@@ -4018,43 +4018,9 @@ public class Solution {
40184018
所以从右边累计上来的。也是一样可以的。
40194019

40204020
---
4021-
**167. [Median of two Sorted Arrays.java](https://github.com/shawnfan/LintCode/blob/master/Java/Median of two Sorted Arrays.java)**
4022-
Median of two Sorted Arrays
4021+
**167. [Median of two Sorted Arrays.java](https://github.com/shawnfan/LintCode/blob/master/Java/Median of two Sorted Arrays.java)** Level: Hard
40234022

4024-
There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays.
4025-
4026-
Example
4027-
Given A=[1,2,3,4,5,6] and B=[2,3,4,5], the median is 3.5.
4028-
4029-
Given A=[1,2,3] and B=[4,5], the median is 3.
4030-
4031-
Challenge
4032-
The overall run time complexity should be O(log (m+n)).
4033-
4034-
Tags Expand
4035-
Sorted Array Divide and Conquer Array Zenefits Uber Google
4036-
4037-
*/
4038-
4039-
/*
4040-
Thoughts:
4041-
Trivial: merge and find median. NOPE: have to be in log(m+n) time
4042-
http://www.jiuzhang.com/solutions/median-of-two-sorted-arrays/
4043-
4044-
http://fisherlei.blogspot.com/2012/12/leetcode-median-of-two-sorted-arrays.html
4045-
4046-
*/
4047-
4048-
class Solution {
4049-
/**
4050-
* @param A: An integer array.
4051-
* @param B: An integer array.
4052-
* @return: a double whose format is *.5 or *.0
4053-
*/
4054-
public double findMedianSortedArrays(int[] A, int[] B) {
4055-
// write your code here
4056-
}
4057-
}
4023+
Not done
40584024

40594025

40604026
---

0 commit comments

Comments
 (0)