KK's blog

A nonogram is a logic puzzle, similar to a crossword, in which the player is given
a blank grid and has to color it according to some instructions. Specifically,
each cell can be either black or white, which we will represent as 0 for black and
1 for white.
+————+
| 1 1 1 1 |
| 0 1 1 1 |
| 0 1 0 0 |
| 1 1 0 1 |
| 0 0 1 1 |
+————+
For each row and column, the instructions give the lengths of contiguous runs of
black (0) cells. For example, the instructions for one row of [ 2, 1 ] indicate
that there must be a run of two black cells, followed later by another run of one
black cell, and the rest of the row filled with white cells.
These are valid solutions: [ 1, 0, 0, 1, 0 ] and [ 0, 0, 1, 1, 0 ] and also [ 0,
0, 1, 0, 1 ]
This is not valid: [ 1, 0, 1, 0, 0 ] since the runs are not in the correct order.
This is not valid: [ 1, 0, 0, 0, 1 ] since the two runs of 0s are not separated by
1s.
Your job is to write a function to validate a possible solution against a set of
instructions. Given a 2D matrix representing a player’s solution; and instructions
for each row along with additional instructions for each column; return True or
False according to whether both sets of instructions match.

题目大意：

Nonogram日本游戏，0表示黑子，[2, 1]表示黑子的连续数目，如棋盘状态[ 1, 0, 0, 1, 0 ]，表示连续黑子数为[2, 1]
[ 1, 0, 0, 0, 1 ]连续黑子数为[3]. 验证棋盘的每一行和每一列是否满足rows和cols所指定的连续黑子数

解题思路：

按题意求解

解题步骤：

N/A

注意事项：

1. 递归只有一种情况
2. 答案需求全局

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

def valid_nonogram(self, matrix, rows, cols):
	for i in range(len(matrix)):
		if self.get_consecutive_zeros(matrix[i]) != rows[i]:
			return False
	for j in range(len(matrix[0])):
		col_vals = []
		for i in range(len(matrix)):
			col_vals.append(matrix[i][j])
		if self.get_consecutive_zeros(col_vals) != cols[j]:
			return False
	return True

# [ 1, 0, 0, 1, 0 ] -> [2, 1], # of 0s
def get_consecutive_zeros(self, matrix_row):
	count, res = 0, []
	for n in matrix_row:
		if n == 0:
			count += 1
		else:
			if count > 0:
				res.append(count)
			count = 0
	if count > 0:
		res.append(count)
	return res

算法分析：

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

LeetCode

Given a root of an N-ary tree, you need to compute the length of the diameter of the tree.

The diameter of an N-ary tree is the length of the longest path between any two nodes in the tree. This path may or may not pass through the root.

(Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value.)

Example 1:

Input: root = [1,null,3,2,4,null,5,6]
Output: 3
Explanation: Diameter is shown in red color.

Example 2:

Input: root = [1,null,2,null,3,4,null,5,null,6]
Output: 4

Example 3:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: 7

Constraints:

The depth of the n-ary tree is less than or equal to 1000. The total number of nodes is between [1, 10<sup>4</sup>].

题目大意：

求树的直径：任何两个节点的最大距离

解题思路：

类似于LeetCode 543 Diameter of Binary Tree，但此题为N叉树

解题步骤：

DFS

注意事项：

1. 求数组中最大的两数和，用去掉最大值的方法得到次大值。还要注意初始值加入[1, 1]，避免没有儿子节点或只有一个的情况

Python代码：

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

def diameter(self, root: 'Node') -> int:
	max_len = 0

	def dfs(root):
		if not root:
			return 0
		nonlocal max_len
		path_len = [1, 1]
		for child in root.children:
			path_len.append(dfs(child) + 1)
		largest = max(path_len)
		path_len.remove(largest)
		second_largest = max(path_len)
		total = largest + second_largest - 1
		max_len = max(total, max_len)
		return largest

	dfs(root)
	return max_len - 1

算法分析：

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

LeetCode

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Example 1:

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2:

Input: root = [1,2]
Output: 1

Constraints:

The number of nodes in the tree is in the range [1, 10<sup>4</sup>]. -100 <= Node.val <= 100

题目大意：

求树的直径：任何两个节点的最大距离

解题思路：

DFS

解题步骤：

N/A

注意事项：

1. 三种情况：自己+左，自己+右，左+右，不要漏掉最后一种
2. 用nonlocal就不用定义self.max_len的全局变量

Python代码：

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

def diameterOfBinaryTree(self, root: TreeNode) -> int:
	max_len = 0

	def dfs(root):
		if not root:
			return 0
		nonlocal max_len
		left = dfs(root.left) + 1
		right = dfs(root.right) + 1
		res = max(left, right)
		total = left + right - 1
		max_len = max(res, total, max_len)
		return res

	dfs(root)
	return max_len - 1

