Skip to content

Commit cead373

Browse files
awangdevawangdev
committed
3.8.2016
1 parent d8639d8 commit cead373

12 files changed

+1038
-1076
lines changed

‎Java/Copy List with Random Pointer.java

Lines changed: 50 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
M
22

3-
Basic Implementation, 其中用了一下HashMap:
3+
Basic Implementation, 其中用了一下HashMap:
44

55
遍历head.next .... null.
66
每一步都check map里面有没有head。没有？加上。
@@ -9,14 +9,15 @@
99
```
1010
/*
1111
12-
A linked list is given such that each node contains an additional random pointer
13-
which could point to any node in the list or null.
12+
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
1413
1514
Return a deep copy of the list.
1615
17-
Tags Expand
18-
Hash Table Linked List Uber
16+
Hide Company Tags Microsoft Uber
17+
Hide Tags Hash Table Linked List
18+
Hide Similar Problems (M) Clone Graph
1919
20+
LeetCode: Hard
2021
*/
2122

2223
/**
@@ -39,16 +40,14 @@
3940
border case: if head == null, return null
4041
*/
4142

42-
4343
public class Solution {
4444
public RandomListNode copyRandomList(RandomListNode head) {
4545
if (head == null) {
4646
return null;
4747
}
4848
//creat node, used to link all nodes
49-
RandomListNode dummy = new RandomListNode(0);
50-
RandomListNode node = dummy;
51-
RandomListNode newNode;
49+
RandomListNode node = new RandomListNode(0);
50+
RandomListNode dummy = node;
5251

5352
//HashMap to mark node
5453
HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
@@ -58,15 +57,13 @@ public RandomListNode copyRandomList(RandomListNode head) {
5857
if (!map.containsKey(head)) {
5958
map.put(head, new RandomListNode(head.label));
6059
}
61-
newNode = map.get(head);
62-
node.next = newNode;
60+
node.next = map.get(head);
6361
//process head.random
6462
if (head.random != null) {
6563
if(!map.containsKey(head.random)) {
6664
map.put(head.random, new RandomListNode(head.random.label));
6765
}
68-
newNode = map.get(head.random);
69-
node.next.random = newNode;
66+
node.next.random = map.get(head.random);
7067
}
7168
node = node.next;
7269
head = head.next;
@@ -75,6 +72,7 @@ public RandomListNode copyRandomList(RandomListNode head) {
7572
}
7673
}
7774

75+
7876
/*
7977
Thinking process:
8078
1. Loop through the original list
@@ -122,5 +120,44 @@ public RandomListNode copyRandomList(RandomListNode head) {
122120
}
123121
}
124122

123+
//Same soluton as above, but split populating map && deep copy, which is not as efficient as above
124+
//Save all possible nodes into HashMap<oldNodeAddress, newNodeAddress>
125+
//Deep copy the list, before adding any node, check map
126+
public class Solution {
127+
public RandomListNode copyRandomList(RandomListNode head) {
128+
if (head == null) {
129+
return null;
130+
}
131+
//Populate map
132+
HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
133+
RandomListNode node = head;
134+
RandomListNode newNode;
135+
while(node != null) {
136+
if (!map.containsKey(node)) {
137+
newNode = new RandomListNode(node.label);
138+
map.put(node, newNode);
139+
}
140+
if (node.random != null && !map.containsKey(node.random)) {
141+
newNode = new RandomListNode(node.random.label);
142+
map.put(node.random, newNode);
143+
}
144+
node = node.next;
145+
}
146+
//Deep copy
147+
node = head;
148+
newNode = new RandomListNode(0);
149+
RandomListNode dummy = newNode;
150+
while (node != null) {
151+
newNode.next = map.get(node);
152+
if (node.random != null)
153+
newNode.next.random = map.get(node.random);
154+
newNode = newNode.next;
155+
156+
node = node.next;
157+
}
158+
159+
return dummy.next;
160+
}
161+
}
125162

126163
```

‎Java/Excel Sheet Column Number.java

Lines changed: 0 additions & 46 deletions
This file was deleted.

‎Java/LRU Cache.java

