KK's blog

LeetCode 332 Reconstruct Itinerary

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

1. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
2. All airports are represented by three capital letters (IATA code).
3. You may assume all tickets form at least one valid itinerary.

Example 1:
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return ["JFK", "MUC", "LHR", "SFO", "SJC"].

Example 2:
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.

题目大意：

给定一组机票，用出发机场和到达机场[from, to]来表示，重建行程的顺序。所有的机票都属于一个从JFK（肯尼迪国际机场）出发的旅客。因此，行程必须从JFK开始。

注意：

如果存在多重有效的行程，你应当返回字典序最小的那个。例如，行程[“JFK”, “LGA”]的字典序比[“JFK”, “LGB”]要小。
所有的机场用3个大写字母表示（IATA编码）。
你可以假设所有的机票均至少包含一条有效的行程。

解题思路：

这条题实质是记录DFS路径的题目，且对儿子节点的选择是有顺序的。值得注意的是并不是所有路径都是可形成回路，所以需要DFS搜索。
既然是要记录路径就需要用数组保存结果，而有顺序则表示要排序。

1. 建图，用邻接表来表示HashMap> graph
2. 对每个节点的邻节点LinkList进行排序
3. 从JFK开始dfs。1)终止条件为所有ticket都遍历了(达成回路)或者不能够遍历完。2)路径存在数组中。 3)通过删除节点表示已访问DFS该节点后图要恢复成原状态。

注意事项：

1. 通过删除节点表示已访问DFS该节点后图要恢复成原状态。用下标i来删除，这样才能保证删除再加入仍然有序。另一种方法是用visited边来记录避免修改图。本文用前者
2. 剪枝： 如果找到结果就返回
3. 这题只有一条path，不是所有可能性，但让需要用res，复制path到res，因为path会恢复状态。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

def findItinerary2(self, tickets: List[List[str]]) -> List[str]:
	graph = collections.defaultdict(list)
	for li in tickets:
		graph[li[0]].append(li[1])
	for li in graph.values():
		li.sort()
	path, res = ['JFK'], []
	self.dfs2(graph, 'JFK', len(tickets), path, res)
	return res[0]

def dfs2(self, graph, start, ticket_left, path, res):
	if ticket_left == 0:
		res.append(list(path)) # remember
		return True
	for i, neighbor in enumerate(graph[start]):
		path.append(neighbor)
		graph[start].pop(i) # remember
		if self.dfs2(graph, neighbor, ticket_left - 1, path, res):
			return True
		graph[start].insert(i, neighbor)
		path.pop()
	return False

注意事项：

1. 终止条件为所有ticket都遍历了(达成完整路)或者不能够遍历完Dfs API含ticketLeft。如{“JFK”,”KUL”},{“JFK”,”NRT”},{“NRT”,”JFK”}，虽然KUL在NRT前，但KUL不能组成回路。
2. DFS路径尽量存在数组中，否则用ArrayList中就要先add再remove。
3. 通过删除节点表示已访问DFS该节点后图要恢复成原状态。

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

public List<String> findItinerary(String[][] tickets) {
	HashMap<String, LinkedList<String>> graph = new HashMap<String, LinkedList<String>>();
	for(int i=0;i<tickets.length;i++){
		LinkedList<String> neighbor = graph.get(tickets[i][0]);
		if(neighbor==null)
			neighbor = new LinkedList<String>();
		neighbor.add(tickets[i][1]);
		graph.put(tickets[i][0], neighbor);
	}
	Iterator<String> it = graph.keySet().iterator();
	while(it.hasNext()){
		String key = it.next();
		LinkedList<String> neighbor = graph.get(key);
		Collections.sort(neighbor);
		graph.put(key, neighbor);
	}
	String[] re = new String[tickets.length+1];
	String cur = "JFK";
	re[0] = cur;
	isDFS(graph,cur,tickets.length,tickets.length,re);
	return new ArrayList<String>(Arrays.asList(re));
}

public boolean isDFS(HashMap<String, LinkedList<String>> graph, String departCity
		,int ticketLeft, int ticketNum, String[] re){
	if(ticketLeft==0)
		return true;    	
	LinkedList<String> desCity = graph.get(departCity);
	if(desCity==null)
		return false;
	for(int i=0;i<desCity.size();i++){
		String cur = desCity.get(i);
		re[ticketNum-ticketLeft+1] = cur;
		desCity.remove(i);
		graph.put(departCity, desCity);
		if(isDFS(graph,cur,ticketLeft-1,ticketNum,re))
			return true;;
		desCity.add(i,cur);
		graph.put(departCity, desCity);
	}
	return false;
}

算法分析：

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

LeetCode 349 Intersection of Two Arrays

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:

• Each element in the result must be unique.
• The result can be in any order.

题目大意：

给定两个数组，编写函数计算它们的交集。

注意：
结果中的每个元素一定是唯一的。
结果可以采用任意顺序。

解题思路：

将较小的数组的所有元素放入hashSet，然后遍历另一个数组判断是否相同，相同的话放入hashSet的结果集中。所以需要两个hashSet。

Python代码：

1
2

def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
    return list(set(nums1) & set(nums2))

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public int[] intersection(int[] nums1, int[] nums2) {
	//swap and make sure length of nums1 is smaller
	if(nums1.length>nums2.length){
		int[] tmp = nums1;
		nums1 = nums2;
		nums2 = tmp;
	}
	
	Set<Integer> hash=new HashSet();
	Set<Integer> result=new HashSet();
	for(int i=0;i<nums1.length;i++)
		hash.add(nums1[i]);
	
	for(int i=0; i<nums2.length;i++){
		if(hash.contains(nums2[i]))
			result.add(nums2[i]);
	}
	int[] r=new int[result.size()];
	int k=0;
	for(int i : result)
		r[k++]=i;
	return r;       
}