算法分析：

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

LeetCode

Given the root of a binary tree, return the length of the longest consecutive path in the tree.

A consecutive path is a path where the values of the consecutive nodes in the path differ by one. This path can be either increasing or decreasing.

For example, [1,2,3,4] and [4,3,2,1] are both considered valid, but the path [1,2,4,3] is not valid.

On the other hand, the path can be in the child-Parent-child order, where not necessarily be parent-child order.

Example 1:

Input: root = [1,2,3]
Output: 2
Explanation: The longest consecutive path is [1, 2] or [2, 1].

Example 2:

Input: root = [2,1,3]
Output: 3
Explanation: The longest consecutive path is [1, 2, 3] or [3, 2, 1].

Constraints: The number of nodes in the tree is in the range [1, 3 * 10<sup>4</sup>].
`-3 10<sup>4</sup> <= Node.val <= 3 * 10<sup>4</sup>`

题目大意：

求任意节点到另一个节点的最长连续数列的长度(由小到大)

解题思路：

类似于LeetCode 298 Binary Tree Longest Consecutive Sequence，不过由于父亲到儿子可能递增或递减，所以DFS返回值也返回递增和递减的长度

LeetCode 298 Binary Tree Longest Consecutive Sequence 父亲到儿子由小到大
LeetCode 549 Binary Tree Longest Consecutive Sequence II 任一节点到另一个节点由小到大

类似于LeetCode 124 Binary Tree Maximum Path Sum，有四种情况：自己，自己+左，自己+右，左+右

解题步骤：

N/A

注意事项：

1. DFS返回值也返回递增和递减的长度
2. 类似于LeetCode 124 Binary Tree Maximum Path Sum，有四种情况：自己，自己+左，自己+右，左+右

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

def longestConsecutive(self, root: TreeNode) -> int:
	max_len = 0

	def dfs(root):
		if not root:
			return 0, 0  # (increasing, decreasing) from root
		nonlocal max_len
		inc = desc = 1
		lpath = rpath = 1
		left = dfs(root.left)
		right = dfs(root.right)
		if root.left and root.val + 1 == root.left.val:
			lpath += left[0]
		if root.right and root.val + 1 == root.right.val:
			rpath += right[0]
		inc = max(1, lpath, rpath)

		lpath = rpath = 1
		if root.left and root.val - 1 == root.left.val:
			lpath += left[1]
		if root.right and root.val - 1 == root.right.val:
			rpath += right[1]
		desc = max(1, lpath, rpath)

		total = inc + desc - 1
		max_len = max(inc, desc, total, max_len)
		return inc, desc

	dfs(root)
	return max_len

算法分析：

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

LeetCode

Given the root of a binary tree, return the length of the longest consecutive sequence path.

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path needs to be from parent to child (cannot be the reverse).

Example 1:

Input: root = [1,null,3,2,4,null,null,null,5]
Output: 3
Explanation: Longest consecutive sequence path is 3-4-5, so return 3.

Example 2:

Input: root = [2,null,3,2,null,1]
Output: 2
Explanation: Longest consecutive sequence path is 2-3, not 3-2-1, so return 2.

Constraints:

The number of nodes in the tree is in the range `[1, 3 10<sup>4</sup>]. *-3 10<sup>4</sup> <= Node.val <= 3 10<sup>4</sup>`

题目大意：

求从父到子的最长连续数列的长度(由小到大)

解题思路：

DFS

LeetCode 298 Binary Tree Longest Consecutive Sequence 父亲到儿子由小到大
LeetCode 549 Binary Tree Longest Consecutive Sequence II 任一节点到另一个节点由小到大

解题步骤：

N/A

注意事项：

1. 题意是从父到儿子的有小到大数列，而不是儿子到父亲
2. 以root为起点的最长数列，若root不符合条件，不加入left或right的长度
3. 类似于LeetCode 124 Binary Tree Maximum Path Sum，有三种情况：自己，自己+左，自己+右

Python代码：

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

def longestConsecutive(self, root: TreeNode) -> int:
	max_len = 0

	def dfs(root):
		if not root:
			return 0
		nonlocal max_len
		lpath = rpath = 1
		left = dfs(root.left)
		right = dfs(root.right)
		if root.left and root.val + 1 == root.left.val:  # remember not ==
			lpath += left
		if root.right and root.val + 1 == root.right.val:
			rpath += right
		res = max(lpath, rpath)
		max_len = max(res, max_len)
		return res

	dfs(root)
	return max_len

算法分析：

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