KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode

<div>

Given an integer array nums, design an algorithm to randomly shuffle the array. All permutations of the array should be equally likely as a result of the shuffling.

Implement the Solution class:

  • Solution(int[] nums) Initializes the object with the integer array nums.
  • int[] reset() Resets the array to its original configuration and returns it.
  • int[] shuffle() Returns a random shuffling of the array.

Example 1:

<pre>Input ["Solution", "shuffle", "reset", "shuffle"] [[[1, 2, 3]], [], [], []] Output [null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

Explanation Solution solution = new Solution([1, 2, 3]); solution.shuffle(); // Shuffle the array [1,2,3] and return its result. // Any permutation of [1,2,3] must be equally likely to be returned. // Example: return [3, 1, 2] solution.reset(); // Resets the array back to its original configuration [1,2,3]. Return [1, 2, 3] solution.shuffle(); // Returns the random shuffling of array [1,2,3]. Example: return [1, 3, 2]

</pre>

Constraints:

  • 1 <= nums.length <= 200
  • -10<sup>6</sup> <= nums[i] <= 10<sup>6</sup>
  • All the elements of nums are unique.
  • At most 5 * 10<sup>4</sup> calls in total will be made to reset and shuffle.

</div>

题目大意：

随机重排数组

解题思路：

水塘抽样法

先看算法，再理解，第i个元素会被交换的概率：
某一个元素保留概率为(n - i) / (n - i + 1) 某一个元素交换概率为1 / (n - i) 所以从左到右遍历到第i个元素时，它被交换到后面的概率为 所有前面都保留 乘以 第i轮循环时被交换： 

1
(n - 1) / n * (n - 2) / (n - 1) ... (n - i) / (n - i + 1) * 1 / (n - i)
前面都约了，最后等于1 / n

解题步骤：

N/A

注意事项：

  1. 死记算法，跟后面的元素互换
  2. 复制原数组以防被改

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def __init__(self, nums: List[int]):
	self.original = list(nums)
	self.nums = nums

def reset(self) -> List[int]:
	return list(self.original)

def shuffle(self) -> List[int]:
	for i in range(len(self.nums)):
		swap_idx = random.randrange(i, len(self.nums))
		self.nums[i], self.nums[swap_idx] = self.nums[swap_idx], self.nums[i]
	return self.nums

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

Design a logger system that receives a stream of messages along with their timestamps. Each unique message should only be printed at most every 10 seconds (i.e. a message printed at timestamp t will prevent other identical messages from being printed until timestamp t + 10).

All messages will come in chronological order. Several messages may arrive at the same timestamp.

Implement the Logger class:

  • Logger() Initializes the logger object.
  • bool shouldPrintMessage(int timestamp, string message) Returns true if the message should be printed in the given timestamp, otherwise returns false.

Example 1:

<pre>Input ["Logger", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage"] [[], [1, "foo"], [2, "bar"], [3, "foo"], [8, "bar"], [10, "foo"], [11, "foo"]] Output [null, true, true, false, false, false, true]

Explanation Logger logger = new Logger(); logger.shouldPrintMessage(1, "foo"); // return true, next allowed timestamp for "foo" is 1 + 10 = 11 logger.shouldPrintMessage(2, "bar"); // return true, next allowed timestamp for "bar" is 2 + 10 = 12 logger.shouldPrintMessage(3, "foo"); // 3 < 11, return false logger.shouldPrintMessage(8, "bar"); // 8 < 12, return false logger.shouldPrintMessage(10, "foo"); // 10 < 11, return false logger.shouldPrintMessage(11, "foo"); // 11 >= 11, return true, next allowed timestamp for "foo" is 11 + 10 = 21 </pre>

Constraints:

  • 0 <= timestamp <= 10<sup>9</sup>
  • Every timestamp will be passed in non-decreasing order (chronological order).
  • 1 <= message.length <= 30
  • At most 10<sup>4</sup> calls will be made to shouldPrintMessage.

</div>

题目大意：

实现Logger打印的rate limiter

解题思路：

题不难，但有实际意义

解题步骤：

N/A

注意事项：

  1. shouldPrintMessage只有返回True时候才记录时间点。否则不记录。这属于元素相等的test case

Python代码：

1
2
3
4
5
6
7
8
9
10
11
class Logger(TestCases):

    def __init__(self):
        self.throttle_interval = 10
        self.msg_to_timestamp = {}

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        if message in self.msg_to_timestamp and timestamp - self.msg_to_timestamp[message] < self.throttle_interval:
            return False
        self.msg_to_timestamp[message] = timestamp
        return True

算法分析：

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

Posted on Edited on Disqus:

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<String, LinkedList<String>> 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)。

Posted on Edited on Disqus:

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

Posted on Edited on Disqus:

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的方法不比先排序快。

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

Free mock interview