KK's blog

算法思路：

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

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.

Input: target = 4, nums = [1,4,4]
Output: 1

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

算法思路：

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]]

        0
        |
        1
       / \
      2   3

return [1]

Example 2:

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

     0  1  2
      \ | /
        3
        |
        4
        |
        5

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

LeetCode 329 Longest Increasing Path in a Matrix

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Return 4
The longest increasing path is [1, 2, 6, 9].

Example 2:

nums = [
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

Return 4
The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

题目大意：

给定一个整数矩阵，计算其最长递增路径的长度。
从每一个单元格出发，你可以向四个方向移动：左右上下。你不可以沿着对角线移动也不能移出边界。（亦即，环绕是不允许的）。

Floyd解题思路：

这是经典题，类似于LIS题，只要将以每个点为终点的最长路径长度存起来，就可以类推它的邻近点的最长长度（DP）。f(x,y)=max{f(x,y),4个邻近点的f+1}
由于这是求最长路径题且为矩阵，可以考虑按步长计算，就是Floyd的思路，就是先计算步长为1,2一直到所以最长路径长度矩阵长度不再更新为止。
另一个思路也是用矩阵存起每个点最长路径长度，但用DFS搜索，直至这个点的值不为初始值为止，详见书影博客。

注意事项：

1. 矩阵为空或长度为0
2. 当任何值没有更新时，Floyd停止计算

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

public int longestIncreasingPath(int[][] matrix) {
	if (matrix==null || matrix.length==0)
		return 0;
	int[][] path = new int[matrix.length][matrix[0].length];
	for(int i=0;i<matrix.length;i++)
		for(int j=0;j<matrix[0].length;j++)
			path[i][j] = 1;
	
	boolean nextPath = true;
	while(nextPath){
		nextPath = false;
		for(int i=0;i<matrix.length;i++)
			for(int j=0;j<matrix[0].length;j++){
				if(changeCell(matrix, path, i, j))
					nextPath = true;
			}
	}
	
	int max = 1;
	for(int i=0;i<matrix.length;i++)
		for(int j=0;j<matrix[0].length;j++)
			if(path[i][j]>max)
				max = path[i][j];
	return max;
}

public boolean changeCell(int[][] matrix, int[][] path, int i, int j){
	int pre = path[i][j];
	
	if(i-1>=0 && matrix[i-1][j]<matrix[i][j] &&  path[i-1][j]+1>path[i][j])
		path[i][j] = path[i-1][j]+1;
	
	if(i+1<matrix.length && matrix[i+1][j]<matrix[i][j] &&  path[i+1][j]+1>path[i][j])
		path[i][j] = path[i+1][j]+1;
	
	if(j-1>=0 && matrix[i][j-1]<matrix[i][j] &&  path[i][j-1]+1>path[i][j])
		path[i][j] = path[i][j-1]+1;
	
	if(j+1<matrix[0].length && matrix[i][j+1]<matrix[i][j] &&  path[i][j+1]+1>path[i][j])
		path[i][j] = path[i][j+1]+1;
	
	if(pre!=path[i][j])
		return true;
	else return false;
}

算法分析：

k为最长路径长度，时间复杂度为O(kn2)，空间复杂度O(n2)。

DP算法II解题思路(推荐)：

求最值，考虑用DP，但DP的应用条件为有序，所以不妨将所有值排序。
先对所有数的值排序作为新的输入数组，按这个顺序，计算DP，每个点的往前4个方向的DP值+1。
如题第一个例子, 元祖里第一个为值，后两个为xy坐标
[(1, 2, 1), (1, 2, 2)…]
递归公式：

1

dp[x][y] = dp[x + dx][y + dy] + 1, ifmatrix[x][y] > matrix[x + dx][y + dy]:

注意事项：

1. 当递增时，才更新DP，Line 13

Python代码：

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

def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
	ary = []
	for i in range(len(matrix)):
		for j in range(len(matrix[0])):
		   ary.append((matrix[i][j], i, j))
	ary.sort()
	dp = [[1 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
	for val, _x, _y in ary:
		for _dx, _dy in OFFSETS:
			x, y = _x + _dx, _y + _dy
			if x < 0 or x >= len(matrix) or y < 0 or y >= len(matrix[0]):
				continue
			if matrix[x][y] > matrix[_x][_y]:
				dp[x][y] = max(dp[x][y], dp[_x][_y] + 1)
	return max(map(max, dp))

算法分析：

排序是n^2logn^2 = n^2logn, dp计算是n^2
所以时间复杂度为O(n2logn)，空间复杂度O(n2)

算法III解题思路：

这题也可以额用记忆性搜索DFS来解。

LeetCode

You are given an m x n grid grid of values 0, 1, or 2, where:

each 0 marks an empty land that you can pass by freely, each 1 marks a building that you cannot pass through, and
each 2 marks an obstacle that you cannot pass through.

You want to build a house on an empty land that reaches all buildings in the shortest total travel distance. You can only move up, down, left, and right.

Return the shortest travel distance for such a house. If it is not possible to build such a house according to the above rules, return -1.

The total travel distance is the sum of the distances between the houses of the friends and the meeting point.

The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

Example 1:

Input: grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 7
Explanation: Given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2).
The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal.
So return 7.

Example 2:

Input: grid = [[1,0]]
Output: 1

Example 3:

Input: grid = [[1]]
Output: -1

Constraints: m == grid.length
n == grid[i].length 1 <= m, n <= 50
grid[i][j] is either 0, 1, or 2. There will be at least one building in the grid.

题目大意：

找到所有大厦最短距离的点，这个点不能是大厦也不能是障碍

解题思路：

一开始觉得类似于LeetCode 296 Best Meeting Point，但由于有障碍，所以不能用贪婪法。最值考虑用BFS。属于对所有节点BFS。类似于LeetCode 200 Number of Islands，
从每一栋大厦开始做BFS，计算每个点到此大厦距离。然后对累计到这个点的总距离矩阵dis中。最后求距离矩阵的最小值。

此题难点在于-1的情况，也就是一个点不能到达其中一个building或者是这个building不能到达的点。所以要再用一个矩阵house_count来记录每一个点能到达的大厦数。

解题步骤：

N/A

注意事项：

1. -1的情况，用一个矩阵house_count来记录每一个点能到达的大厦数。
2. 用常数记录矩阵长和宽，不用x >= len(grid) or y >= len(grid[0]), 否则会TLE

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

OFFSETS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def shortestDistance(self, grid: List[List[int]]) -> int:
	dis = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]
	house_count = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]
	total_houses = 0
	for i in range(len(grid)):
		for j in range(len(grid[0])):
			if grid[i][j] == 1:
				self.bfs(grid, i, j, dis, house_count)
				total_houses += 1
	min_dis = float('inf') # remember
	for i in range(len(dis)):
		for j in range(len(dis[0])):
			if dis[i][j] > 0 and house_count[i][j] == total_houses:
				min_dis = min(min_dis, dis[i][j])
	return -1 if min_dis == float('inf') else min_dis # remember

def bfs(self, grid, start_x, start_y, dis, house_count):
	h = len(grid)
	w = len(grid[0]) # remember otherwise TLE
	queue = collections.deque([(start_x, start_y, 0)])
	visited = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]
	visited[start_x][start_y] = True
	while queue:
		node = queue.popleft()
		for _dx, _dy in OFFSETS:
			x, y = node[0] + _dx, node[1] + _dy
			if x < 0 or x >= h or y < 0 or y >= w or grid[x][y] != 0 or visited[x][y]:
				continue
			queue.append((x, y, node[2] + 1))
			visited[x][y] = True
			dis[x][y] += node[2] + 1
			house_count[x][y] += 1

算法分析：

时间复杂度为O(nm * nm)，空间复杂度O(nm)