KK's blog

LeetCode

<div>

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Implement the MovingAverage class:

• MovingAverage(int size) Initializes the object with the size of the window size.
• double next(int val) Returns the moving average of the last size values of the stream.

Example 1:

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

Constraints:

• 1 <= size <= 1000
• -10<sup>5</sup> <= val <= 10<sup>5</sup>
• At most 10<sup>4</sup> calls will be made to next.

</div>

题目大意：

求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

<div>

Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.

Example 1:

<pre>Input: s = "eceba", k = 2 Output: 3 Explanation: The substring is "ece" with length 3.</pre>

Example 2:

<pre>Input: s = "aa", k = 1 Output: 2 Explanation: The substring is "aa" with length 2. </pre>

Constraints:

• 1 <= s.length <= 5 * 10<sup>4</sup>
• 0 <= k <= 50

</div>

题目大意：

求最长子串，它含有最多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)

算法思路：

left is left pointer, i is right pointer 外循环为扩张，内循环为收缩。收缩条件为固定字符种数(必须固定或者少于k)或者(以及)固定字符频数。若字符种数不固定，要试1-26种字符，才能单调，详见L395

求最短串

Python代码：

1
2
3
4
5
6
7
8

def two_pointers(self, nums):
	for i in range(len(nums)):
		<calculate condition such as char_to_count>
		while <meets condition>:
			res = min(res, i - left + 1) <求最短子列>
			<anti-calculate condition such as char_to_count>
			left += 1
	return <result>

求最长串

Python代码：

1
2
3
4
5
6
7
8

def two_pointers(self, nums):
	for i in range(len(nums)):
		<calculate condition such as char_to_count>
		while <does not meet condition>:
			<anti-calculate condition such as char_to_count>
			left += 1
		res = max(res, i - left + 1) <求最短子列>
	return <result>

算法分析：

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

LeetCode

<div>

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [nums<sub>l</sub>, nums<sub>l+1</sub>, ..., nums<sub>r-1</sub>, nums<sub>r</sub>] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

<pre>Input: target = 7, nums = [2,3,1,2,4,3] Output: 2 Explanation: The subarray [4,3] has the minimal length under the problem constraint. </pre>

Example 2:

<pre>Input: target = 4, nums = [1,4,4] Output: 1 </pre>

Example 3:

<pre>Input: target = 11, nums = [1,1,1,1,1,1,1,1] Output: 0 </pre>

Constraints:

• 1 <= target <= 10<sup>9</sup>
• 1 <= nums.length <= 10<sup>5</sup>
• 1 <= nums[i] <= 10<sup>5</sup>

Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).</div>

算法思路：

N/A

注意事项：

1. 求最小值，所以min_len初始化最大值
2. 长度为i - j + 1写例子来计算

Python代码：

1
2
3
4
5
6
7
8
9

def minSubArrayLen(self, target: int, nums: List[int]) -> int:
	min_len, num_sum, left = float('inf'), 0, 0
	for i in range(len(nums)):
		num_sum += nums[i]
		while num_sum >= target:
			min_len = min(min_len, i - left + 1)
			num_sum -= nums[left]
			left += 1
	return 0 if min_len == float('inf') else min_len

算法分析：

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

LeetCode 310 Minimum Height Trees

For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example 1:

Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]

<pre> 0 | 1 /
2 3 </pre>

return [1]

Example 2:

Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

<pre> 0 1 2 \ | / 3 | 4 | 5 </pre>

return [3, 4]

Note:

(1) According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”

(2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

题目大意：

对于一棵无向树，我们可以选择它的任意节点作为根。得到的结果就是有根树。在所有可能的有根树中，高度最小的称为最小高度树（MHT）。
给定一个无向图，编写函数找出所有的最小高度树，并返回其根标号的列表。

解题思路：

此题本质上求最长路径上的中间1-2个节点。由于根节点不确定，从叶节点出发，层层剥离，这就是拓扑排序(inDegree数组)。而且需要知道最后一层的1-2个节点，所以考虑用按层遍历BFS（两数组）。见KB。

注意事项：

1. 由于最后一层可能是1-2个节点，所以要用一个变量res把最后一层记录下来, res = list(queue)在开始和循环中。
2. 还有一点要注意的是这是无向图，所以入度=1而不是0时候即入队列。
3. 单一节点(没有边)返回空列表

Python代码：

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

def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
	if not edges:
		return [0] # remember
	graph = collections.defaultdict(list)
	in_degree = [0] * n
	for li in edges:
		graph[li[0]].append(li[1])
		graph[li[1]].append(li[0])
		in_degree[li[0]] += 1
		in_degree[li[1]] += 1
	queue = collections.deque([i for i in range(len(in_degree)) if in_degree[i] == 1])
	res = list(queue) # remember
	while queue:
		for _ in range(len(queue)):
			node = queue.popleft()
			for neighbor in graph[node]:
				in_degree[neighbor] -= 1
				if in_degree[neighbor] == 1:
					queue.append(neighbor)
		if queue: # remember
			res = list(queue)
	return res

注意事项：

1. 由于最后一层可能是1-2个节点，所以要用一个变量把最后一层记录下来。
2. 还有一点要注意的是这是无向图，所以入度=1而不是0时候即入队列。

Topological:

1. 根据边统计每个节点的入度数记入in[i]
2. 找出度数为0的节点加入到Queue
3. 取出队首节点，把此节点邻接的节点度数减1，如果度数为0，加入到队列，循环直到队列为空

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

public List<Integer> findMinHeightTrees(int n, int[][] edges) {
	if(n==1 && edges.length==0){
		return new ArrayList<Integer>(Arrays.asList(new Integer[]{0}));
	}
	ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	int num = n;
	for(int i=0;i<n;i++)
		graph.add(new ArrayList<Integer>());
	int[] inDegree = new int[n];
	//populate inDegree & convert to graph
	for(int i=0;i<edges.length;i++){
		inDegree[edges[i][0]]++;
		inDegree[edges[i][1]]++;
		graph.get(edges[i][1]).add(edges[i][0]);
		graph.get(edges[i][0]).add(edges[i][1]);
	}
	Queue<Integer> q = new LinkedList<Integer>();
	Queue<Integer> q2 = new LinkedList<Integer>();

	for(int i=0;i<inDegree.length;i++){
		if(inDegree[i]==1)
			q.offer(i);
	}
	Queue<Integer> lastLayerQ = new LinkedList<Integer>(q);
	while(!q.isEmpty()){
		Integer v = q.poll();
		for(int neighbor : graph.get(v)){
			if(--inDegree[neighbor]==1)
				q2.offer(neighbor);
		}
		if(q.isEmpty() && !q2.isEmpty()){
			q = q2;
			q2 = new LinkedList<Integer>();
			lastLayerQ = new LinkedList<Integer>(q);
		}
			
	}

	return (List)lastLayerQ;
}

算法分析：

时间复杂度为O(n)，w为树的所有层里面的最大长度，空间复杂度O(w)。