100644100755
Lines changed: 57 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1,21 +1,22 @@
1-
当李特第一次把这题拿出来的时候，我是慌的。
2-
啥是LRU Cache啊？ 接下去看吧。
1+
H
32

4-
后来，我很天真的来了一个O(n) 的解法，结果果然时间过多。
5-
天真解法很简单啊：一个map<key,value>存数值。一个queue<key>来存排位。
6-
每次有更新，就把最新的放在末尾；每次超过capaticity,就把大头干掉。很简单嘛，但是跑起来太久，失败了。
73

8-
于是就来了第二个做法。其实还是跟方法一是类似的。只不过用了一个特别的双向的LinkNode，有了head和tail，这样就大大加快了速度。
9-
主要加快的就是那个‘更新排位’的过程，过去我是O(n),现在O(1)就好了。具体看下面。
4+
timeout method, 天真的来了一个O(n) 的解法，结果果然timeout.
5+
一个map<key,value>存数值。一个queue<key>来存排位。
6+
每次有更新，就把最新的放在末尾；每次超过capaticity,就把大头干掉。很简单嘛，但是跑起来太久，失败了。
107

11-
巧妙点：
12-
1. head和tail特别巧妙：除掉头和尾，和加上头和尾，就都特别快。
13-
2. 用双向的pointer: pre和next， 当需要除掉任何一个node的时候，只要知道要除掉哪一个，
14-
直接把node.pre和node.next耐心连起来就好了，node就自然而然的断开不要了。
8+
于是就来了第二个做法。其实还是跟方法一是类似的。
9+
用了一个特别的双向的LinkNode，有了head和tail，这样就大大加快了速度。
10+
主要加快的就是那个‘更新排位’的过程，过去我是O(n),现在O(1)就好了。
1511

16-
李特的这个Design的题目很有意思。果然值得被作为Hard。但是一旦知道怎么解决了，就不是很特别，因为并不是难想的算法。
12+
巧妙点：
13+
1. head和tail特别巧妙：除掉头和尾，和加上头和尾，就都特别快。
14+
2. 用双向的pointer: pre和next， 当需要除掉任何一个node的时候，只要知道要除掉哪一个，
15+
直接把node.pre和node.next耐心连起来就好了，node就自然而然的断开不要了。
1716

18-
````
17+
一旦知道怎么解决了，就不是很特别，并不是难写的算法。
18+
19+
```
1920
/*
2021
Design and implement a data structure for Least Recently Used (LRU) cache.
2122
It should support the following operations: get and set.
@@ -167,4 +168,46 @@ public void moveUsedToTop(int key) {
167168
}
168169
}
169170
}
170-
````
171+
172+
//O(n) timeout
173+
//Get: find target in arraylist, remove it, insert in front, return map.get(target)
174+
//Set: if exist, find in arraylist, remove it, insert in front.
175+
// if not exist: check capacity: if full, remove last element and remove it from map. Then, insert in front, and insert into map.
176+
public class LRUCache {
177+
public ArrayList<Integer> list = new ArrayList<Integer>();
178+
public HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
179+
public int capacity;
180+
public LRUCache(int capacity) {
181+
this.capacity = capacity;
182+
}
183+
184+
public int get(int key) {
185+
if (map.containsKey(key)) {
186+
int ind = list.indexOf(key);
187+
list.remove(ind);
188+
list.add(0, key);
189+
return map.get(key);
190+
}
191+
return -1;
192+
}
193+
194+
public void set(int key, int value) {
195+
if (map.containsKey(key)) {
196+
int ind = list.indexOf(key);
197+
list.remove(ind);
198+
list.add(0, key);
199+
map.put(key, value);
200+
} else {
201+
list.add(0, key);
202+
map.put(key, value);
203+
if (list.size() > capacity) {
204+
int rm = list.get(list.size() - 1);
205+
list.remove(list.size() - 1);
206+
map.remove(rm);
207+
}
208+
}
209+
210+
}
211+
}
212+
213+
```

‎Java/Permutation Index.java

