KK's blog

LeetCode

Input: x = 3, y = 4, points = [[1,2],[3,1],[2,4],[2,3],[4,4]]
Output: 2
Explanation: Of all the points, only [3,1], [2,4] and [4,4] are valid. Of the valid points, [2,4] and [4,4] have the smallest Manhattan distance from your current location, with a distance of 1. [2,4] has the smallest index, so return 2.

Input: x = 3, y = 4, points = [[3,4]]
Output: 0
Explanation: The answer is allowed to be on the same location as your current location.

Input: x = 3, y = 4, points = [[2,3]]
Output: -1
Explanation: There are no valid points.

题目大意：

给定一个坐标和一堆坐标，这个坐标与某个点在同一条y轴或x轴上叫合法点，求它到这些点的最小曼哈顿距离对应的点的下标，若有多个结果，返回最小的数组下标。

解题思路：

Easy题，根据题意求

解题步骤：

N/A

注意事项：

1. Python代码：

   1 2 3 4 5 6 7 8 9 10 11

   def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int: min_dis = float('inf') res = -1 for i, (_x, _y) in enumerate(points): if x == _x or y == _y: if abs(x - _x) + abs(y - _y) < min_dis: min_dis = abs(x - _x) + abs(y - _y) res = i elif abs(x - _x) + abs(y - _y) == min_dis and i < res: res = i return res

算法分析：

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

LeetCode

You are given an undirected graph. You are given an integer n which is the number of nodes in the graph and an array edges, where each edges[i] = [u<sub>i</sub>, v<sub>i</sub>] indicates that there is an undirected edge between u<sub>i</sub> and v<sub>i</sub>.

A connected trio is a set of three nodes where there is an edge between every pair of them.

The degree of a connected trio is the number of edges where one endpoint is in the trio, and the other is not.

Return the minimum degree of a connected trio in the graph, or -1 if the graph has no connected trios.

Example 1:

Input: n = 6, edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]
Output: 3
Explanation: There is exactly one trio, which is [1,2,3]. The edges that form its degree are bolded in the figure above.

Example 2:

Input: n = 7, edges = [[1,3],[4,1],[4,3],[2,5],[5,6],[6,7],[7,5],[2,6]]
Output: 0
Explanation: There are exactly three trios:
1) [1,4,3] with degree 0.
2) [2,5,6] with degree 2.
3) [5,6,7] with degree 2.

Constraints:

2 <= n <= 400 edges[i].length == 2
`1 <= edges.length <= n (n-1) / 2*1 <= u<sub>i</sub>, v<sub>i</sub> <= n*u<sub>i</sub> != v<sub>i</sub>`
* There are no repeated edges.

题目大意：

给定一个图，trio是三个节点直接互相相连，而度数表示连着trio的边的个数

解题思路：

根据定义，找出所有三个节点的组合，判断是否trio，然后根据trio的每个节点的度数总和 - 6即为所求
遍历所有三个节点组合时，会重复了两次。所以一个优化是，先按度数排序节点，若节点度数大于等于最小度数除以3，跳出循环。因为这个最小度数的节点已经大于等于3，trio里其他两个度数比它大的节点的度数更加会大于最小度数除以3，这样总度数肯定大于此时的最小度数

解题步骤：

N/A

注意事项：

1. 根据定义，找出所有三个节点的组合u -> v, v -> w, w是否在u中，判断是否trio。先按度数排序节点，若节点度数大于等于最小度数除以3，跳出循环
2. 邻接图用set，因为Line 13查找w是否在u中可以提高效率
3. min_degree / 3不是// 3

Python代码：

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

def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:
	graph = collections.defaultdict(set) # use set coz if w in graph[u]
	for u, v in edges:
		graph[u].add(v)
		graph[v].add(u)

	min_degree = float('inf')
	for u in sorted(range(1, n + 1), key=lambda x: len(graph[x])):
		if len(graph[u]) >= min_degree / 3: # remember / 3 not // 3
			break
		for v in graph[u]:
			for w in graph[v]:
				if w in graph[u]:
					min_degree = min(min_degree, len(graph[u]) + len(graph[v]) + len(graph[w]))
	return min_degree - 6 if min_degree != float('inf') else -1

算法分析：

时间复杂度为O(n3)，空间复杂度O(n2)

LeetCode

You are given the root of a binary tree with n nodes where each node in the tree has node.val coins. There are n coins in total throughout the whole tree.

In one move, we may choose two adjacent nodes and move one coin from one node to another. A move may be from parent to child, or from child to parent.

Return the minimum number of moves required to make every node have exactly one coin.

Example 1:

Input: root = [3,0,0]
Output: 2
Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.

Example 2:

Input: root = [0,3,0]
Output: 3
Explanation: From the left child of the root, we move two coins to the root [taking two moves]. Then, we move one coin from the root of the tree to the right child.

Constraints:

The number of nodes in the tree is n. 1 <= n <= 100
0 <= Node.val <= n The sum of all Node.val is n.

题目大意：

二叉树某些节点含有硬币，求将这些硬币推向其他节点，使得所有节点都有一个硬币，求总移动次数

解题思路：

先思考，若硬币都在root，也就是求所有节点的路径和。可以用每个节点的路径和求和，也可以定义dfs返回节点数，用全局变量加左右数，每轮递归都加一次，所以每个节点被加了其路径长度的次数。本算法采用后者
下面思考若硬币不在root，由于硬币可以从儿子给父亲，这是双向的，所以dfs定义为儿子给父亲的硬币数，若节点没有硬币，返回值会是负数，也就是父亲给儿子硬币，此时这个负数正是以此节点为root的数的总的节点数，所以与上述定义一致。
所以返回root.val + left + right - 1，left和right都是负数，left + right - 1是树的大小的负数，此结果为剩余硬币推给父亲的硬币数
res += abs(left) + abs(right)左子树和右子树所有节点一起走一条边的路径和

解题步骤：

N/A

注意事项：

1. dfs定义为儿子给父亲的硬币数(若有硬币)，同时是子树的节点数的负数(若无硬币)

Python代码：

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

def distributeCoins(self, root: TreeNode) -> int:
	res = 0

	def dfs(root):
		if not root:
			return 0
		nonlocal res
		left = dfs(root.left)
		right = dfs(root.right)
		res += abs(left) + abs(right)
		return root.val + left + right - 1

	dfs(root)
	return res

算法分析：

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

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

Input: s = “babad”
Output: “bab”
Explanation: “aba” is also a valid answer.

Input: s = “cbbd”
Output: “bb”

题目大意：

最长回文

解题思路：

遍历每个字符，以该字符为中心，往前后比较是否回文，求最长回文

解题步骤：

N/A

注意事项：

1. 回文字符串的中心位可以为1个或2个
2. 此题求最长回文字符串，而不是其长度
3. 避免死循环，记得i -= 1, j += 1
4. Line 63 若不相等，要break，或者return[i + 1:j]和下面return一样

Python代码：

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

def longestPalindrome(self, s: str) -> str:
	res = ''
	for i in range(len(s)):
		tmp = self.longestPalindromeFromCenter(s, i, i)
		if len(tmp) > len(res):
			res = tmp
		if i + 1 < len(s):
			tmp = self.longestPalindromeFromCenter(s, i, i + 1)
			if len(tmp) > len(res):
				res = tmp
	return res

def longestPalindromeFromCenter(self, s, left, right):
	while left >= 0 and right <= len(s) - 1:
		if s[left] != s[right]:
			break
		left -= 1
		right += 1
	return s[left + 1:right]

算法分析：

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