KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode 004 Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1: 

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2: 

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

题目大意：

求两个有序数组中的中位数。

数值二分法解题思路(推荐)：

由于是求中位数或第k小的数，根据题型分类用Heap或binary select。Heap的话，由于是有序，所以优势不大，复杂度为O[(m+n)log2].
考虑用binary select，思路比较直接，就是将两个数组看成一个，统计个数的时候由于有序，分别在两数组用二分法统计。

注意事项：

  1. 中位数有1-2两个。用单一元素数组的例子来确定+1还是-1，Line 6
  2. 统计最大最小值，注意空数组
  3. 统计count用bisect不需要+1

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
	m, n = len(nums1), len(nums2)
	if (m + n) % 2 == 1:
		return self.find_kth_smallest(nums1, nums2, (m + n) // 2)
	else:
		return (self.find_kth_smallest(nums1, nums2, (m + n) // 2) + self.find_kth_smallest(nums1, nums2, (m + n) // 2 - 1)) / 2

def find_kth_smallest(self, nums1, nums2, k):
	min_val, min_val2 = nums1[0] if nums1 else float('inf'), nums2[0] if nums2 else float('inf')
	max_val, max_val2 = nums1[-1] if nums1 else float('-inf'), nums2[-1] if nums2 else float('-inf')
	start, end, epsilon = min(min_val, min_val2), max(max_val, max_val2), 0.5
	while end - start > epsilon:
		mid = start + (end - start) / 2
		count = self.count(nums1, nums2, mid)
		if k < count:
			end = mid
		elif k > count:
			start = mid
		else:
			start = mid
	return math.floor(end)

def count(self, nums1, nums2, mid):
	return bisect.bisect(nums1, mid) + bisect.bisect(nums2, mid)  # remember

算法分析：

时间复杂度为O(nlog(|hi-lo|/delta))，由于数据大小范围是10^6, 而前面的n是基于全数组扫描，这里用二分法，n变成log(m)+log(n)
时间复杂度为O(logm + logn)，空间复杂度O(1)

Merge sort算法II解题思路：

既然是有序，考虑用merge sort中的merge步骤
merge sort里面的数组是无序，但这里是有序，所以merge这个步骤可以改进，不是一个个数比较，可以分别取第k/2进行比较，原理是一样的，但效率更高。
若num1[k/2] < num2[k/2]相当于nums1[i] <= nums2[j]，此时表示num1[0..k/2]都满足小于等于第k个数的结果数组中。i移位，不是移一位，而是移k/4.
这样得到方法三。方法三解释比较难懂，用mergesort模拟较易懂。
一般是对数组二分，此法采用对k二分

注意事项：

  1. 若i或j用完，返回另一个数组的元素，下标是j+k或i+k，k此时是剩余的k

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def findMedianSortedArrays2(self, nums1: List[int], nums2: List[int]) -> float:
	m, n = len(nums1), len(nums2)
	if (m + n) % 2 == 1:
		return self.find_kth_smallest2(nums1, nums2, (m + n) // 2)
	else:
		return (self.find_kth_smallest2(nums1, nums2, (m + n) // 2) + self.find_kth_smallest2(nums1, nums2, (m + n) // 2 - 1)) / 2

def find_kth_smallest2(self, nums1, nums2, k):
	i, j = 0, 0
	while i < len(nums1) and j < len(nums2) and k > 0:
		if nums1[i] <= nums2[j]:
			i += 1
		else:
			j += 1
		k -= 1
	if i == len(nums1):  # remember dont use (not nums1)
		return nums2[j + k]  # remember use j+k rather than k
	if j == len(nums2):
		return nums1[i + k]
	return min(nums1[i], nums2[j])

算法分析：

时间复杂度为O(m + n)，空间复杂度O(1)。

二分法算法III解题思路：

将上面的方法换成递归，if判断语句换成递归终止条件，+1变成+k/2，注意判断越界
说起来轻松，但非常容易错，不推荐

注意事项：

  1. 中位数有1-2两个。
  2. off by 1的问题。递归子函数要用(k+1)//2而不是k//2因为若k=1时候，k//2就不能移动一位。
  3. 若nums中i + k // 2越界，不碰nums，右移j，因为nums不能右移那么多, 所以num1赋最大值不是最小值
  4. 终止条件i >= len(nums1)取大于号，跟上面不同，因为可能越界

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def findMedianSortedArrays3(self, nums1: List[int], nums2: List[int]) -> float:
	m, n = len(nums1), len(nums2)
	if (m + n) % 2 == 1:
		return self.find_kth_smallest3(nums1, nums2, 0, 0, (m + n) // 2)
	else:
		aa = self.find_kth_smallest3(nums1, nums2, 0, 0, (m + n) // 2)
		bb = self.find_kth_smallest3(nums1, nums2, 0, 0, (m + n) // 2 - 1)
		return (self.find_kth_smallest3(nums1, nums2, 0, 0, (m + n) // 2)
				+ self.find_kth_smallest3(nums1, nums2, 0, 0, (m + n) // 2 - 1)) / 2

    def find_kth_smallest3(self, nums1, nums2, i, j, k):
        if i >= len(nums1):  # remember to use >= rather than ==
            return nums2[j + k]
        if j == len(nums2):
            return nums1[i + k]
        if k == 0:
            return min(nums1[i], nums2[j])
        num1 = nums1[i + k // 2] if i + k // 2 < len(nums1) else float('inf')  # remember sys.maxsize not minus
        num2 = nums2[j + k // 2] if j + k // 2 < len(nums2) else float('inf')
        if num1 <= num2:  # remember the steps are same by moving i and k, k + 1
            return self.find_kth_smallest3(nums1, nums2, i + (k + 1) // 2, j, k - (k + 1) // 2)
        else:
            return self.find_kth_smallest3(nums1, nums2, i, j + (k + 1) // 2, k - (k + 1) // 2)

Java实现

题目要求log(m+n)复杂度，也就提示要对数组总长做二分法。因为要同时处理两个数组所以考虑用递归版二分法。因奇偶中位数有1-2个，
所以加强命题为求两有序数组的第k个数(k>=1)。
对k的值进行二分k/2，先尝试num1数组的第k/2个数和num2数组的第k/2个数。若它们相等，表示它们即为第k个数。也就是比如求第4个数，
分别在两数组中取前两个，平均分配名额。此题类似于求前k大的数(算法文档4.1.13)用统计个数的方法来判断走左还是右。若它们不等，不妨假设
aKey<bKey，这样表示第k个数一定不会是aKey，因为即使比bKey小的数均小于aKey的话（有k/2-1个），总共有k/2-1+k/2-1=k-2个数小于
aKey，也就是aKey为第k-1个数，不可能为第k个数，它只可能出现是bKey或者在num1中比aKey大的数。既然aKey不是解，比aKey小的数
更不可能是解。所以，可以抛掉num1[0, k/2]这部分，转而求num1[k/2+1,nums.length-1]以及nums2的第k-k/2个数，抛掉部分会影响结果
吗？答案是否定的。比如
1 2 3 4
0 6 7 8
k=4，比较2和6,2<6抛掉1 2，转求[3,4],[0,6,7,8]的第2个数，答案仍为3，不影响结果，因为前k/2个数即使有些在nums2也不会影响
最后结果，求的是第k个。
1 2 3 4
0 6 7 8
第k=4数可能出现在num1[k/2+1,nums.length-1]=3或num2=6（下面例子），所以保留部分是正确的。
主要思路是每次递归抛掉k/2个数，数组规模减少k/2，k变成k-k/2, API为left, left2表示新数组的左边界(因为永远抛左边部分)以及k。
递归终止条件为

  1. left越界，这时此数组的数刚好用完或此数组为空(不会越界太多，否则aKey无穷大会递归到num2)。归结为求另一数组[left..]的第k个数.
  2. k为1时候，是基本情况，表示求两数组的第1个数，只要返回左端的最小值即可。

注意事项：

  1. 中位数有1-2两个。
  2. off by 1的问题。若API中的k定义为第k个数k>=1，若总长len=5，中位数为第len/2+1=3个数。所以在递归函数中，数组下标用到k时
    都要-1。抛掉[left, left+k/2-1],递归[left+k/2..]。
  3. 若nums中left+k/2-1越界，不碰nums，右移left2，因为nums不能右移那么多。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public double findMedianSortedArrays(int[] num1, int[] num2){
	int len = num1.length+num2.length;
	if(len%2==1)
		return findKth(num1,num2,0,0,len/2+1);
	else return (findKth(num1,num2,0,0,len/2)+findKth(num1,num2,0,0,len/2+1))/2.0;
}

public int findKth(int[] num1, int[] num2, int left, int left2, int k){
	if(left>=num1.length)
		return num2[left2+k-1];
	if(left2>=num2.length)
		return num1[left+k-1];
	if(k==1)
		return Math.min(num1[left], num2[left2]);;
	
	int aKey = left+k/2-1<num1.length?num1[left+k/2-1]:Integer.MAX_VALUE;
	int bKey = left2+k/2-1<num2.length?num2[left2+k/2-1]:Integer.MAX_VALUE;
	if(aKey<bKey)
		return findKth(num1,num2,left+k/2,left2,k-k/2);
	else
		return findKth(num1,num2,left,left2+k/2, k-k/2);
}

算法分析：

假设两数组总长度为N，k为中位数即N/2，每次抛掉k/2也就是子问题规模为N-k/2=N-N/4=3N/4. f(N)=f(3N/4)+1.
利用master理论b=4/3, a=1, f(n)=1代入时间复杂度为O(log(m+n))，空间复杂度O(1)。

Posted on Edited on Disqus:

LeetCode 127 Word Ladder



Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list.

Note:

Return 0 if there is no such transformation sequence. All words have the same length.
All words contain only lowercase alphabetic characters. You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]

Output: 5

Explanation: As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”,
return its length 5.


Example 2:

Input:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,”dot”,”dog”,”lot”,”log”]

Output: 0

*Explanation: The endWord “cog” is not in wordList, therefore no possibletransformation.


题目大意：

给定一个字典和两个单词。每次变换一个字母的得到新单词且该词要在字典中。求最少变换次数。

解题思路：

这题是最短路径题，第一时间想到BFS。这是一条典型的单源最短路径问题。

  1. 这是图，所以要有visited记录是否重复访问。
  2. 字典的实现两个作用： 快速查找，以及记录距离可以省下一轮循环。总共两重循环。
  3. getNextWords的实现。通过变换每位上字母，比较巧妙。

解题步骤：

这题是最短路径题，第一时间想到BFS。这是一条典型的单源最短路径问题。

  1. 建字典。
  2. BFS访问。
  3. 求所有距离为1的相邻单词getNextWords。

注意事项：

  1. 注意题目条件，开始词不在字典中(终结词默认在，否则无结果），要将它加入字典中且距离为1。
  2. 用Map来记录解(儿子节点，参考按层搜索)，visited用于记录父节点
  3. getNextWords的实现不含自己。
  4. Python中用popleft出列，不是pop

Python代码：

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
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
	if not beginWord or not endWord:
		return 0
	distance = {}
	for word in wordList:
		distance[word] = 0
	distance[beginWord] = 1
	return self.bfs(beginWord, endWord, distance, set())

def bfs(self, beginWord, endWord, dict, visited):
	queue = deque([beginWord])
	visited.add(beginWord)
	while queue:
		word = queue.popleft()
		if word == endWord:
			return dict[word]

		neighbors = self.get_next_words(word, dict)
		for neighbor in neighbors:
			if neighbor not in visited:
				queue.append(neighbor)
				visited.add(neighbor)
				dict[neighbor] = dict[word] + 1

	return 0

def get_next_words(self, word, dict):
	res = []
	for i in range(len(word)):
		for c in string.ascii_lowercase: # or use 'abcdefghijklmnopqrstuvwxyz'
			if c == word[i]:
				continue
			new_word = word[:i] + c + word[i + 1:]
			if new_word in dict:
				res.append(new_word)
	return res

Java代码：

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
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
	// This is a dict and also keeps track of distance
	Map<String, Integer> dict = getDict(wordList);
	// Make sure endWord is in the dict and can be the next word 
	//dict.put(endWord, 0);
	dict.put(beginWord, 1);
	
	Set<String> visited = new HashSet<>();
	Queue<String> q = new LinkedList<>();
	q.offer(beginWord);
	visited.add(beginWord);
	while(!q.isEmpty()) {
		String word = q.poll();
		if(endWord.equals(word))
			return dict.get(word);
		
		List<String> nextWords = getNextWords(word, dict);
		for(String s : nextWords) {
			if(visited.contains(s))
				continue;
			
			q.offer(s);
			visited.add(s);
			dict.put(s, dict.get(word) + 1);
			
		}
	}
	return 0;
}

Map<String, Integer> getDict(List<String> wordList) {
	Map<String, Integer> map = new HashMap<>();
	for(String word : wordList) {
		map.put(word, 0);
	}
	return map;
}

List<String> getNextWords(String word, Map<String, Integer> dict) {
	List<String> result = new ArrayList<>();
	for(int i = 0; i < word.length(); i++) {
		for(int j = 0; j < 26; j++) { 
			char newChar = (char)('a' + j);
			if(word.charAt(i) == newChar) // exclude itself
				continue;
			String newWord = word.substring(0, i) + 
					newChar + word.substring(i + 1, word.length());
			if(dict.containsKey(newWord))
				result.add(newWord);
			
		}
	}
	return result;
}

算法分析：

getNextWords是L26L=O(L2)产生新字符串需要L
时间复杂度为O(n*L2)，空间复杂度O(n)，n为单词数。

算法II解题思路：

利用双向BFS，参考双向BFS概念
如果搜索不够广的话(例如类似于一条直线)，BFS会较慢，用双向BFS可解决此问题。双向BFS就是同时从起点和终点两个方向开始搜索，结果分存在map中，如果节点在另一个map中，
就意味着找到了一条连接起点和终点的最短路径。若任一queue为空，表明不会存在路径。如下图，前向BFS找到了结果。

搜索方式分为同步搜索和队列容量较少的先搜。本法采取前者

解题步骤：

  1. 与单向BFS类似，但由于现在是双向，所以将BFS的通用部分提取出来，变量为queue, visited, distance, target_distance, target_distance是查找本方向
    的节点是否在对方搜索过的路径上代替endWord，距离为本方向的路径+对方的路径。while循环移到调用函数中。
  2. while循环用两个queue不为空
  3. 为了优化get_next_words重复调用，将结果存在graph中形成邻接表。这样的话，distance不用初始化为0，还可以用于记录重复节点代替visited。
  4. 其他初始化步骤给endWord的BFS复制一次。

注意事项：

  1. graph = collections.defaultdict(list)避免NPE，dict都尽量用此法

Python代码：

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
def ladderLength2(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
	if not beginWord or not endWord:
		return 0
	wordList.append(beginWord)
	graph, word_dict = collections.defaultdict(list), set(wordList)
	for word in wordList:
		graph[word] = self.get_next_words(word, word_dict)
	forward_distance, backward_distance = collections.defaultdict(int), collections.defaultdict(int)
	forward_distance[beginWord], backward_distance[endWord] = 1, 0

	forward_queue, backward_queue = deque([beginWord]), deque([endWord])
	forward_visited, backward_visited = set([beginWord]), set([endWord])
	while forward_queue and backward_queue:
		total_dis = self.bfs_from_start_or_end(graph, forward_queue, forward_distance, backward_distance)
		if total_dis > 0:
			return total_dis
		total_dis = self.bfs_from_start_or_end(graph, backward_queue, backward_distance, forward_distance)
		if total_dis > 0:
			return total_dis
	return 0

def bfs_from_start_or_end(self, graph, queue, distance, target_dict):
	word = queue.popleft()
	if word in target_dict and target_dict[word] > 0:  # the forward distance has all words initially
		return distance[word] + target_dict[word]

	neighbors = graph[word]
	for neighbor in neighbors:
		#if neighbor in visited:
		if neighbor in distance:
			continue
		queue.append(neighbor)
		# visited.add(neighbor)
		distance[neighbor] = distance[word] + 1
	return 0

Posted on Edited on Disqus:

LeetCode



You have a queue of integers, you need to retrieve the first unique integer in the queue.

Implement the FirstUnique class:

FirstUnique(int[] nums) Initializes the object with the numbers in the queue. int showFirstUnique() returns the value of the first unique integer of the queue, and returns -1 if there is no such integer.
void add(int value) insert value to the queue.

Example 1:

Input:
[“FirstUnique”,”showFirstUnique”,”add”,”showFirstUnique”,”add”,”showFirstUnique”,”add”,”showFirstUnique”]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output:
[null,2,null,2,null,3,null,-1]
Explanation:
FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // return 2
firstUnique.add(5);            // the queue is now [2,3,5,5]
firstUnique.showFirstUnique(); // return 2
firstUnique.add(2);            // the queue is now [2,3,5,5,2]
firstUnique.showFirstUnique(); // return 3
firstUnique.add(3);            // the queue is now [2,3,5,5,2,3]
firstUnique.showFirstUnique(); // return -1


Example 2:

Input:
[“FirstUnique”,”showFirstUnique”,”add”,”add”,”add”,”add”,”add”,”showFirstUnique”]
[[[7,7,7,7,7,7]],[],[7],[3],[3],[7],[17],[]]
Output:
[null,-1,null,null,null,null,null,17]
Explanation:
FirstUnique firstUnique = new FirstUnique([7,7,7,7,7,7]);
firstUnique.showFirstUnique(); // return -1
firstUnique.add(7);            // the queue is now [7,7,7,7,7,7,7]
firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3]
firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3,3]
firstUnique.add(7);            // the queue is now [7,7,7,7,7,7,7,3,3,7]
firstUnique.add(17);           // the queue is now [7,7,7,7,7,7,7,3,3,7,17]
firstUnique.showFirstUnique(); // return 17


Example 3:

Input:
[“FirstUnique”,”showFirstUnique”,”add”,”showFirstUnique”]
[[[809]],[],[809],[]]
Output:
[null,809,null,-1]
Explanation:
FirstUnique firstUnique = new FirstUnique([809]);
firstUnique.showFirstUnique(); // return 809
firstUnique.add(809);          // the queue is now [809,809]
firstUnique.showFirstUnique(); // return -1


Constraints: 1 <= nums.length <= 10^5
1 <= nums[i] <= 10^8 1 <= value <= 10^8
* At most 50000 calls will be made to showFirstUnique and add.

算法思路：

Dict + LL (1次) + Set (2次)。此题非常类似于LRU, 相当于实习LinkedHashMap。

由易到难

题目 LL Map 其他数据结构
LRU 按时间顺序，头删尾入 值->LL节点 N/A
First Unique 按时间顺序，任意删尾入 值->LL节点 Set存两次以上
LFU 多个时间顺序的LL 值->LL节点 第二个Map存freq-> LL的首节点以及min_freq

注意事项：

  1. 注意两种情况，节点不在Map, 在Map中，对应的LL操作同样是add_to_tail和remove_node不过少了move_to_tail。
  2. 头尾dummy node，初始化要相连。
  3. 注意删除顺序，先删map中的entry再删Node。否则会出现NPE。新加入是顺序相反。删除节点要将prev和next赋None
  4. 区别还有ListNode不需要key，因为输入是单值，不是key-value对。数据结构多了set来记录出现两次及以上的元素，直接忽略

Python代码：

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
class FirstUnique(TestCases):

    '''
    2, 3, 5, 5
    dict:
    {2:1
     3:1
     5:2 (remove)
     }
    LinkedList: 2, 3, 5(r), 5(r)
    dict:
    {
        2: Node(2)
        3: Node(3)
        5: Node(5)
    }
    
    '''

    def __init__(self, nums: List[int]):
        self.head = ListNode(0)  # only store unique elements
        self.tail = ListNode(0)
        self.key_to_node = {}  # only store unique elements
        self.non_unique_set = set()
        self.head.next, self.tail.prev = self.tail, self.head

        for n in nums:
            self.add(n)

    def showFirstUnique(self) -> int:
        if len(self.key_to_node) == 0:
            return -1
        return self.head.next.val
    # 2, 3, 5, 5
    def add(self, value: int) -> None:
        if value in self.non_unique_set:
            return

        if value not in self.key_to_node:
            new_node = ListNode(value)
            self.add_to_tail(new_node)
            self.key_to_node[value] = new_node
        else:
            to_be_removed_node = self.key_to_node[value]
            self.key_to_node.pop(value)
            self.remove_node(to_be_removed_node)
            self.non_unique_set.add(value)

    def add_to_tail(self, node):
        predecessor = self.tail.prev
        predecessor.next, node.prev = node, predecessor
        node.next, self.tail.prev = self.tail, node

    def remove_node(self, node):
        predecessor, successor = node.prev, node.next
        predecessor.next, successor.prev = successor, predecessor
        node.prev, node.next = None, None


class ListNode:

    def __init__(self, val, next = None, prev = None):
        self.val = val
        self.next = next
        self.prev = prev

算法分析：

每个操作时间复杂度为O(1)，空间复杂度O(n).

Posted on Edited on Disqus:

LeetCode 146 LRU Cache



Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 / capacity / );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4


题目大意：

设计LRU。就是最旧的cache会先被删除。

题目 LL Map 其他数据结构
LRU 按时间顺序，头删尾入 值->LL节点 N/A
First Unique 按时间顺序，任意删尾入 值->LL节点 Set存两次以上
LFU 多个时间顺序的LL 值->LL节点 第二个Map存freq-> LL的首节点以及min_freq

解题思路：

因为是Cache，get是O(1)，自然想到用HashMap。如果不限容量，get，put都可以O(1)。限容量的情况下，
就要删除部分数据，这里要求按key的时间排序，所以考虑用一个串将keys串联起来。而key的添加和删除
也要O(1)，所以考虑用LinkedList。HashMap和LinkedList的组合很常见。这里value就指向LL中的Node，
而Node中含key和value，key又可以让Node只向HashMap，做到互相索引。分析get和set，get就只要从Map
中读Node的value即可。set比较复杂，含三种情况：

  1. 已有节点
  2. 不含节点且少于容量
  3. 不含节点且大于等于容量

对应链表操作为：

  1. 删除该节点且插入到末尾（LL顺序为由旧到新）
  2. 插入新节点到末尾
  3. 删除头节点且插入新节点到末尾

总结链表操作为两个：

  1. 删除某节点
  2. 插入新节点到末尾

实现上可以分为单链表和双链表。单链表要让Map指向节点的父节点。实现上很麻烦，因为更新节点都会涉及
两个keys上HashMap更新，即使已有节点换到末尾同样要两次更新Map。但双链表对此情况就避免了Map的更新。

DummyNode的选择：一开始我只选用了DummyHead，但capacity=1的时候要判断末节点是否为空很麻烦，由于
经常性的插入末节点，所以根据若头结点涉及插入删除就应该用dummyNode的原则，末节点也增加dummyNode
程序就简洁很多。

有些解法用单链表，用node映射到对应节点的父节点key_to_prev，这个方法反而不好理解，写的时候也容易错，不推荐

注意事项：

  1. set中，若节点存在，更新value。更新节点在链表中的顺序。注意三种情况，已有节点以及不含节点的两种。
  2. 头尾dummy node，初始化要相连。
  3. 注意删除顺序，先删map中的entry再删Node。否则会出现NPE。新加入是顺序相反。删除节点要将prev和next赋None
  4. 双向LL加入新节点有两个赋值语句，不要忘记node.prev, node.next = predecessor, successor

Python代码：

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
class LRUCache:

    def __init__(self, capacity: int):
        self.key_to_node = {}
        self.capacity = capacity
        self.head = ListNode(0, 0)
        self.tail = ListNode(0, 0)
        self.head.next, self.tail.prev = self.tail, self.head

    def get(self, key: int) -> int:
        if key not in self.key_to_node:
            return -1
        self.move_to_tail(self.key_to_node[key])
        return self.key_to_node[key].val

    def put(self, key: int, value: int) -> None:
        if key in self.key_to_node:
            self.key_to_node[key].val = value
            self.move_to_tail(self.key_to_node[key])
        else:
            if len(self.key_to_node) == self.capacity:
                self.key_to_node.pop(self.head.next.key)
                self.remove_node(self.head.next)

            node = ListNode(key, value)
            self.add_to_tail(node)  # add_to_tail(node)
            self.key_to_node[key] = node

    def move_to_tail(self, node):
        self.remove_node(node)
        self.add_to_tail(node)

    def add_to_tail(self, node):
        predecessor, successor = self.tail.prev, self.tail
        predecessor.next, node.prev = node, predecessor
        node.next, successor.prev = successor, node

    def remove_node(self, node):
        predecessor, successor = node.prev, node.next
        predecessor.next, successor.prev = successor, predecessor
        node.prev, node.next = None, None


class ListNode:
    def __init__(self, key, val, next = None, prev = None):
        self.val = val
        self.key = key
        self.next = next
        self.prev = prev

Java代码：

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
Map<Integer, ListNode> map;
ListNode head; // from oldest to newest
ListNode tail;
int capacity;
public L146LRUCache(int capacity) {
	this.capacity = capacity;
	head = new ListNode(-1, -1);
	tail = new ListNode(-1, -1);
	head.next = tail;
	tail.prev = head;
	map = new HashMap<>();
}

public int get(int key) {
	if(!map.containsKey(key))
		return -1;
	pushback(key);
	return map.get(key).val;
}

public void put(int key, int value) {
	if(map.containsKey(key)) {
		pushback(key);
		map.get(key).val = value; // remember to update the value
	}
	else {
		if(map.size() == capacity) {
			map.remove(head.next.key);
			deleteNode(head.next);
		}
		// add new key
		ListNode newNode = new ListNode(key, value);
		addNodeToTail(newNode);
		map.put(key, newNode);
	}
}

void pushback(int key) {
	ListNode curNode = map.get(key);
	deleteNode(curNode);
	addNodeToTail(curNode);
}

void addNodeToTail(ListNode curNode) {
	ListNode prevTailNode = tail.prev;
	prevTailNode.next = curNode;
	curNode.prev = prevTailNode;
	curNode.next = tail;
	tail.prev = curNode;
}
// delete head node and updated node
void deleteNode(ListNode curNode) {
	ListNode nextNode = curNode.next;
	ListNode prevNode = curNode.prev;
	prevNode.next = nextNode;
	nextNode.prev = prevNode;
	curNode.next = null;
	curNode.prev = null;
}

public class ListNode {
	public int key;
	public int val;
	public ListNode next;
	public ListNode prev;

	public ListNode(int key, int val) {
		this.key = key;
		this.val = val;
	}
}

算法分析：

时间复杂度为O(1)，空间复杂度为O(n)。

Posted on Edited on Disqus:

LeetCode



You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6


Example 2:

Input: lists = []
Output: []


Example 3:

Input: lists = [[]]
Output: []


Constraints:

k == lists.length 0 <= k <= 10^4
0 <= lists[i].length <= 500 -10^4 <= lists[i][j] <= 10^4
lists[i] is sorted in ascending order. The sum of lists[i].length won’t exceed 10^4.

算法思路：

N/A

注意事项：

  1. heap不能比较ListNode大小，要实现lt函数或者将(node.val, node)对加入到heap中(此法Leetcode有编译错误但PyCharm可过)
  2. 出堆后node的next赋None不需要，因为每个节点next都会重复赋值，而最后一个节点本来也没有next

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ListNode.__lt__ = lambda x, y: x.val < y.val
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = []
        fake_head = ListNode(0)
        for head in lists:
            if head:
                heappush(heap, head)
        it = fake_head
        while heap:
            node = heappop(heap)
            if node.next:
                heappush(heap, node.next)
            # node.next = None
            it.next = node
            it = it.next
        return fake_head.next

算法分析：

时间复杂度为O(nlogk)，空间复杂度O(k).

算法II解题思路：

Devide and Conquer

注意事项：

  1. k.next = None因为删除节点，所以赋None，这句不加也行，但作为良好习惯建议加，且不能在i = i.next前加，否则i会变空。
  2. 查lists是否为空

Python代码：

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
def mergeKLists2(self, lists: List[List['ListNode']]) -> 'ListNode':
	if not lists:
		return None
	return self.merge_sort(lists, 0, len(lists) - 1)

def merge_sort(self, lists, start, end):
	if start >= end:
		return lists[start]
	mid = start + (end - start) // 2
	li = self.merge_sort(lists, start, mid)
	li2 = self.merge_sort(lists, mid + 1, end)
	return self.merge_two_lists(li, li2)

def merge_two_lists(self, li, li2):
	i, j, res = li, li2, ListNode(0)
	k = res
	while i and j:
		if i.val < j.val:
			k.next = i
			i = i.next
			k = k.next
			k.next = None
		else:
			k.next = j
			j = j.next
			k = k.next
			k.next = None
	if i:
		k.next = i
	if j:
		k.next = j
	return res.next

算法分析：

不管多少次递归，每次递归的一层总的节点数为n，而对k做二分，所以递归数为logk, 时间复杂度为O(nlogk)，空间复杂度O(1).

算法III解题思路：

算法二的迭代法

注意事项：

  1. 输入大小的奇偶处理
  2. 返回值是lists[0]而不是lists

Python代码：

1
2
3
4
5
6
7
8
9
10
11
def mergeKLists3(self, lists: List[List['ListNode']]) -> 'ListNode':
	if not lists:
		return None
	while len(lists) > 1:
		tmp = []
		if len(lists) % 2 == 1:
			lists.append([])
		for i in range(0, len(lists), 2):
			tmp.append(self.merge_two_lists(lists[i], lists[i + 1]))
		lists = tmp
	return lists[0]

算法分析：

同算法二.

Free mock interview