Lines changed: 26 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -1,39 +1,43 @@
1-
这题目标为简单。但是做了很久。
2-
最后分析出来：
3-
每个数位的数字，都是基于这个数字之前越过的战壕...好吧，意思是，跳过了多少种可能。
4-
对，就用4，2，1举例。网上大家都用这个例子。不行，我要换一个。
1+
E
52

6-
换【6，5，2】吧。我们找6，5，2是permudation里面的第几个。
7-
正常排序，也就是permutation的第一个，应该是【2，5，6】
8-
如果要从首位，2，变成6，要跨过多少条尸体呢？
9-
很简单，高中就学过，重点来了：小于6的数字有多少个呢？（2，5）.然后每个数字变成head，都有各自的变化可能，而每个数字打头，都有(n-1)!种可能。明显了吧，把每个（n-1）!加起来。　注意（ｎ－１）意思就是出去开头的数字（２、５），后面有多少个，有序排列一下有多少情况，不就是（ｎ－１）！嘛。
10-
这一步，公式推出来就是很简单的 (有几个小于6的数字呀) ×（出去ｈｅａｄ剩下有多少个数字）！
3+
和Permutation Sequence相反的题目。思想类似。
114

12-
以上 种种，都是为了把６推上皇位，而牺牲的条数。
5+
题目为Easy，琢磨很久，分析：
6+
每个数位的数字，都是跳过了小于这数字开头的多种可能。
7+
8+
举例【6，5，2】吧。我们找6，5，2是permudation里面的第几个。
9+
正常排序，也就是permutation的第一个，应该是【2，5，6】
10+
如果要从首位，2，变成6，要跨过多少可能性呢？
11+
很简单，就是问：小于6的数字有多少个呢？（2，5）.每个数字变成head，都有各自的一套变化，都有(n-1)!种可能。
12+
13+
本题做法：每个（n-1）!加起来。　Note:(n-1) means, 开头的数字(2,5)各带出多少种排列，也就是不就是(n-1)!嘛。
14+
这一步，计算数量很简单: (有几个小于6的数字) ×(除去head剩下有多少个数字)!
15+
16+
以上 ，都是为了把６推上皇位，而牺牲的条数。
1317

1418
那么把６推上去以后，还有接下去的呢。
1519

16-
接下去要看５，２.
20+
接下去要看５，２.
1721
６确定，后面ｐｅｒｍｕｄａｔｉｏｎ可变的情况有可能是【６，５，２】，那还可能是【６，２，５】呢。
1822

19-
方法一样了。
20-
看ｇｉｖｅｎ　数组的第二位５，算它接下去：
21-
１.　有几个数字小于５呢？
22-
２.　除去５，还有几个数字可以　ｆａｃｔｏｒｉａｌ呢？
23-
３. 一样的。第一步就结果乘以第二步。
23+
Same process, 看ｇｉｖｅｎ　数组的第二位５，算它接下去：
24+
１.　有几个数字小于５呢？
25+
２.　除去５，还有几个数字可以　ｆａｃｔｏｒｉａｌ呢？
26+
３. 一样的。第一步就结果乘以第二步。
2427

25-
接下去要看最后一个元素2了。
26-
一样的想法。
28+
最后接下去要看最后一个元素2了。
2729

2830

29-
6,5,2全看过了以后咋办。
30-
加起来呗。
31-
加起来，就是【6，5，2】上位，所踏过的所有小命啊！
31+
6,5,2全看过了以后，加起来。
32+
就是【6，5，2】上位，所踏过的所有小命啊！
3233

3334
我这解释太生动了。因为耗费了好长时间思考...
35+
3436
```
3537
/*
36-
Given a permutation which contains no repeated number, find its index in all the permutations of these numbers, which are ordered in lexicographical order. The index begins at 1.
38+
Given a permutation which contains no repeated number, find its index in all the permutations of these numbers,
39+
which are ordered in lexicographical order. The index begins at 1.
40+
3741
3842
Example
3943
Given [1,2,4], return 1.

‎Java/Search Rotated in Sorted Array II.java

100644100755
File mode changed.

0 commit comments

Comments
 (0)