算法分析：

m和n为数组长度m>n，时间复杂度为O(m)，空间复杂度O(n)。

LeetCode 350 Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:

• Each element in the result should appear as many times as it shows in both arrays.
• The result can be in any order.

Follow up:

• What if the given array is already sorted? How would you optimize your algorithm?
• What if nums1‘s size is small compared to nums2‘s size? Which algorithm is better?
• What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

题目大意：

给定两个数组，编写函数计算它们的交集。

注意：
结果中的每个元素的出现次数应与其在两个数组中同时出现的次数一样多。 结果可以采用任意顺序。

进一步思考：
如果数组已经排好序，怎样优化你的算法？
如果nums1的长度＜nums2的长度？哪一种算法更好？
如果nums2的元素存储在磁盘上，并且内存大小有限，不足以将其一次性的加载到内存中。此时应当怎样做？

解题思路：

类似于L349，但由于可允许重复，所以改hashSet成hashMap记录频数。具体而言，将较小的数组的所有元素放入hashMap且统计频数，
然后遍历另一个数组判断是否相同，相同的话放入ArrayList的结果集中且频数减一。

Python代码：

1
2
3
4
5
6
7
8

def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
	num_to_count = collections.Counter(nums1)
	res = []
	for n in nums2:
		if n in num_to_count and num_to_count[n] > 0:
			num_to_count[n] -= 1
			res.append(n)
	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

public int[] intersect(int[] nums1, int[] nums2) {
	//swap and make sure length of nums1 is smaller
	if(nums1.length>nums2.length){
		int[] tmp = nums1;
		nums1 = nums2;
		nums2 = tmp;
	}
	
	Map<Integer, Integer> map=new HashMap<Integer, Integer>();
	List<Integer> result=new ArrayList();
	for(int i=0;i<nums1.length;i++){
		if(map.containsKey(nums1[i]))
			map.put(nums1[i], map.get(nums1[i])+1);
		else
			map.put(nums1[i],1);
	}
	
	for(int i=0; i<nums2.length;i++){
		if(map.containsKey(nums2[i]) && map.get(nums2[i])>0){
			result.add(nums2[i]);
			map.put(nums2[i], map.get(nums2[i])-1);
		}
	}
	return result.stream().mapToInt(i->i).toArray();      
}

算法分析：

m和n为数组长度m>n，时间复杂度为O(m)，空间复杂度O(n)。

算法II解题思路：

另一个解题思路是，先对它们排序，然后类似于mergeSort算法维持两个指针分别在两个数组搜索相同元素。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public int[] intersect(int[] nums1, int[] nums2) {
	List<Integer> result=new ArrayList();
	Arrays.sort(nums1);
	Arrays.sort(nums2);
	int i=0, j=0;
	while(i<nums1.length && j<nums2.length){
		if(nums1[i]==nums2[j]){
			result.add(nums1[i]);
			i++;
			j++;
		}
		else if(nums1[i]<nums2[j])
			i++;
		else j++;
	}
	return result.stream().mapToInt(k->k).toArray();
}

算法分析：

m和n为数组长度m>n，时间复杂度为O(mlogm)，空间复杂度O(1)。此算法空间较优，但时间稍逊。

1. 如果数组已经排好序，怎样优化你的算法？
   用第二个算法，时间复杂度为O(m),但空间复杂度可以优化为O(1)
2. 如果nums1的长度＜nums2的长度？哪一种算法更好？
   方法一更优，因为nums1空间用的比较少情况下
3. 如果nums2的元素存储在磁盘上，并且内存大小有限，不足以将其一次性的加载到内存中。此时应当怎样做？
   也应该用方法一，因为它不需要把nums2数组一次性加载到内存中。假设内存大小为L，每次L大小的内存可解决
   部分问题，时间复杂度为O(m),然后有n/L次，最后结果为O(mn)，表示空间有限时候，hashSet的方法不比先排序快。

第三种方法是一个数组排序，另一个可以不排序。不排序数组的每个元素在排序数组中用二分法查找。

LeetCode

Input
[“MovingAverage”, “next”, “next”, “next”, “next”]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

Explanation
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // return 1.0 = 1 / 1
movingAverage.next(10); // return 5.5 = (1 + 10) / 2
movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3

题目大意：

求data stream特定窗口的平均数

解题思路：

结构上跟LRU cache类似

解题步骤：

N/A

注意事项：

1. 用queue

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def __init__(self, size: int):
	self.queue = collections.deque()
	self.size = size
	self.sum = 0

def next(self, val: int) -> float:
	if len(self.queue) < self.size:
		self.queue.append(val)
		self.sum += val
	else:
		n = self.queue.popleft()
		self.sum -= n
		self.queue.append(val)
		self.sum += val
	return self.sum / len(self.queue)

算法分析：

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

LeetCode

Input: s = “eceba”, k = 2
Output: 3
Explanation: The substring is “ece” with length 3.

Input: s = “aa”, k = 1
Output: 2
Explanation: The substring is “aa” with length 2.

题目大意：

求最长子串，它含有最多k种字符

解题思路：

同向双指针，属于最长串类型

解题步骤：

N/A

注意事项：

1. while条件中，反计算char_to_count，还要pop key

Python代码：

1
2
3
4
5
6
7
8
9
10
11

def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
	char_to_count, left, max_len = collections.defaultdict(int), 0, 0
	for i, char in enumerate(s):
		char_to_count[char] += 1
		while len(char_to_count) > k:
			char_to_count[s[left]] -= 1
			if char_to_count[s[left]] == 0:
				char_to_count.pop(s[left])
			left += 1
		max_len = max(max_len, i - left + 1)
	return max_len

算法分析：

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