KK's blog

LeetCode

题目大意：

N/A

解题思路：

N/A

解题步骤：

N/A

注意事项：

Python代码：

1

算法分析：

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

LeetCode

<div>

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++'s atoi function).

The algorithm for myAtoi(string s) is as follows:

1. Read in and ignore any leading whitespace.
2. Check if the next character (if not already at the end of the string) is '-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
3. Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
4. Convert these digits into an integer (i.e. "123" -> 123, "0032" -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).
5. If the integer is out of the 32-bit signed integer range [-2<sup>31</sup>, 2<sup>31</sup> - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -2<sup>31</sup> should be clamped to -2<sup>31</sup>, and integers greater than 2<sup>31</sup> - 1 should be clamped to 2<sup>31</sup> - 1.
6. Return the integer as the final result.

Note:

• Only the space character ' ' is considered a whitespace character.
• Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.

Example 1:

<pre>Input: s = "42" Output: 42 Explanation: The underlined characters are what is read in, the caret is the current reader position. Step 1: "42" (no characters read because there is no leading whitespace) ^ Step 2: "42" (no characters read because there is neither a '-' nor '+') ^ Step 3: "<u>42</u>" ("42" is read in) ^ The parsed integer is 42. Since 42 is in the range [-2³¹, 2³¹ - 1], the final result is 42. </pre>

Example 2:

<pre>Input: s = " -42" Output: -42 Explanation: Step 1: "-42" (leading whitespace is read and ignored) ^ Step 2: " <u>-</u>42" ('-' is read, so the result should be negative) ^ Step 3: " -<u>42</u>" ("42" is read in) ^ The parsed integer is -42. Since -42 is in the range [-2³¹, 2³¹ - 1], the final result is -42. </pre>

Example 3:

<pre>Input: s = "4193 with words" Output: 4193 Explanation: Step 1: "4193 with words" (no characters read because there is no leading whitespace) ^ Step 2: "4193 with words" (no characters read because there is neither a '-' nor '+') ^ Step 3: "<u>4193</u> with words" ("4193" is read in; reading stops because the next character is a non-digit) ^ The parsed integer is 4193. Since 4193 is in the range [-2³¹, 2³¹ - 1], the final result is 4193. </pre>

Constraints:

• 0 <= s.length <= 200
• s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.

</div>

题目大意：

字符串转整数

解题思路：

关键是第一位是否符号的判断，之后是ord函数的运用

解题步骤：

N/A

注意事项：

1. 空字符或全空格返回0
2. [key]若有符号只能第一位是符号，连续是符号不合法返回0，如-+12, 将符号处理放在循环外
3. 除符号外，若第一位为非数字，不合法，返回0
4. 循环内，若出现非数字，跳出循环
5. 计算符号，然后检查数字范围

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 myAtoi(self, s: str) -> int:
	s = s.strip()
	if not s:
		return 0
	sign = 1
	if s[0] == '-':
		sign = -1
		s = s[1:]
	elif s[0] == '+':
		s = s[1:]
	if s and not s[0].isdigit():
		return 0
	res = 0
	for char in s:
		if char.isdigit():
			res = res * 10 + ord(char) - ord('0')
		else:
			break
	res *= sign
	if res < -pow(2, 31):
		return -pow(2, 31)
	if res > pow(2, 31) - 1:
		return pow(2, 31) - 1
	return res

算法分析：

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

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:

<pre>nums1 = [1, 3] nums2 = [2]

The median is 2.0 </pre>

Example 2:

<pre>nums1 = [1, 2] nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5 </pre>

题目大意：

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

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

由于是求中位数或第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)。

LeetCode 127 Word Ladder

<div>

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:

<pre>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. </pre>

Example 2:

<pre>Input: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possibletransformation. </pre>

</div>

题目大意：

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

解题思路：

这题是最短路径题，第一时间想到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=<code>O(L²)</code>产生新字符串需要L
时间复杂度为<code>O(n*L²)</code>，空间复杂度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

LeetCode 146 LRU Cache

<div>

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:

<pre>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 </pre>

</div>

题目大意：

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

解题思路：

因为是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. 需求：记得get和set都需要更新LL的顺序
2. set的时候，如果只是更新值而不产生新的key，不需要查capacity，需要分情况
3. 此题跟first unique number不同，node有key和val
4. 注意删除顺序，先删map中的entry再删Node。否则会出现NPE。新加入是顺序相反。删除节点要将prev和next赋None
5. 函数加入self，内部函数用下划线前缀，跟第一遍不同，只用了两个内部函数，分别是_remove, _append

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

class LRUCache:

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

    def get(self, key: int) -> int:
        if key not in self.key_to_node:
            return -1
        node = self.key_to_node[key]
        #attn update LL
        self._remove(node)
        self._append(node)
        return node.val
        

    def put(self, key: int, value: int) -> None:
        if key not in self.key_to_node and len(self.key_to_node) == self.capacity: #attn key not in self.key_to_node
            old_node = self.head.next
            self.key_to_node.pop(old_node.key)
            self._remove(self.head.next)
        #attn update LL
        if key in self.key_to_node:
            node = self.key_to_node[key]
            node.val = value
            self._remove(node)
        else:
            node = Node(key, value)
        self._append(node)
        self.key_to_node[key] = node

    def _remove(self, node):
        predecessor, successor = node.prev, node.next
        predecessor.next, successor.prev = successor, predecessor
        node.prev, node.next = None, None
    
    def _append(self, node):
        predecessor, successor = self.tail.prev, self.tail
        predecessor.next, node.prev = node, predecessor
        node.next, successor.prev = successor, node
        
class Node:

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

注意事项：

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)。